Linked List dan Memory Management

Linked list berbeda dari std::vector dalam satu hal krusial: setiap node dialokasikan terpisah dengan new, dan pemilik linked list bertanggung jawab membebaskannya dengan delete. Lupa satu node saja menyebabkan memory leak — node tetap di heap tanpa bisa diakses kembali. Pada Chapter ini kita akan memahami konsep ownership node, bagaimana destructor berperan sebagai penjaga RAII, dan bagaimana std::unique_ptr<Node> memberikan jaminan keamanan memori secara otomatis. Kita juga akan melihat AddressSanitizer mendeteksi leak yang sengaja dibuat.

Ownership Node: Siapa yang Memiliki Apa #

Pada linked list berbasis raw pointer, setiap new Node(...) menghasilkan blok memori di heap. Pointer ke blok itu disimpan di head_ atau di field next dari node sebelumnya. Pertanyaan ownership: siapa yang bertanggung jawab delete?

Jawabannya: linked list sebagai objek memiliki semua node. Destructor linked list wajib traverse dan delete setiap node. Bila ada fungsi yang menerima Node* dan menyimpannya tanpa salinan pointer lain, ownership berpindah — fungsi tersebut sekarang penanggung jawab.

Memory Leak: Apa dan Bagaimana #

Memory leak terjadi saat blok heap dialokasikan tetapi tidak pernah dibebaskan, sementara referensi ke blok itu hilang. Pada linked list, leak paling umum muncul karena:

1. Lupa memanggil destructor (mis. leak dari fungsi yang membuat list lokal).
2. Hapus head_ tanpa traverse — node kedua dan seterusnya kehilangan referensi.
3. Iterasi yang delete cur sebelum menyimpan cur->next.
4. Exception terjadi di tengah insert, node baru sudah dialokasikan tetapi belum terhubung ke list.

Demo Leak dengan Raw Pointer #

#include <iostream>
#include <memory>

struct NodeRaw {
    int nilai;
    NodeRaw* next;
    NodeRaw(int v) : nilai(v), next(nullptr) {}
};

// Demo memory leak
void demo_leak() {
    NodeRaw* head = new NodeRaw(1);
    head->next = new NodeRaw(2);
    head->next->next = new NodeRaw(3);
    // Lupa traverse & delete — setelah fungsi selesai,
    // 3 node bocor (tetap di heap, tak bisa diakses)
    std::cout << "[demo_leak] keluar tanpa cleanup — 3 node bocor\n";
}

struct NodeSmart {
    int nilai;
    std::unique_ptr<NodeSmart> next;
    NodeSmart(int v) : nilai(v), next(nullptr) {}
};

// Demo RAII otomatis via unique_ptr
void demo_smart() {
    auto head = std::make_unique<NodeSmart>(1);
    head->next = std::make_unique<NodeSmart>(2);
    head->next->next = std::make_unique<NodeSmart>(3);

    // Traverse
    NodeSmart* cur = head.get();
    while (cur != nullptr) {
        std::cout << cur->nilai << (cur->next ? " -> " : " -> null\n");
        cur = cur->next.get();
    }
    // Setelah fungsi selesai, destructor unique_ptr cascade:
    // head di-destroy → head->next di-destroy → head->next->next di-destroy
    std::cout << "[demo_smart] keluar — cleanup otomatis\n";
}

int main() {
    std::cout << "=== Raw pointer (rentan leak) ===\n";
    demo_leak();

    std::cout << "\n=== Smart pointer (RAII otomatis) ===\n";
    demo_smart();

    return 0;
}

Output yang Dihasilkan:

=== Raw pointer (rentan leak) ===
[demo_leak] keluar tanpa cleanup — 3 node bocor

=== Smart pointer (RAII otomatis) ===
1 -> 2 -> 3 -> null
[demo_smart] keluar — cleanup otomatis

1. Baris NodeRaw* head = new NodeRaw(1);: alokasi node pertama. head adalah satu-satunya referensi ke node ini.
2. Baris head->next = new NodeRaw(2);: alokasi node kedua. Referensi disimpan di head->next. Bila kita delete head tanpa traverse, node kedua kehilangan referensi.
3. Akhir fungsi demo_leak: head keluar scope sebagai pointer lokal — head hilang. Ketiga node tetap di heap, tanpa cara untuk dijangkau. Inilah memory leak.
4. std::make_unique<NodeSmart>(1): alokasi dengan ownership disimpan di std::unique_ptr. Saat head keluar scope, destructor unique_ptr otomatis delete node pertama.
5. Field std::unique_ptr<NodeSmart> next;: cascade destruction. Saat node pertama di-destroy, field next (yang juga unique_ptr) ikut di-destroy, yang pada gilirannya meng-destroy node kedua, dan seterusnya. Satu destructor memicu cleanup seluruh chain.

