Linked List

Senarai tunggal dan ganda: menyisipkan, menghapus, dan menelusuri simpul.

Daftar isi

Linked list, yakni senarai berantai, menyimpan setiap data pada simpul terpisah yang dihubungkan melalui pointer, sehingga banyaknya data tidak perlu diketahui sejak awal program ditulis. Topik ini menggabungkan pengetahuan struct, pointer, dan malloc menjadi struktur data yang utuh. Bahasannya meliputi penyisipan di depan dan di belakang, penghapusan simpul berdasarkan nilainya, hingga penelusuran pada rantai tunggal dan rantai ganda. Setiap mekanisme disertai program yang dapat dijalankan, sehingga perubahan pada pointer dapat diikuti dari keluarannya.

Penyisipan di depan dan di belakang#

Penyisipan pada linked list selalu berarti membangun satu simpul baru dengan malloc, mengisi anggota datanya, lalu menata ulang dua pointer di sekitar posisi baru. Posisi yang paling murah adalah depan, karena hanya kepala rantai yang perlu diubah. Posisi di belakang menuntut penelusuran terlebih dahulu untuk menemukan simpul terakhir, sehingga biayanya sebanding dengan panjang rantai. Diagram berikut menampilkan bentuk rantai tunggal beserta penanda NULL di ujungnya.

Rantai tunggal berisi empat simpul dengan penanda NULL di ujungnya

Kedua fungsi penyisipan pada program berikut menerima struct simpul **kepala, yaitu alamat dari pointer kepala, bukan pointer kepala itu sendiri. Pola ini diperlukan karena fungsi berhak mengubah variabel kepala milik pemanggil, misalnya saat simpul baru justru menjadi kepala yang baru. Apabila hanya nilainya yang dilewatkan, perubahan pada salinan parameter tidak pernah sampai ke pemanggil, sebagaimana perilaku pass by value.

c senarai.c

#include <stdio.h>
#include <stdlib.h>

struct simpul {
    int nilai;
    struct simpul *berikut;
};

struct simpul *simpul_baru(int nilai)
{
    struct simpul *baru = malloc(sizeof(struct simpul));
    if (baru == NULL) {
        fprintf(stderr, "Alokasi gagal.\n");
        exit(1);
    }
    baru->nilai = nilai;
    baru->berikut = NULL;
    return baru;
}

void sisip_depan(struct simpul **kepala, int nilai)
{
    struct simpul *baru = simpul_baru(nilai);
    baru->berikut = *kepala;
    *kepala = baru;
}

void sisip_akhir(struct simpul **kepala, int nilai)
{
    struct simpul *baru = simpul_baru(nilai);
    if (*kepala == NULL) {
        *kepala = baru;
        return;
    }
    struct simpul *p = *kepala;
    while (p->berikut != NULL) {
        p = p->berikut;
    }
    p->berikut = baru;
}

void cetak(const struct simpul *kepala)
{
    for (const struct simpul *p = kepala; p != NULL; p = p->berikut) {
        printf("%d -> ", p->nilai);
    }
    printf("NULL\n");
}

int hapus_nilai(struct simpul **kepala, int nilai)
{
    struct simpul *p = *kepala;
    struct simpul *sebelum = NULL;

    while (p != NULL && p->nilai != nilai) {
        sebelum = p;
        p = p->berikut;
    }
    if (p == NULL) {
        return 0;
    }
    if (sebelum == NULL) {
        *kepala = p->berikut;
    } else {
        sebelum->berikut = p->berikut;
    }
    free(p);
    return 1;
}

void bebaskan_semua(struct simpul **kepala)
{
    while (*kepala != NULL) {
        struct simpul *berikutnya = (*kepala)->berikut;
        free(*kepala);
        *kepala = berikutnya;
    }
}

int main(void)
{
    struct simpul *kepala = NULL;

    sisip_akhir(&kepala, 10);
    sisip_akhir(&kepala, 20);
    sisip_akhir(&kepala, 30);
    printf("Rantai: ");
    cetak(kepala);

    sisip_depan(&kepala, 5);
    printf("Setelah 5 disisipkan di depan: ");
    cetak(kepala);

    if (hapus_nilai(&kepala, 20)) {
        printf("Simpul 20 dihapus: ");
        cetak(kepala);
    }
    if (hapus_nilai(&kepala, 99) == 0) {
        printf("Nilai 99 tidak ditemukan, rantai tetap.\n");
    }

    bebaskan_semua(&kepala);
    printf("Setelah dibebaskan: ");
    cetak(kepala);
    return 0;
}

