Linked List — Struktur Data

Linked List adalah kumpulan node yang terhubung melalui pointer. Setiap node menyimpan data dan referensi ke node berikutnya. Perbedaan dengan Array: Fitur…

Linked list adalah daftar yang isinya disimpan di kotak-kotak terpisah bernama node. Tiap node menyimpan dua hal: nilainya, dan alamat node berikutnya. Mirip permainan cari harta karun: tiap kertas petunjuk memberi tahu di mana kertas berikutnya, jadi kamu harus mengikutinya satu per satu dari kertas pertama.

🧪 Tebakan cepat: list-nya 10 -> 20 -> 30. Kamu mau menambah 5 di paling depan. Berapa node yang harus digeser? Tebak dulu, jawabannya ada di bagian "prepend: tambah di depan".

Node: nilai dan alamat berikutnya

Bayangkan dulu gambarnya, baru kodenya:

head
  |
[10 | next] --> [20 | next] --> [30 | next] --> null

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

const a = new Node(10);
const b = new Node(20);
const c = new Node(30);
a.next = b;
b.next = c;

const head = a;
console.log(head.value);           // 10
console.log(head.next.value);      // 20
console.log(head.next.next.value); // 30
console.log(c.next);               // null

Class LinkedList

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

  prepend(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    this.size++;
  }

  append(value) {
    const node = new Node(value);
    if (this.head === null) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }

  print() {
    let teks = "head";
    let current = this.head;
    while (current !== null) {
      teks += " -> " + current.value;
      current = current.next;
    }
    return teks + " -> null";
  }
}

const list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.prepend(5);
console.log(list.print()); // head -> 5 -> 10 -> 20 -> 30 -> null
console.log(list.size);    // 4

List kosong punya head bernilai null dan size 0. Tiap kali node ditambah, di depan atau di belakang, size naik satu. Class Node dari bagian sebelumnya tetap dipakai.

prepend: tambah di depan

list.prepend(5) ke list 10 -> 20 -> 30:

Langkah Kode Keadaannya
1 const node = new Node(5) node 5 sendirian, next-nya null
2 node.next = this.head 5 menunjuk ke 10, list lama tergantung di belakangnya
3 this.head = node head -> 5 -> 10 -> 20 -> 30 -> null

Gak ada node yang digeser, cuma dua pointer yang diubah. Itu jawaban tebakan tadi: nol. Jadi prepend selalu satu langkah, sepanjang apa pun list-nya. Itu yang disebut O(1).

Urutan langkah 2 dan 3 penting. Kalau head diganti duluan, alamat node 10 hilang dan sisa list-nya ikut hilang.

append: tambah di belakang

List cuma tahu head, jadi buat menambah di belakang, kita jalan dulu sampai node terakhir. list.append(40) ke list 10 -> 20 -> 30:

Langkah current di current.next Lalu
1 10 20 belum null, maju
2 20 30 belum null, maju
3 30 null berhenti, current.next = node

Hasilnya 10 -> 20 -> 30 -> 40 -> null. Kalau list-nya masih kosong, node baru langsung jadi head. Makin panjang list, makin jauh jalannya: list dua kali lebih panjang, jalannya kira-kira dua kali lebih lama. Itu O(n), dengan n jumlah node.

Berjalan dari head sampai null

Semua yang perlu membaca seluruh list memakai pola yang sama, seperti print() di atas:

Mau semua nilai dalam array? Polanya sama, cuma isinya diganti: siapkan [], lalu push(current.value) tiap putaran, dan kembalikan array-nya sesudah loop.

Linked list atau array?

Array Linked list
Ambil isi ke-i langsung, O(1) jalan dari head, O(n)
Tambah di depan semua isi digeser, O(n) ubah dua pointer, O(1)
Tambah di belakang O(1) O(n), kecuali punya tail

Keunggulan utama linked list: menambah dan menghapus di depan cuma mengubah pointer, tanpa menggeser isi lain. Kelemahannya: gak bisa langsung loncat ke isi ke-i.

⚠️ Jebakan yang sering ketemu

💡 Pointer tail. Kalau list juga menyimpan tail, alamat node terakhir, append gak perlu jalan lagi: langsung this.tail.next = node, lalu this.tail = node. Append jadi O(1). Tapi menghapus node terakhir tetap harus jalan dari head, karena next cuma mengarah ke depan.

TL;DR: Linked list adalah rangkaian node. Tiap node menyimpan value dan next, alamat node berikutnya, dan node terakhir next-nya null. head menunjuk node pertama. prepend bikin node baru, node.next = this.head, lalu this.head = node: O(1), tanpa menggeser apa pun. append jalan dari head sampai node yang next-nya null, lalu menyambung di situ: O(n). Membaca seluruh list: current mulai dari head, maju lewat current.next sampai null. Jangan lupa size++ di tiap penambahan.

Yang akan kamu pelajari