Singly linked list hanya bisa berjalan maju — dari head ke tail. Operasi seperti hapus_node(pos) tetap perlu traverse O(n) untuk menemukan predecessor, meskipun pointer pos sudah diketahui. Doubly linked list menambahkan pointer prev pada setiap node, memungkinkan traversal dua arah dan penghapusan node dalam O(1) langsung dari pointer node. Trade-off-nya: setiap node membutuhkan satu pointer ekstra (8 byte pada sistem 64-bit). Pada Chapter ini kita akan membangun doubly linked list lengkap, melihat operasi hapus yang lebih elegan, dan membandingkan overhead memorinya dibanding singly.

Struktur Node Doubly #

Setiap node doubly menyimpan tiga hal: data, pointer prev ke node sebelumnya, dan pointer next ke node berikutnya. Invariant penting: bila node->next != nullptr, maka node->next->prev == node. Hubungan ini harus dijaga pada setiap operasi insert/delete.

Panah dua arah pada diagram melambangkan dua pointer — next maju, prev mundur. Pointer prev dari head dan pointer next dari tail selalu nullptr.

Operasi push_back #

Mekanisme: Sambung Dua Arah #

  1. Alokasikan node baru n.
  2. Bila list kosong: head_ = tail_ = n.
  3. Bila tidak, sambungkan dua arah:
    • n->prev = tail_ — node baru tahu predecessornya.
    • tail_->next = n — tail lama menunjuk ke node baru.
    • tail_ = n — perbarui tail.

Operasi tetap O(1) berkat tail pointer.

Operasi push_front #

Mekanisme: Sambung Dua Arah dari Head #

Mirip push_back namun dari sisi head:

  1. Alokasikan n.
  2. Bila list kosong: head_ = tail_ = n.
  3. Bila tidak:
    • n->next = head_ — node baru menunjuk ke head lama.
    • head_->prev = n — head lama tahu node baru sebagai predecessor.
    • head_ = n — perbarui head.

Operasi hapus O(1) dari Pointer Node #

Aturan #

Berbeda dengan singly linked list yang harus traverse untuk menemukan prev, doubly linked list langsung memiliki cur->prev. Jadi penghapusan node berdasarkan pointer adalah O(1).

Mekanisme: Lompati Node Saat Ini #

Bila cur adalah node yang akan dihapus:

  1. cur->prev->next = cur->next — predecessor melompati cur.
  2. cur->next->prev = cur->prev — successor melompati cur.
  3. Kasus khusus: bila cur == head_, update head_ = cur->next. Bila cur == tail_, update tail_ = cur->prev.
  4. delete cur.

Kode Lengkap Doubly Linked List #

cpp 
#include <iostream>

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

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

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

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

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

    void forward() const {
        std::cout << "maju  : ";
        Node<T>* cur = head_;
        while (cur != nullptr) {
            std::cout << cur->nilai << " ";
            cur = cur->next;
        }
        std::cout << '\n';
    }

    void backward() const {
        std::cout << "mundur: ";
        Node<T>* cur = tail_;
        while (cur != nullptr) {
            std::cout << cur->nilai << " ";
            cur = cur->prev;
        }
        std::cout << '\n';
    }

    void clear() {
        Node<T>* cur = head_;
        while (cur != nullptr) {
            Node<T>* nx = cur->next;
            delete cur;
            cur = nx;
        }
        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() {
    DoublyLinkedList<int> dl;
    dl.push_back(10);
    dl.push_back(20);
    dl.push_back(30);
    dl.push_front(5);
    dl.forward();
    dl.backward();

    std::cout << "hapus 20...\n";
    dl.hapus_nilai(20);
    dl.forward();
    dl.backward();

    std::cout << "size = " << dl.size() << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
maju  : 5 10 20 30 
mundur: 30 20 10 5 
hapus 20...
maju  : 5 10 30 
mundur: 30 10 5 
size = 3
  1. Baris Node* prev; Node* next;: dua pointer per node — inilah inti doubly. Setiap node tahu predecessor dan successor.
  2. Baris n->prev = tail_; tail_->next = n; tail_ = n; (di push_back): sambungan dua arah lengkap dalam tiga baris. Node baru tahu tail lama, tail lama tahu node baru, lalu tail diperbarui.
  3. Baris if (cur->prev != nullptr) cur->prev->next = cur->next; else head_ = cur->next; (di hapus_nilai): predecessor melompati cur. Bila cur adalah head (tidak punya predecessor), maka head langsung diganti.
  4. Baris if (cur->next != nullptr) cur->next->prev = cur->prev; else tail_ = cur->prev; (di hapus_nilai): successor melompati cur. Bila cur adalah tail, tail mundur ke predecessor.
  5. Method backward(): traverse dari tail_ mengikuti pointer prev. Inilah keunggulan utama doubly — operasi terbalik sama mudahnya dengan forward.
  6. Setelah hapus 20: node 20 dihapus dan chain disambung ulang — 10->next = 30 dan 30->prev = 10. Traversal forward dan backward keduanya konsisten.

Perbandingan Singly vs Doubly #

AspekSinglyDoubly
Pointer per node1 (next)2 (prev, next)
Traverse mundurTidak didukungO(n) langsung
Hapus dari pointerO(n) — cari prevO(1) — cur->prev ada
Memori per int node12 byte (4+8, padding)20 byte (4+8+8, padding)
Use case umumStack, queue sederhanaLRU cache, browser history, deque

Trade-off: Mengapa Doubly Worth It #

Pertimbangan memilih doubly:

  1. Bila perlu hapus node dengan pointer O(1) — mis. LRU cache yang menyimpan iterator ke node. Doubly menghemat traverse O(n).
  2. Bila perlu traverse mundur — mis. undo/redo, navigasi playlist, algoritma yang memindai dua arah.
  3. Bila tipe data besar — overhead 8 byte per node relatif kecil dibanding 100+ byte data.

Pilih singly bila:

  1. Memori ketat — jutaan elemen kecil, overhead pointer mendominasi.
  2. Operasi dominan push/pop satu arah — stack dan queue sederhana tidak butuh prev.

Ringkasan #

  • Doubly linked list menambah pointer prev per node — memungkinkan traversal dua arah.
  • push_front, push_back, dan hapus (dengan pointer node) semuanya O(1).
  • Trade-off: 8 byte pointer ekstra per node; invariant node->next->prev == node harus dijaga.
  • Untuk tipe kecil (mis. int), overhead relatif besar; untuk tipe besar, overhead relatif kecil.
  • Chapter berikutnya akan membahas circular linked list — varian yang tail menunjuk ke head untuk struktur ring.