Linked List

Array memakai blok memori kontigu—cepat untuk akses acak, tetapi kaku: menambah atau menghapus elemen di tengah butuh menggeser seluruh elemen setelahnya. Linked list menawarkan alternatif: setiap node menyimpan data dan pointer ke node berikutnya. Memori tersebar di heap, tetapi penambahan/penghapusan di depan bisa O(1). Pada chapter ini kita akan mengimplementasikan singly linked list dengan operasi insert di depan/belakang, delete berdasarkan nilai, traversal, dan search, sambil memperhatikan manajemen memori yang benar.

Struktur Node #

Setiap node pada singly linked list berisi dua field: data (nilai) dan next (pointer ke node berikutnya). Node terakhir memiliki next == NULL sebagai penanda akhir list. Kepala list (head) adalah pointer ke node pertama; bila head == NULL, list kosong.

c
typedef struct node {
    int data;
    struct node *next;
} node;

Field struct node *next bersifat rekursif—struct berisi pointer ke struct itu sendiri. Ini legal di C karena ukuran pointer tidak bergantung pada ukuran struct yang ditunjuk. Akses ke elemen berikutnya: cur = cur->next.

Visualisasi Konsep #

Diagram berikut memperlihatkan singly linked list berisi tiga node yang dihubungkan oleh pointer next, dengan head sebagai pintu masuk dan NULL sebagai penanda akhir:

flowchart LR Head["head (pointer)"] N1["node 1 data = 10 next -> "] N2["node 2 data = 20 next -> "] N3["node 3 data = 30 next -> "] Null["NULL (akhir list)"] Head --> N1 N1 --> N2 N2 --> N3 N3 --> Null

Pada diagram di atas, setiap node pada linked list berisi field data (nilai yang disimpan) dan next (pointer ke node berikutnya). Pointer head adalah pintu masuk list—seluruh operasi traversal, insertion, dan deletion dimulai dari sini. Node terakhir memiliki next == NULL sebagai penanda akhir list. Berbeda dengan array yang menempati blok memori kontigu, node-node pada linked list tersebar di heap dan dihubungkan oleh pointer next; untuk mencapai node ke-i, kita harus traverse dari head mengikuti rantai pointer—operasi O(n). Keunggulan linked list muncul pada insertion/deletion di depan: cukup alokasikan node baru, atur next-nya ke head lama, dan update head—operasi O(1) tanpa perlu menggeser elemen lain.

Implementasi Singly Linked List #

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

typedef struct node {
    int data;
    struct node *next;
} node;

/* Buat node baru */
static node *buat_node(int data) {
    node *n = malloc(sizeof(node));
    if (n == NULL) return NULL;
    n->data = data;
    n->next = NULL;
    return n;
}

/* Sisipkan di awal list */
node *sisip_depan(node *kepala, int data) {
    node *n = buat_node(data);
    if (n == NULL) return kepala;
    n->next = kepala;
    return n;
}

/* Sisipkan di akhir list */
node *sisip_belakang(node *kepala, int data) {
    node *n = buat_node(data);
    if (n == NULL) return kepala;
    if (kepala == NULL) return n;
    node *cur = kepala;
    while (cur->next != NULL) cur = cur->next;
    cur->next = n;
    return kepala;
}

/* Hapus elemen dengan nilai tertentu */
node *hapus_nilai(node *kepala, int data) {
    if (kepala == NULL) return NULL;
    if (kepala->data == data) {
        node *tmp = kepala->next;
        free(kepala);
        return tmp;
    }
    node *cur = kepala;
    while (cur->next != NULL && cur->next->data != data) {
        cur = cur->next;
    }
    if (cur->next != NULL) {
        node *tmp = cur->next;
        cur->next = tmp->next;
        free(tmp);
    }
    return kepala;
}