text Keluaran

Rantai: 10 -> 20 -> 30 -> NULL
Setelah 5 disisipkan di depan: 5 -> 10 -> 20 -> 30 -> NULL
Simpul 20 dihapus: 5 -> 10 -> 30 -> NULL
Nilai 99 tidak ditemukan, rantai tetap.
Setelah dibebaskan: NULL

Perhatikan urutan dua penugasan pada sisip_depan. Pointer simpul baru diarahkan ke kepala lama lebih dahulu, barulah kepala berpindah ke simpul baru. Membalik urutan tersebut membuat sisa rantai menjadi tak terjangkau dari variabel mana pun, sehingga memorinya bocor. Pada sisip_akhir, kasus rantai kosong diperiksa lebih dahulu karena perulangan pencarian simpul terakhir tidak memiliki titik mulai ketika *kepala masih NULL.

Menghapus simpul berdasarkan nilai#

Penghapusan membutuhkan dua pointer yang bergerak bersamaan, yaitu p yang mencari simpul sasaran dan sebelum yang mengingat simpul di belakangnya. Rantai hanya dapat dipotong dari simpul sebelumnya, karena tidak ada jalan mundur pada rantai tunggal. Fungsi hapus_nilai pada program di atas membedakan tiga keadaan, yaitu simpul tidak ditemukan, simpul berada di kepala, dan simpul berada di tengah atau ujung. Nilai kembali berupa int dipakai untuk melaporkan keberhasilan, sehingga pemanggil dapat mencetak pesan yang jelas ketika nilai yang dicari tidak ada.

Apabila simpul sasaran ternyata berada di kepala, rantai dipotong dengan memindahkan *kepala ke p->berikut karena variabel sebelum masih NULL. Untuk keadaan lain, kaitan sebelum->berikut diarahkan langsung ke simpul sesudah sasaran. Pembebasan memori dilakukan setelah kaitan baru terbentuk, dan urutan ini tidak boleh dibalik karena membaca anggota simpul yang sudah di-free merupakan perilaku tak terdefinisi.

Biaya terburuk penghapusan terjadi ketika nilai berada di ujung rantai atau tidak ada sama sekali, karena seluruh simpul harus disusuri lebih dahulu sebelum keberadaan nilai dapat dipastikan. Keadaan ini berbeda dengan penyisipan di depan yang selalu selesai dalam dua penugasan tanpa memandang panjang rantai. Perbedaan biaya semacam inilah yang menentukan di posisi mana sebuah operasi sebaiknya ditempatkan ketika pola aksesnya sudah diketahui.

Linked list ganda dan perbandingannya#

Linked list ganda (doubly linked list) menambah satu anggota pointer bernama sebelum pada setiap simpul, sehingga rantai dapat ditelusuri dari dua arah. Biayanya berupa satu pointer tambahan per simpul dan dua kaitan yang harus dipelihara pada setiap penyisipan. Diagram berikut menampilkan rantai ganda dengan kedua arah kaitannya.

Rantai ganda dengan pointer maju dan pointer mundur pada setiap simpul

Program berikut menyimpan dua pointer, yaitu kepala dan ekor, sehingga penyisipan di belakang tidak perlu menelusuri seluruh rantai lagi. Penelusuran maju bergerak melalui berikut dari kepala, sedangkan penelusuran mundur bergerak melalui sebelum dari ekor, dan keduanya menghasilkan urutan yang berlawanan.

c senarai-ganda.c

#include <stdio.h>
#include <stdlib.h>

struct simpul {
    int nilai;
    struct simpul *sebelum;
    struct simpul *berikut;
};

void sisip_akhir(struct simpul **kepala, struct simpul **ekor, int nilai)
{
    struct simpul *baru = malloc(sizeof(struct simpul));
    if (baru == NULL) {
        fprintf(stderr, "Alokasi gagal.\n");
        exit(1);
    }
    baru->nilai = nilai;
    baru->berikut = NULL;
    baru->sebelum = *ekor;

    if (*kepala == NULL) {
        *kepala = baru;
    } else {
        (*ekor)->berikut = baru;
    }
    *ekor = baru;
}

