Doubly Linked List — Struktur Data

Doubly Linked List adalah linked list di mana setiap node punya pointer ke node sebelumnya dan node berikutnya. Keunggulan vs Singly Linked List: Bisa…

Doubly linked list adalah linked list yang tiap node-nya punya dua pointer: next ke node sesudahnya, dan prev ke node sebelumnya. List-nya juga menyimpan dua ujung: head (node pertama) dan tail (node terakhir). Mirip rangkaian gerbong kereta: tiap gerbong tersambung ke gerbong depan dan belakangnya, jadi kamu bisa jalan ke dua arah.

🧪 Tebakan cepat: di linked list biasa, menghapus node terakhir harus jalan dari head. Di doubly linked list, berapa node yang harus dilewati? Tebak dulu, jawabannya ada di bagian "Hapus di belakang".

Node dengan prev dan next

Gambarnya dulu:

        head                        tail
         |                           |
null <- [A] <-------> [B] <-------> [C] -> null

class DNode {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  append(value) {
    const node = new DNode(value);
    if (this.tail === null) {
      this.head = node;
      this.tail = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
  }
}

const list = new DoublyLinkedList();
list.append("A");
list.append("B");
list.append("C");

console.log(list.head.value);      // A
console.log(list.tail.value);      // C
console.log(list.head.next.value); // B
console.log(list.tail.prev.value); // B
console.log(list.size);            // 3

list.append("C") ke list A <-> B, langkah demi langkah:

Langkah Kode Yang berubah
1 const node = new DNode("C") C sendirian
2 node.prev = this.tail C menunjuk balik ke B
3 this.tail.next = node B menunjuk maju ke C
4 this.tail = node tail sekarang C

Tiap sambungan baru berarti dua pointer: satu maju, satu mundur. Jumlah langkahnya selalu sama, sepanjang apa pun list-nya, jadi append di sini O(1).

prepend: cerminan append

Menambah di depan memakai langkah yang sama, dengan head di tempat tail dan arah pointer yang dibalik:

append (di belakang) prepend (di depan)
node.prev = this.tail node.next = this.head
this.tail.next = node this.head.prev = node
this.tail = node this.head = node

Aturan list kosong juga berlaku: node pertama yang masuk lewat prepend harus jadi head dan tail sekaligus. Dan this.size++ di keduanya.

Jalan maju dan jalan mundur

Maju: mulai dari head, ikuti next. Mundur: mulai dari tail, ikuti prev.

let current = list.tail;
while (current !== null) {
  console.log(current.value);
  current = current.prev;
}
// C
// B
// A

Kode ini lanjutan dari list di atas. Mau hasilnya dalam array? Siapkan [], push(current.value) tiap putaran, lalu kembalikan array-nya sesudah loop.

Hapus di belakang

Node sebelum yang terakhir ada di tail.prev, jadi removeLast cukup satu langkah: tail dipindah ke tail.prev, lalu next milik tail yang baru diisi null. Itu jawaban tebakan tadi: gak ada node yang dilewati, O(1). Menghapus node di tengah juga gampang: sambungkan node sebelum dan sesudahnya satu sama lain, karena keduanya bisa dicapai lewat prev dan next.

Singly atau doubly?

Singly linked list Doubly linked list
Pointer per node 1 (next) 2 (prev dan next)
Arah jalan cuma maju maju dan mundur
Hapus node terakhir jalan dari head, O(n) lewat tail.prev, O(1)

Harganya memori: tiap node menyimpan satu pointer tambahan. Datanya sendiri gak disimpan dua kali. Doubly linked list dipakai kalau kamu butuh bolak-balik, misalnya tombol back dan forward di browser, lagu sebelumnya dan berikutnya di playlist, atau LRU cache.

⚠️ Jebakan yang sering ketemu

TL;DR: Doubly linked list: tiap node punya prev dan next, dan list-nya menyimpan head dan tail. append: node.prev = this.tail, this.tail.next = node, this.tail = node. prepend adalah cerminannya lewat head. List kosong: node pertama jadi head sekaligus tail. Maju dari head lewat next, mundur dari tail lewat prev. Tambah dan hapus di kedua ujung O(1), harganya satu pointer tambahan di tiap node.

Yang akan kamu pelajari