Linked List adalah kumpulan node yang terhubung melalui pointer. Setiap node menyimpan data dan referensi ke node berikutnya.

Perbedaan dengan Array:

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

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

  // Sisip di awal — O(1)
  prepend(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    this.size++;
  }

  // Sisip di akhir — O(n)
  append(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }

  // Hapus di awal — O(1)
  removeFirst() {
    if (!this.head) return undefined;
    const value = this.head.value;
    this.head = this.head.next;
    this.size--;
    return value;
  }

  // Cetak semua — O(n)
  print() {
    let current = this.head;
    const result = [];
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    return result.join(" → ");
  }
}

const list = new LinkedList();
list.append(10);
list.append(20);
list.prepend(5);
list.print(); // "5 → 10 → 20"

Kapan pakai Linked List?

• Sering menambah/menghapus di awal/tengah
• Ukuran data berubah-ubah drastis
• Implementasi Stack dan Queue yang efisien

🎭 Analogi sehari-hari: Lomba estafet sambung tongkat. Pelari 1 tahu pelari 2 di mana, pelari 2 tahu pelari 3, dst. Mau cari pelari ke-7? Harus mulai dari pelari 1, ikutin tongkat satu per satu (O(n)). Tapi mau sisip pelari baru di tengah? Cukup ubah arah tongkat 2 orang — gak perlu semua geser kayak array.

💡 Trade-off cache locality: Array berurutan di memori = CPU cache friendly = beneran lebih cepat dari Big O. Linked List node tersebar di RAM = setiap akses mungkin cache miss. Praktiknya, Array suka menang walau Big O sama, kecuali beneran sering insert/delete di tengah.

⚠️ Jebakan umum:

• Lupa current = current.next di loop = infinite loop
• Lupa update tail saat append/remove last = bug pelan
• Hapus tanpa prev reference = harus traverse dari head untuk cari node sebelumnya = O(n)
• Memory leak: node yang dihapus tapi masih di-reference dari luar = GC tidak bisa bersihkan

🎯 Array vs Linked List:

• Akses random by index → Array (O(1))
• Insert/delete di awal sering → Linked List (O(1))
• Memory limited → Array (compact, no pointer overhead)
• Size sangat berubah-ubah → Linked List (no resize cost)

🧪 Tebakan cepat: Append 1jt elemen ke linked list dengan append() di contoh — Big O total? Setiap append traverse dari head = O(n). Total = O(n²). Solusinya: simpan reference tail supaya append O(1).

TL;DR: Linked List = node terhubung lewat pointer. Sisip/hapus di awal O(1), akses by index O(n). Pakai jika butuh insert/delete fleksibel, hindari kalau butuh random access.