Doubly Linked List adalah linked list di mana setiap node punya pointer ke node sebelumnya dan node berikutnya.

Keunggulan vs Singly Linked List:

• Bisa traversal dua arah (maju dan mundur)
• Hapus node tertentu jadi O(1) jika punya referensi langsung
• Tapi butuh lebih banyak memori (pointer tambahan)

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;
  }

  // Tambah di akhir — O(1)
  append(value) {
    const node = new DNode(value);
    if (!this.tail) {
      this.head = node;
      this.tail = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
  }

  // Hapus node tertentu — O(1) jika punya referensi
  remove(node) {
    if (node.prev) node.prev.next = node.next;
    else this.head = node.next;

    if (node.next) node.next.prev = node.prev;
    else this.tail = node.prev;

    this.size--;
    return node.value;
  }

  // Cetak maju
  printForward() {
    let current = this.head;
    const result = [];
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    return result.join(" ⇄ ");
  }
}

Kegunaan nyata:

• LRU Cache — cache yang menghapus item paling lama tidak dipakai
• Text editor — navigasi kursor maju/mundur
• Playlist musik — lagu sebelumnya/berikutnya
• Browser tab management — pindah tab kiri/kanan

🎭 Analogi sehari-hari: Rangkaian KRL. Tiap gerbong tau gerbong sebelumnya DAN sesudahnya. Penumpang mau pindah ke gerbong sebelumnya = langsung. Mau lepas gerbong di tengah? Tinggal sambungin gerbong sebelum & sesudahnya — gak perlu rombak semua.

💡 Kenapa LRU Cache butuh Doubly Linked List?

• Set jadi "paling baru" = pindah node ke head = butuh prev untuk lepas dari posisi lama (O(1))
• Hapus "paling lama" = tail (langsung)
• Singly linked list butuh O(n) untuk lepas node tengah → LRU jadi O(n) per get → percuma

⚠️ Jebakan umum:

• Lupa update kedua pointer saat insert/remove (prev DAN next) = list rusak
• Edge case head & tail null = gampang lupa, bug muncul saat list cuma 1 elemen
• 2x memory overhead dibanding singly — gak gratis. Pakai cuma kalau butuh traversal dua arah

🎯 Singly vs Doubly:

• Cuma traverse maju → Singly (hemat memori)
• Butuh traverse maju & mundur → Doubly
• Butuh hapus node tertentu O(1) dengan reference → Doubly
• LRU Cache, undo/redo dengan navigasi → Doubly

TL;DR: Doubly Linked List = node tau prev & next. 2x memori, tapi remove node tertentu jadi O(1). Inti pondasi LRU Cache dan navigasi dua arah.