Linked List

Dynamic array menyimpan elemen dalam satu blok memori yang berurutan; linked list memilih jalan yang berlawanan. Setiap elemen (node) dialokasikan sendiri-sendiri di mana pun memori menyediakan tempat, lalu disambungkan satu sama lain lewat pointer ke node berikutnya. Konsekuensinya menarik: menyambung atau melepas node di depan bisa secepat O(1) tanpa menggeser apa pun, tetapi mengakses “elemen ke-500” tidak lagi bisa langsung — kita harus menelusuri rantai satu per satu. Chapter ini membangun singly linked list secara manual dari struct dan pointer, dua bahan yang sudah kita kuasai di section sebelumnya.

Anatomi Singly Linked List #

Bahan bangunan sebuah singly linked list hanya satu struct: data plus pointer next ke node berikutnya. Node terakhir menunjuk nullptr sebagai tanda akhir rantai, sedangkan pointer head menunjuk node pertama. Untuk membuat operasi penambahan di belakang tetap O(1), implementasi kita juga menyimpan pointer tail ke node terakhir — tanpa itu, setiap insertTail harus menelusuri seluruh list.

head -> [10|next] -> [20|next] -> [30|next] -> nullptr

Skema di atas adalah list berisi 10, 20, 30. Perhatikan bahwa tidak ada indeks: satu-satunya cara menuju node ke-2 adalah mulai dari head dan mengikuti pointer. Setiap operasi yang kita tulis pada bagian berikutnya pada dasarnya hanya tiga gerakan yang sama: menyewa node baru dengan new, memindahkan pointer agar rantai tetap tersambung, dan melepas node yang tidak lagi dipakai dengan delete. Kesalahan klasik pemula adalah memindahkan pointer sebelum menyimpan alamat node berikutnya — rantai terputus dan node sisanya menjadi tak terjangkau sekaligus tidak bisa dibebaskan, itulah memory leak.

Implementasi Manual #

Program berikut memuat seluruh operasi inti — insertHead, insertTail, removeValue, search, dan traverse — beserta destructor yang membersihkan semua node:

// Singly linked list manual: Node + operasi insert, delete, traverse, search.
#include <iostream>

struct Node {
    int data;
    Node* next;
};

class LinkedList {
public:
    LinkedList() : head_(nullptr), tail_(nullptr) {}
    ~LinkedList() {  // hapus semua node agar tidak terjadi memory leak
        Node* sekarang = head_;
        while (sekarang != nullptr) {
            Node* berikut = sekarang->next;
            delete sekarang;
            sekarang = berikut;
        }
    }

    void insertHead(int nilai) {           // O(1): cukup sambung ulang head
        Node* baru = new Node{nilai, head_};
        head_ = baru;
        if (tail_ == nullptr) tail_ = baru;
    }

    void insertTail(int nilai) {           // O(1) karena kita simpan tail
        Node* baru = new Node{nilai, nullptr};
        if (head_ == nullptr) {
            head_ = baru;
            tail_ = baru;
        } else {
            tail_->next = baru;
            tail_ = baru;
        }
    }

    bool removeValue(int nilai) {          // O(n): harus menemukan node-nya
        Node* sekarang = head_;
        Node* sebelum = nullptr;
        while (sekarang != nullptr && sekarang->data != nilai) {
            sebelum = sekarang;
            sekarang = sekarang->next;
        }
        if (sekarang == nullptr) return false;       // nilai tidak ada
        if (sebelum == nullptr) head_ = sekarang->next;  // menghapus head
        else sebelum->next = sekarang->next;
        if (sekarang == tail_) tail_ = sebelum;
        delete sekarang;
        return true;
    }

    Node* search(int nilai) const {        // O(n): telusuri satu per satu
        for (Node* p = head_; p != nullptr; p = p->next) {
            if (p->data == nilai) return p;
        }
        return nullptr;
    }

    void traverse() const {                // cetak seluruh isi list
        for (Node* p = head_; p != nullptr; p = p->next) {
            std::cout << p->data << " -> ";
        }
        std::cout << "NULL\n";
    }

private:
    Node* head_;
    Node* tail_;
};

