Konsep Linked List

Array menyimpan elemen dalam blok memori yang kontigu sehingga akses indeks O(1) sangat cepat. Sayangnya, array berukuran tetap — bila kita perlu menambah elemen di tengah atau di akhir, seluruh blok harus dipindahkan. Linked list lahir untuk menjawab kelemahan ini: setiap elemen (node) dialokasikan terpisah di heap dan dihubungkan dengan pointer. Kita tidak perlu tahu ukuran di depan, dan menyisipkan/menghapus di posisi yang diketahui dapat dilakukan dalam O(1). Pada Chapter ini kita akan memahami layout memori linked list, perbandingannya dengan array, dan kapan memilih linked list sebagai struktur data.

Mengapa Linked List Ada #

Tiga masalah utama array statis yang ingin dipecahkan linked list:

1. Ukuran tetap — int a[100] memesan 100 elemen walau hanya butuh 5, dan tidak bisa tumbuh melebihi 100.
2. Insert/hapus di tengah mahal — menambah elemen pada indeks 0 berarti menggeser seluruh elemen lain (O(n)).
3. Realokasi besar — array dinamis seperti std::vector mengatasi masalah (1) dengan realokasi penuh ketika kapasitas penuh, yang menyalin seluruh elemen lama.

Linked list mengorbankan akses acak O(1) untuk mendapatkan:

• Ukuran dinamis — tumbuh dan menyusut sesuai kebutuhan.
• Insert/delete O(1) bila pointer ke node sudah diketahui.
• Tidak perlu realokasi besar — setiap node dialokasikan terpisah.

Anatomi Sebuah Node #

Node adalah unit terkecil linked list. Setiap node memuat data dan pointer ke node berikutnya. Pada singly linked list, satu pointer cukup; pada doubly linked list, ada pointer prev tambahan.

Head adalah pintu masuk — pointer ke node pertama. Tanpa head, linked list hilang. Setiap operasi traverse, insert, atau delete dimulai dari head dan mengikuti rantai pointer next.

Layout Memori: Array vs Linked List #

Mari kita bandingkan secara konkret bagaimana array dan linked list menempati memori. Kode berikut mencetak alamat setiap elemen:

#include <iostream>
#include <vector>

// Linked list node
struct Node {
    int nilai;
    Node* berikutnya;
};

int main() {
    // --- Array: alokasi kontigu ---
    int a[5] = {10, 20, 30, 40, 50};
    std::cout << "=== Array (kontigu) ===\n";
    for (int i = 0; i < 5; ++i) {
        std::cout << "a[" << i << "] = " << a[i]
                  << " @ offset +" << (reinterpret_cast<char*>(&a[i]) -
                                        reinterpret_cast<char*>(&a[0]))
                  << " byte\n";
    }

    // --- Linked list: simpul terpisah, dihubungkan pointer ---
    Node* head = new Node{10, nullptr};
    head->berikutnya = new Node{20, nullptr};
    head->berikutnya->berikutnya = new Node{30, nullptr};

    std::cout << "\n=== Linked List (simpul terpisah) ===\n";
    Node* cur = head;
    int idx = 0;
    while (cur != nullptr) {
        std::cout << "node[" << idx << "] = " << cur->nilai
                  << " @ " << cur << ", berikutnya @ " << cur->berikutnya << '\n';
        cur = cur->berikutnya;
        ++idx;
    }

    // cleanup
    cur = head;
    while (cur != nullptr) {
        Node* next = cur->berikutnya;
        delete cur;
        cur = next;
    }
    return 0;
}

Output yang Dihasilkan:

=== Array (kontigu) ===
a[0] = 10 @ offset +0 byte
a[1] = 20 @ offset +4 byte
a[2] = 30 @ offset +8 byte
a[3] = 40 @ offset +12 byte
a[4] = 50 @ offset +16 byte

=== Linked List (simpul terpisah) ===
node[0] = 10 @ 0x55a38f1dc2c0, berikutnya @ 0x55a38f1dc2e0
node[1] = 20 @ 0x55a38f1dc2e0, berikutnya @ 0x55a38f1dc300
node[2] = 30 @ 0x55a38f1dc300, berikutnya @ 0

1. Array offset: setiap elemen int berjarak tepat 4 byte — alamat naik secara deterministik. Inilah yang membuat a[i] ekuivalen dengan *(a + i) dan dihitung dengan aritmetika pointer O(1).
2. Node terpisah: alamat node[0], node[1], dan node[2] (mis. 0x...2c0, 0x...2e0, 0x...300) tidak dijamin berurutan secara logis — new mengembalikan blok dari heap allocator yang mungkin saja tidak berdekatan dengan node sebelumnya.
3. Pointer berikutnya: field berikutnya di setiap node menyimpan alamat node berikutnya — inilah yang menjaga rangkaian logis meskipun memori fisik terpisah. Pada node terakhir, field berikutnya bernilai nullptr (alamat 0).

Tabel Perbandingan Array vs Linked List #

Kapan Memilih Linked List #

Pilih linked list ketika:

1. Ukuran berubah dinamis dan tak terduga — kita tidak ingin realokasi penuh seperti std::vector.
2. Operasi dominan adalah insert/delete di posisi tengah dengan pointer node yang sudah diketahui — misalnya implementasi LRU cache, undo buffer, atau adjacency list.
3. Ingin menghindari copy mahal — elemen besar dapat dipindahkan antar struktur hanya dengan memanipulasi pointer, tanpa menyalin data.

Pilih array (atau std::vector) ketika:

1. Akses acak dominan — a[i] cepat, sedangkan linked list harus traverse O(n).
2. Cache locality penting — kompresi data, algoritma numerik, image processing.
3. Memori ketat — overhead pointer linked list tidak signifikan untuk tipe kecil.

Jenis-Jenis Linked List #

Empat varian utama yang akan kita pelajari di Section ini:

Pemilihan varian tergantung kebutuhan operasi. Doubly mempermudah delete (kita tahu node sebelumnya), circular cocok untuk round-robin scheduling.

Ringkasan #

• Linked list terdiri atas node yang dialokasikan terpisah di heap dan dihubungkan dengan pointer next.
• Array kontigu memungkinkan akses acak O(1) namun insert/delete tengah O(n); linked list kebalikannya.
• Linked list mengorbankan memori (pointer ekstra) dan cache locality untuk fleksibilitas dinamis.
• Pilihan varian (singly, doubly, circular) tergantung operasi yang dominan pada use case.
• Chapter berikutnya akan membahas implementasi singly linked list dari nol menggunakan C++ template.