void cetak_maju(const struct simpul *kepala)
{
    for (const struct simpul *p = kepala; p != NULL; p = p->berikut) {
        printf("%d -> ", p->nilai);
    }
    printf("NULL\n");
}

void cetak_mundur(const struct simpul *ekor)
{
    for (const struct simpul *p = ekor; p != NULL; p = p->sebelum) {
        printf("%d -> ", p->nilai);
    }
    printf("NULL\n");
}

void bebaskan(struct simpul *kepala)
{
    while (kepala != NULL) {
        struct simpul *berikutnya = kepala->berikut;
        free(kepala);
        kepala = berikutnya;
    }
}

int main(void)
{
    struct simpul *kepala = NULL;
    struct simpul *ekor = NULL;
    int data[4] = {10, 20, 30, 40};

    for (int i = 0; i < 4; i++) {
        sisip_akhir(&kepala, &ekor, data[i]);
    }

    printf("Maju  : ");
    cetak_maju(kepala);
    printf("Mundur: ");
    cetak_mundur(ekor);

    bebaskan(kepala);
    printf("Rantai ganda telah dibebaskan seluruhnya.\n");
    return 0;
}

text Keluaran

Maju  : 10 -> 20 -> 30 -> 40 -> NULL
Mundur: 40 -> 30 -> 20 -> 10 -> NULL
Rantai ganda telah dibebaskan seluruhnya.

Pemilihan jenis rantai mengikuti pola akses data. Tabel berikut merangkum perbedaan keduanya dari sisi memori, arah penelusuran, dan biaya penyisipan di akhir.

Aspek	Rantai tunggal	Rantai ganda
Pointer per simpul	satu (`berikut`)	dua (`sebelum` dan `berikut`)
Arah penelusuran	maju saja	maju dan mundur
Penyisipan di akhir	perlu menelusuri atau pointer ekor	langsung melalui pointer ekor
Penghapusan simpul	perlu simpul sebelumnya	cukup simpul itu sendiri

Kesalahan umum#

Empat kesalahan berikut paling sering muncul ketika linked list baru dipraktikkan, dan semuanya berasal dari pengelolaan pointer yang kurang hati-hati. Menggambar rantai pada kertas sebelum menulis kode membantu mengenali kesalahan semacam ini lebih awal.

Menelusuri memakai pointer kepala langsung. Variabel kepala ikut berpindah sehingga alamat awal rantai hilang dan sisa simpul tidak pernah dapat dibebaskan. Gunakan pointer kerja terpisah dan pertahankan kepala sebagai titik kembali.
Membaca anggota simpul setelah dibebaskan. Pemanggilan p->berikut setelah free(p) adalah penggunaan memori yang sudah dikembalikan. Simpan alamat simpul berikutnya pada variabel lokal sebelum membebaskan simpul yang sedang dipegang.
Lupa memeriksa hasil malloc. Simpul baru berupa NULL saat memori habis, dan penugasan baru->nilai pada NULL menghentikan program. Periksa hasil alokasi sebelum anggotanya diisi.
Kondisi putar yang salah. Perulangan dengan while (p->berikut != NULL) berhenti di simpul terakhir dan tidak pernah memprosesnya, sedangkan while (p != NULL) memproses seluruh simpul. Pilih kondisi sesuai tujuan, yaitu mencari simpul terakhir atau memproses semuanya.

Ringkasan#

Setiap simpul berupa struct pada heap yang menunjuk simpul berikutnya, dan rantai berakhir pada NULL.
Penyisipan dan penghapusan di depan maupun di tengah bekerja dengan menata ulang pointer simpul tetangga, dan fungsi yang mengubah kepala menerima struct simpul ** agar perubahannya terasa oleh pemanggil.
Rantai ganda menambah pointer sebelum sehingga penelusuran dua arah dan penghapusan menjadi lebih mudah, dengan biaya satu pointer tambahan per simpul.

Referensi#

malloc(3) — Linux man-pages project — Kontrak alokasi yang dipakai untuk membangun setiap simpul pada rantai.
Linked List — VisuAlgo — Visualisasi interaktif penyisipan, penghapusan, dan penelusuran linked list.