int main() {
    LinkedList list;
    list.insertTail(10);
    list.insertTail(20);
    list.insertTail(30);
    list.traverse();

    list.insertHead(5);
    list.insertTail(40);
    list.traverse();

    if (list.search(20) != nullptr) std::cout << "20 ditemukan\n";
    if (list.search(99) == nullptr) std::cout << "99 tidak ada\n";

    list.removeValue(20);
    std::cout << "Setelah removeValue(20): ";
    list.traverse();
    return 0;
}

Output yang Dihasilkan:

10 -> 20 -> 30 -> NULL
5 -> 10 -> 20 -> 30 -> 40 -> NULL
20 ditemukan
99 tidak ada
Setelah removeValue(20): 5 -> 10 -> 30 -> 40 -> NULL

Bedah baris penting:

1. Baris 4-7 (struct Node): satu node hanya berisi int data dan pointer next; inilah seluruh “anatomi” list.
2. Baris 12-19 (destructor): menghapus node satu per satu sambil mengingat node berikutnya sebelum node sekarang di-delete — menghapus tanpa menyimpan next terlebih dahulu akan membuat pointer menunjuk memori yang sudah dibebaskan.
3. Baris 21-25 (insertHead): node baru menunjuk head_ lama, lalu head_ dipindah ke node baru. Dua operasi pointer, biaya O(1), tidak peduli seberapa panjang list.
4. Baris 27-36 (insertTail): bila list kosong head_ dan tail_ sama-sama menunjuk node baru; kalau tidak, tail_->next disambung lalu tail_ bergeser — tetap O(1) karena kita menyimpan tail_.
5. Baris 38-51 (removeValue): telusuri sambil menyimpan node sebelum; saat node target ditemukan, sebelum->next melompati node tersebut. Dua kasus khusus: target adalah head (baris 46) dan target adalah tail (baris 48).
6. Baris 53-58 (search): satu-satunya cara adalah menelusuri dari head — biaya O(n), berbeda dengan akses indeks O(1) pada vector.
7. Baris 74-81 (main): tiga insertTail menghasilkan 10 -> 20 -> 30, lalu insertHead(5) menaruh 5 di depan dan insertTail(40) menaruh 40 di belakang.

Keluaran juga menunjukkan perilaku search: 20 ditemukan, sedangkan 99 mengembalikan nullptr. Setelah removeValue(20), node 20 dihapus dari memori dan rantai tersambung langsung dari 10 ke 30.

Linked List vs std::vector #

Perbandingan berikut merangkum trade-off keduanya; kolom Big-O merujuk pada hasil penghitungan yang sudah kita latih:

Aturan praktisnya: default ke std::vector untuk hampir semua kasus, karena kepadatan memori membuatnya menang meski jumlah operasi teoretis sama. Baris terakhir tabel adalah penyebabnya: memori vector yang rapat membuat prosesor membaca banyak elemen sekaligus dalam sekali akses cache, sementara node linked list tersebar di heap sehingga setiap langkah p = p->next berisiko cache miss. Linked list menang justru saat struktur berubah terus-menerus di tengah-tengah data dan akses acak nyaris tidak dilakukan, misalnya daftar pekerjaan yang disisipkan dan dilepas sesuai prioritas selama program berjalan.

Sekilas Doubly Linked List #

Varian kedua menambahkan pointer prev sehingga list bisa ditelusuri dua arah:

struct NodeDua {
    int data;
    NodeDua* prev;  // menunjuk node sebelumnya
    NodeDua* next;  // menunjuk node berikutnya
};

Dengan prev, menghapus node cukup menyambung node->prev->next dan node->next->prev tanpa perlu menelusuri dari head, dan std::list di STL memakai desain ini. Biayanya memori ekstra per node dan kode sambung-menyambung yang lebih rapat, sehingga singly tetap menjadi latihan terbaik untuk memahami manajemen pointer.

Setelah terbiasa menelusuri rantai node, kita siap untuk pola yang memanfaatkannya: stack, struktur LIFO yang bisa dibangun di atas vector maupun linked list ini.

Rujukan resmi: std::list dan std::forward_list .