RAII: Resource Acquisition Is Initialization #

Idiom RAII menyatakan: setiap resource (memori, file, lock) harus dibungkus dalam objek yang mengakuisisi di constructor dan membebaskan di destructor. Destructor dipanggil otomatis saat objek keluar scope, bahkan saat exception — ini jaminan keamanan resource.

Pada linked list dengan raw pointer:

• Constructor menginisialisasi head_ = nullptr (list kosong).
• push_back meng-new node.
• Destructor traverse dan delete setiap node.

Dengan RAII yang benar, linked list yang dibuat di stack tidak akan pernah leak — destructor menangani semuanya. Yang menjadi masalah adalah bila kita menyimpan raw pointer tanpa destructor yang benar.

Smart Pointer: std::unique_ptr<Node> #

Mekanisme: Ownership Eksklusif #

std::unique_ptr<T> adalah smart pointer dengan ownership eksklusif — hanya satu unique_ptr yang boleh menunjuk ke objek. Saat unique_ptr keluar scope, objek di-delete otomatis.

struct NodeSmart {
    int nilai;
    std::unique_ptr<NodeSmart> next;  // ownership node berikutnya
    NodeSmart(int v) : nilai(v), next(nullptr) {}
};

Keuntungan pakai unique_ptr<Node>:

1. Tidak ada leak: destructor cascade otomatis membebaskan seluruh chain.
2. Tidak ada double-free: ownership eksklusif mencegah dua pointer delete objek yang sama.
3. Tidak ada dangling pointer: setelah move, sumber di-set nullptr.
4. Move semantics natural: std::move(head) memindahkan kepemilikan ke list lain.

Trade-off unique_ptr vs Raw Pointer #

Verifikasi dengan AddressSanitizer #

AddressSanitizer (ASan) adalah tool yang menginstrumentasi program untuk mendeteksi memory error: leak, use-after-free, buffer overflow. Compile dengan -fsanitize=address:

g++ -std=c++17 -O0 -g -fsanitize=address -o leak_test linked-list-dan-memory-management.cpp
./leak_test

Output (disederhanakan):

==6789==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 16 byte(s) in 1 object(s) allocated from:
    #0 ... in operator new
    #1 ... in demo_leak() ...:12

Indirect leak of 16 byte(s) in 1 object(s) allocated from:
    #1 ... in demo_leak() ...:14

Indirect leak of 16 byte(s) in 1 object(s) allocated from:
    #1 ... in demo_leak() ...:13

SUMMARY: AddressSanitizer: 48 byte(s) leaked in 3 allocation(s).

ASan menunjukkan tiga leak: 16 byte direct (node pertama yang head menunjuk) dan dua indirect leak (node kedua dan ketiga, yang hanya bisa dijangkau melalui node pertama). Total 48 byte = 3 node × 16 byte per node (int 4 byte + 8 byte pointer + 4 byte padding).

demo_smart tidak muncul di laporan leak — cleanup otomatis via unique_ptr bekerja.

Pola Hapus yang Aman dengan Raw Pointer #

Bila Anda tetap memakai raw pointer (mis. untuk kompatibilitas C-API), pastikan pola hapus benar:

// BENAR — simpan next SEBELUM delete
void clear_benar(Node<T>* head) {
    Node<T>* cur = head;
    while (cur != nullptr) {
        Node<T>* nx = cur->next;  // simpan dulu!
        delete cur;                 // baru delete
        cur = nx;
    }
}

// SALAH — use-after-free, cur->next setelah delete cur
void clear_salah(Node<T>* head) {
    Node<T>* cur = head;
    while (cur != nullptr) {
        delete cur;
        cur = cur->next;  // UB: cur sudah dangling
    }
}

Ringkasan #

• Ownership linked list: objek linked list memiliki semua node dan wajib membebaskannya via destructor.
• Memory leak terjadi bila raw pointer ke node hilang sebelum delete — AddressSanitizer mendeteksinya dengan -fsanitize=address.
• RAII membungkus resource dalam objek; destructor otomatis membebaskan saat keluar scope.
• std::unique_ptr<Node> memberikan ownership eksklusif dengan overhead nol — cascade destruction otomatis membersihkan seluruh chain.
• Untuk produksi, lebih baik pakai std::list/std::forward_list atau unique_ptr-based linked list daripada raw pointer manual.