Singly Linked List

Singly linked list adalah bentuk paling sederhana dari linked list: setiap node memuat data dan satu pointer next yang menunjuk ke node berikutnya. Struktur ini cukup untuk operasi dasar — insert di depan/belakang, hapus berdasarkan nilai, dan traverse dari head ke tail. Pada Chapter ini kita akan membangun singly linked list lengkap menggunakan template C++, dengan penanganan head dan tail agar push_back tetap O(1). Setiap operasi akan kita bedah baris-per-baris agar mekanisme pointer terlihat jelas.

Struktur Node dan Class #

Node adalah blok dasar linked list. Kita gunakan template <typename T> agar node bisa menampung tipe data apa pun — int, std::string, atau tipe user-defined.

Mekanisme: Node sebagai Pasangan Data dan Pointer #

Saat kita menulis Node<int> n(42), compiler memesan blok memori yang cukup untuk int (4 byte) plus pointer (8 byte pada sistem 64-bit). Constructor mengisi nilai dengan 42 dan berikutnya dengan nullptr — artinya node ini belum terhubung ke node lain.

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

Class SinglyLinkedList menyimpan tiga member privat:

• head_ — pointer ke node pertama; nullptr bila list kosong.
• tail_ — pointer ke node terakhir; memungkinkan push_back O(1).
• size_ — jumlah node; menghindari traverse hanya untuk menghitung ukuran.

Operasi push_front: Sisip di Depala #

Aturan #

Tambah node baru di posisi paling depan sehingga node baru menjadi head. Kompleksitas O(1) — tidak ada traverse.

Mekanisme: Sambung Baru ke Head Lama #

1. Alokasikan node baru n.
2. Set n->berikutnya = head_ — node baru menunjuk ke head lama.
3. Set head_ = n — head sekarang menunjuk ke node baru.
4. Bila list sebelumnya kosong (tail_ == nullptr), maka tail juga harus di-update ke node baru tersebut.

Operasi push_back: Sisip di Belakang #

Mekanisme: Pakai Tail Pointer #

Bila kita hanya punya head, push_back memerlukan traverse O(n) untuk mencari node terakhir. Dengan tail_, kita langsung sambungkan ke node terakhir dalam O(1).

1. Alokasikan node baru n.
2. Bila list kosong: head_ = tail_ = n.
3. Bila tidak: tail_->berikutnya = n, lalu tail_ = n.

Operasi insert_after: Sisip Setelah Node Tertentu #

Mekanisme: Sambung Dua Arah #

1. Alokasikan n.
2. n->berikutnya = pos->berikutnya — node baru menunjuk ke node setelah posisi.
3. pos->berikutnya = n — posisi sekarang menunjuk ke node baru.
4. Bila pos == tail_, update tail_ = n.

Operasi hapus_nilai: Hapus Node Berdasarkan Nilai #

Mekanisme: Simpan Pointer Sebelumnya #

Karena singly linked list tidak punya pointer prev, kita harus menjaga pointer prev selama traverse agar dapat menyambung ulang node sebelumnya.

1. Iterasi cur = head_, prev = nullptr.
2. Bila cur->nilai == v: sambung prev->berikutnya = cur->berikutnya (atau head_ = cur->berikutnya bila prev == nullptr), lalu delete cur.
3. Update tail_ bila node yang dihapus adalah tail.

Kode Lengkap Singly Linked List #

#include <iostream>

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

template <typename T>
class SinglyLinkedList {
public:
    SinglyLinkedList() : head_(nullptr), tail_(nullptr), size_(0) {}
    ~SinglyLinkedList() { clear(); }

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

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

    void insert_after(Node<T>* pos, const T& v) {
        if (pos == nullptr) { push_front(v); return; }
        Node<T>* n = new Node<T>(v);
        n->berikutnya = pos->berikutnya;
        pos->berikutnya = n;
        if (pos == tail_) tail_ = n;
        ++size_;
    }

    bool hapus_nilai(const T& v) {
        Node<T>* cur = head_;
        Node<T>* prev = nullptr;
        while (cur != nullptr) {
            if (cur->nilai == v) {
                if (prev == nullptr) head_ = cur->berikutnya;
                else prev->berikutnya = cur->berikutnya;
                if (cur == tail_) tail_ = prev;
                delete cur;
                --size_;
                return true;
            }
            prev = cur;
            cur = cur->berikutnya;
        }
        return false;
    }