/* Cetak list */
void cetak(node *kepala) {
    node *cur = kepala;
    while (cur != NULL) {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

/* Bebaskan seluruh list */
void hapus_semua(node *kepala) {
    node *cur = kepala;
    while (cur != NULL) {
        node *tmp = cur->next;
        free(cur);
        cur = tmp;
    }
}

int main(void) {
    node *list = NULL;
    list = sisip_belakang(list, 10);
    list = sisip_belakang(list, 20);
    list = sisip_belakang(list, 30);
    list = sisip_depan(list, 5);
    cetak(list);

    list = hapus_nilai(list, 20);
    cetak(list);

    list = hapus_nilai(list, 5);
    cetak(list);

    hapus_semua(list);
    return 0;
}

Output yang Dihasilkan:

text
-> 10 -> 20 -> 30 -> NULL
-> 10 -> 30 -> NULL
-> 30 -> NULL

Setelah menyisipkan 10, 20, 30 di belakang dan 5 di depan, list menjadi 5 -> 10 -> 20 -> 30. Menghapus 20 melepaskan node dari list dan membebaskan memorinya. Menghapus 5 (kepala) mengembalikan kepala baru yaitu 10.

Mari kita telaah baris-baris kode di atas:

Baris 4-7 (struct node): struct self-referential. Field next adalah pointer ke struct node yang sama. Ukuran next adalah sizeof(pointer) (8 byte di 64-bit), tidak bergantung pada ukuran struct.
Baris 10-15 (buat_node): alokasi node baru via malloc. Selalu cek NULL—bila malloc gagal, kembalikan NULL agar pemanggil tahu. Field next diinisialisasi NULL (penting untuk mengakhiri traversal).
Baris 18-23 (sisip_depan): sisip di awal. Node baru menjadi kepala baru. n->next = kepala menghubungkan node baru ke list lama, lalu return n sebagai kepala baru. Kompleksitas O(1).
Baris 26-34 (sisip_belakang): sisip di akhir. Bila list kosong, node baru langsung menjadi kepala. Bila tidak, traversal ke node terakhir (cur->next == NULL) lalu sambungkan. Kompleksitas O(n) karena traversal.
Baris 37-52 (hapus_nilai): hapus node pertama yang nilainya cocok. Kasus kepala ditangani terpisah karena kepala baru berubah. Untuk node lain, traversal sampai menemukan cur->next yang cocok, lalu sambung cur->next = tmp->next dan free(tmp).
Baris 64-71 (hapus_semua): bebaskan seluruh node. Penting: simpan cur->next ke tmp dulu sebelum free(cur), karena free(cur) membuat field cur->next tidak terdefinisi.

Traversal dan Search #

Operasi traversal linked list menggunakan loop while dengan pointer cur. Kompleksitas O(n) untuk traversal penuh. Berikut contoh fungsi panjang() dan cari():

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

typedef struct node {
    int data;
    struct node *next;
} node;

static node *buat_node(int data) {
    node *n = malloc(sizeof(node));
    if (n == NULL) return NULL;
    n->data = data;
    n->next = NULL;
    return n;
}

node *sisip_belakang(node *kepala, int data) {
    node *n = buat_node(data);
    if (n == NULL) return kepala;
    if (kepala == NULL) return n;
    node *cur = kepala;
    while (cur->next != NULL) cur = cur->next;
    cur->next = n;
    return kepala;
}

/* Hitung panjang list */
int panjang(node *kepala) {
    int count = 0;
    node *cur = kepala;
    while (cur != NULL) {
        count++;
        cur = cur->next;
    }
    return count;
}

/* Cari nilai di list, return node* */
node *cari(node *kepala, int data) {
    node *cur = kepala;
    while (cur != NULL) {
        if (cur->data == data) return cur;
        cur = cur->next;
    }
    return NULL;
}

void cetak(node *kepala) {
    node *cur = kepala;
    while (cur != NULL) {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

void hapus_semua(node *kepala) {
    node *cur = kepala;
    while (cur != NULL) {
        node *tmp = cur->next;
        free(cur);
        cur = tmp;
    }
}

int main(void) {
    node *list = NULL;
    int nilai[] = {10, 25, 7, 42, 15, 30};
    int n = sizeof(nilai) / sizeof(nilai[0]);

    for (int i = 0; i < n; i++) {
        list = sisip_belakang(list, nilai[i]);
    }

    cetak(list);
    printf("Panjang list: %d\n", panjang(list));

    int cari_nilai[] = {42, 99};
    for (int i = 0; i < 2; i++) {
        node *found = cari(list, cari_nilai[i]);
        if (found != NULL)
            printf("Cari %d: ditemukan\n", cari_nilai[i]);
        else
            printf("Cari %d: tidak ditemukan\n", cari_nilai[i]);
    }

    hapus_semua(list);
    return 0;
}

Output yang Dihasilkan:

text
10 -> 25 -> 7 -> 42 -> 15 -> 30 -> NULL
Panjang list: 6
Cari 42: ditemukan
Cari 99: tidak ditemukan

Fungsi cari() mengembalikan pointer ke node yang ditemukan (bukan indeks, karena linked list tidak punya akses acak). Bila tidak ketemu, kembalikan NULL. Kompleksitas search adalah O(n) karena harus traversal dari kepala.

Karakteristik dan Tradeoff #

Tabel berikut merangkum tradeoff linked list vs array:

Operasi	Array	Linked List
Akses elemen ke-k	O(1)	O(k)
Sisip di depan	O(n) (geser)	O(1)
Sisip di belakang	O(1) amortized	O(n) (tanpa tail pointer)
Hapus elemen	O(n) (geser)	O(1) bila punya pointer ke node
Memori tambahan	0	O(n) untuk pointer `next`
Cache locality	Baik (kontigu)	Buruk (tersebar)