Implementasi Linked List

Setelah memahami operasi dasar singly linked list di Chapter sebelumnya, sekarang kita menyusun implementasi produksi-grade. Versi ini mencakup empat pilar class C++ modern: destructor (RAII), copy constructor (deep copy), move semantics, dan iterator untuk mendukung range-for. Tanpa empat pilar ini, linked list rentan terhadap double-free, memory leak, dan shallow copy yang berbahaya. Pada Chapter ini kita akan membedah setiap pilar dan melihat bagaimana copy-and-swap idiom menyederhanakan penanganan assignment.

Empat Pilar Class Modern #

Tanpa copy constructor yang benar, compiler menghasilkan shallow copy — dua list berbagi pointer head_. Saat salah satu destructor berjalan, list lain memegang pointer dangling. Ini disebut double-free dan menjadi sumber bug sulit ditemukan.

RAII: Destructor Membebaskan Node #

Mekanisme: Traverse dan Delete Setiap Node #

C++ menjamin destructor dipanggil saat objek keluar scope, bahkan saat exception dilempar. Kita manfaatkan ini untuk traverse list dan delete setiap node:

~LinkedList() { clear(); }

void clear() {
    Node<T>* cur = head_;
    while (cur != nullptr) {
        Node<T>* nx = cur->next;
        delete cur;
        cur = nx;
    }
    head_ = tail_ = nullptr;
    size_ = 0;
}

Penting menyimpan cur->next sebelum delete cur — setelah delete, akses ke cur->next adalah undefined behavior.

Copy Constructor: Deep Copy #

Mekanisme: Traverse Sumber, push_back ke List Baru #

Copy constructor membuat list baru dengan node-node baru yang menampung nilai yang sama. Kita traverse sumber dan panggil push_back untuk setiap elemen:

LinkedList(const LinkedList& other)
    : head_(nullptr), tail_(nullptr), size_(0) {
    for (Node<T>* cur = other.head_; cur != nullptr; cur = cur->next) {
        push_back(cur->nilai);
    }
}

Hasil: dua list terpisah dengan node-node terpisah. Modifikasi satu tidak memengaruhi yang lain.

Move Constructor: Transfer Kepemilikan #

Mekanisme: Curi Pointer, Set Sumber ke Kosong #

Move constructor tidak mengalokasikan node baru — ia “mencuri” pointer head_, tail_, dan size_ dari sumber. Sumber di-set ke keadaan kosong sehingga destructornya tidak menghapus apa pun.

LinkedList(LinkedList&& other) noexcept
    : head_(other.head_), tail_(other.tail_), size_(other.size_) {
    other.head_ = other.tail_ = nullptr;
    other.size_ = 0;
}

noexcept penting karena memungkinkan std::vector dan container lain memilih move daripada copy saat realokasi.

Copy-and-Swap Idiom untuk Assignment #

Aturan #

Penanganan operator= harus berhati-hati:

1. Self-assignment (a = a) — harus aman.
2. Cleanup sumber lama — node lama harus di-free.
3. Exception safety — bila alokasi gagal, list harus tetap valid.

Idiom copy-and-swap menyatukan ketiganya:

LinkedList& operator=(LinkedList other) {  // pass by value → copy
    swap(other);                            // swap dengan temp
    return *this;
}  // temp keluar scope → destructor free list lama kita

Parameter other di-pass-by-value — compiler otomatis memanggil copy constructor (atau move constructor bila rhs adalah rvalue). Setelah swap, list kita berisi data baru, dan other berisi data lama. Saat other keluar scope, destructor membebaskannya.

Iterator untuk Range-for #

Mekanisme: Wrapper Pointer dengan Operator Overloading #

Iterator adalah objek yang berperilaku seperti pointer. Kita bungkus Node<T>* dengan operator *, ++, dan != agar bisa dipakai di range-for:

class Iterator {
public:
    Iterator(Node<T>* p) : ptr_(p) {}
    T& operator*() const { return ptr_->nilai; }
    Iterator& operator++() { ptr_ = ptr_->next; return *this; }
    bool operator!=(const Iterator& o) const { return ptr_ != o.ptr_; }
private:
    Node<T>* ptr_;
};

Iterator begin() const { return Iterator(head_); }
Iterator end()   const { return Iterator(nullptr); }

Sekarang for (int x : list) bekerja — compiler memanggil begin(), end(), operator!=, operator*, dan operator++.

Kode Lengkap Implementasi Produksi-Grade #

#include <iostream>
#include <stdexcept>
#include <utility>

template <typename T>
struct Node {
    T nilai;
    Node* next;
    Node(const T& v) : nilai(v), next(nullptr) {}
};

template <typename T>
class LinkedList {
public:
    LinkedList() : head_(nullptr), tail_(nullptr), size_(0) {}

    ~LinkedList() { clear(); }

    // Copy constructor: deep copy
    LinkedList(const LinkedList& other)
        : head_(nullptr), tail_(nullptr), size_(0) {
        for (Node<T>* cur = other.head_; cur != nullptr; cur = cur->next) {
            push_back(cur->nilai);
        }
    }

    // Copy assignment: copy-and-swap
    LinkedList& operator=(LinkedList other) {
        swap(other);
        return *this;
    }