    void traverse() const {
        Node<T>* cur = head_;
        std::cout << "[";
        while (cur != nullptr) {
            std::cout << cur->nilai;
            if (cur->berikutnya != nullptr) std::cout << " -> ";
            cur = cur->berikutnya;
        }
        std::cout << "] (size=" << size_ << ")\n";
    }

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

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

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

int main() {
    SinglyLinkedList<int> list;
    list.push_back(10);
    list.push_back(20);
    list.push_back(30);
    list.traverse();

    list.push_front(5);
    list.traverse();

    list.hapus_nilai(20);
    list.traverse();

    list.hapus_nilai(99);
    std::cout << "hapus 99? " << (list.hapus_nilai(99) ? "ya" : "tidak") << "\n";
    list.traverse();

    return 0;
}

Output yang Dihasilkan:

[10 -> 20 -> 30] (size=3)
[5 -> 10 -> 20 -> 30] (size=4)
[5 -> 10 -> 30] (size=3)
hapus 99? tidak
[5 -> 10 -> 30] (size=3)

1. Baris template <typename T> struct Node: struct generik. T bisa int, std::string, atau tipe user-defined. Setiap instance Node<T> adalah tipe berbeda — Node<int> dan Node<double> tidak dapat dipertukarkan.
2. Baris Node(const T& v) : nilai(v), berikutnya(nullptr) {}: constructor menerima konstanta reference agar tidak terjadi copy mahal bila T berukuran besar (mis. std::string). Member initializer list langsung mengisi nilai dan berikutnya.
3. Baris n->berikutnya = head_; head_ = n; (di push_front): urutan krusial. Kita sambungkan dulu node baru ke head lama, baru kemudian head diperbarui. Bila urutan dibalik, kita kehilangan referensi ke list lama.
4. Baris if (tail_ == nullptr) tail_ = n; (di push_front): kasus list kosong — node baru sekaligus menjadi head dan tail.
5. Baris tail_->berikutnya = n; tail_ = n; (di push_back): tail lama menunjuk ke node baru, lalu tail diperbarui. Tetap O(1).
6. Baris n->berikutnya = pos->berikutnya; pos->berikutnya = n; (di insert_after): urutan penting. Node baru harus dulu menunjuk ke node setelah posisi, baru posisi menunjuk ke node baru — kalau tidak, kita memutus rantai.
7. Baris prev->berikutnya = cur->berikutnya; (di hapus_nilai): simpul sebelum cur dilompati ke simpul setelah cur. Inilah inti operasi hapus pada linked list — sambung ulang, baru delete.
8. Baris if (cur == tail_) tail_ = prev; (di hapus_nilai): bila node yang dihapus adalah tail, tail munduk ke prev. Bila prev == nullptr, list jadi kosong — tail akan di-set nullptr saat prev == nullptr kasus.
9. Method clear(): traverse dan delete setiap node. Destructor memanggil clear() agar tidak ada memory leak bila objek keluar scope.

Kompleksitas Operasi #

Iterasi dan Traverse #

Traverse linked list dilakukan dengan loop while mengikuti pointer berikutnya hingga nullptr. Pola ini berulang di banyak operasi (cari, cetak, hapus, hitung panjang):

Node<T>* cur = head_;
while (cur != nullptr) {
    // proses cur->nilai
    cur = cur->berikutnya;
}

Pola ini disebut pointer chasing — kita tidak tahu di mana node berikutnya secara fisik, kita hanya mengikuti alamat yang tersimpan di pointer.

Ringkasan #

• Singly linked list terdiri dari node dengan data + pointer berikutnya; head sebagai pintu masuk.
• Template Node<T> memungkinkan tipe data apa pun; T dipass sebagai const reference untuk efisiensi.
• push_front dan push_back keduanya O(1) berkat kehadiran pointer head dan tail.
• hapus_nilai O(n) karena traverse untuk mencari nilai; perlu menjaga pointer prev.
• Selalu delete node yang dihapus dan panggil clear() di destructor untuk mencegah memory leak.
• Chapter berikutnya akan membahas doubly linked list yang menambah pointer prev untuk traverse dua arah.