    // Move constructor
    LinkedList(LinkedList&& other) noexcept
        : head_(other.head_), tail_(other.tail_), size_(other.size_) {
        other.head_ = other.tail_ = nullptr;
        other.size_ = 0;
    }

    void swap(LinkedList& other) noexcept {
        std::swap(head_, other.head_);
        std::swap(tail_, other.tail_);
        std::swap(size_, other.size_);
    }

    void push_back(const T& v) {
        Node<T>* n = new Node<T>(v);
        if (tail_ == nullptr) head_ = tail_ = n;
        else { tail_->next = n; tail_ = n; }
        ++size_;
    }

    void clear() {
        Node<T>* cur = head_;
        while (cur != nullptr) {
            Node<T>* nx = cur->next;
            delete cur;
            cur = nx;
        }
        head_ = tail_ = nullptr;
        size_ = 0;
    }

    // Iterator basic
    class Iterator {
    public:
        Iterator(Node<T>* p) : ptr_(p) {}
        T& operator*() const { return ptr_->nilai; }
        Iterator& operator++() { ptr_ = ptr_->next; return *this; }
        bool operator!=(const Iterator& o) const { return ptr_ != o.ptr_; }
    private:
        Node<T>* ptr_;
    };

    Iterator begin() const { return Iterator(head_); }
    Iterator end()   const { return Iterator(nullptr); }

    std::size_t size() const { return size_; }

private:
    Node<T>* head_;
    Node<T>* tail_;
    std::size_t size_;
};

int main() {
    LinkedList<int> a;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);

    // Range-for memakai Iterator
    std::cout << "a: ";
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';

    // Copy constructor — deep copy
    LinkedList<int> b = a;
    std::cout << "b (copy): ";
    for (int x : b) std::cout << x << ' ';
    std::cout << '\n';

    // Modifikasi b, a tidak terpengaruh
    b.push_back(99);
    std::cout << "b setelah push 99: ";
    for (int x : b) std::cout << x << ' ';
    std::cout << '\n';
    std::cout << "a (tetap): ";
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';

    // Move constructor
    LinkedList<int> c = std::move(b);
    std::cout << "c (move dari b): ";
    for (int x : c) std::cout << x << ' ';
    std::cout << '\n';
    std::cout << "b setelah move, size=" << b.size() << '\n';

    // Copy assignment via copy-and-swap
    LinkedList<int> d;
    d.push_back(7);
    d = a;  // deep copy a ke d
    std::cout << "d setelah assignment: ";
    for (int x : d) std::cout << x << ' ';
    std::cout << '\n';

    return 0;
}

Output yang Dihasilkan:

a: 1 2 3 
b (copy): 1 2 3 
b setelah push 99: 1 2 3 99 
a (tetap): 1 2 3 
c (move dari b): 1 2 3 99 
b setelah move, size=0
d setelah assignment: 1 2 3 

1. Baris LinkedList(const LinkedList& other): copy constructor. Traverse other.head_ dan panggil push_back untuk setiap nilai. Setiap node dialokasikan baru — deep copy.
2. Baris LinkedList& operator=(LinkedList other): idiom copy-and-swap. other adalah parameter by-value — compiler memanggil copy/move constructor untuk membuat other. Setelah swap, list this berisi data baru, other berisi data lama.
3. Baris LinkedList(LinkedList&& other) noexcept: move constructor. Curi head_, tail_, size_ dari other, lalu set other ke keadaan kosong. noexcept penting agar container STL memilih move.
4. Baris void swap(LinkedList& other) noexcept: menukar tiga pointer dengan std::swap. O(1) tanpa alokasi.
5. Baris class Iterator: nested class yang membungkus Node<T>*. Operator *, ++, != membuatnya kompatibel dengan range-for.
6. Hasil modifikasi b: b punya 99 tambahan, a tetap [1,2,3] — deep copy bekerja, tidak ada sharing.
7. Hasil std::move(b): pointer head_/tail_/size_ berpindah ke c. b jadi kosong (size=0) tanpa alokasi/dealokasi — inilah efisiensi move semantics.
8. d = a: copy assignment memanggil copy constructor untuk membuat other (by-value), swap, lalu destructor other membebaskan [7] lama.

Rule of Five #

Dalam C++ modern, bila class mengelola resource (pointer ke node), lima special member function harus didefinisikan secara konsisten:

1. Destructor
2. Copy constructor
3. Copy assignment
4. Move constructor
5. Move assignment

Bila salah satu didefinisikan, biasanya semua harus didefinisikan — aturan ini disebut Rule of Five (perluasan Rule of Three pra-C++11).

Kapan Pakai Iterator Sendiri vs STL #

Ringkasan #

• Empat pilar class modern C++: destructor (RAII), copy constructor (deep copy), move constructor (transfer), iterator (range-for).
• Copy-and-swap idiom menyatukan self-assignment safety, cleanup, dan exception safety dalam satu operator=.
• Iterator adalah wrapper pointer dengan operator*, ++, != — memungkinkan range-for dan (dengan kategori lebih tinggi) <algorithm>.
• Rule of Five: bila salah satu special member didefinisikan manual, biasanya semua harus didefinisikan.
• Untuk produksi, pertimbangkan std::list atau std::forward_list daripada roll-your-own.