Stack, Queue & Linked List

Kenapa ini penting

Stack, queue, dan linked list adalah struktur data "klasik" yang sering muncul di phone screen karena soalnya pendek tapi menguji ketelitian: manipulasi pointer, kasus kosong, dan urutan operasi. Kamu juga memakainya setiap hari tanpa sadar. Call stack JavaScript adalah stack; event loop memakai antrean (task queue dan microtask queue); tombol Back di browser adalah stack history; React menyimpan hooks per komponen dalam urutan pemanggilan, dan itulah kenapa aturan "jangan panggil hook di dalam kondisi" ada.

Analogi: stack seperti tumpukan piring, yang terakhir ditaruh diambil pertama (LIFO, last in first out). Queue seperti antrean kasir minimarket, yang datang pertama dilayani pertama (FIFO, first in first out). Linked list seperti rangkaian gerbong kereta: tiap gerbong hanya tahu gerbong berikutnya, jadi untuk ke gerbong ke-10 kamu harus berjalan dari gerbong pertama.

Konsep inti

Stack di JavaScript

Array JS sudah cukup sebagai stack: push untuk menaruh, pop untuk mengambil, at(-1) untuk mengintip puncak, semuanya O(1). Gunakan stack saat soal punya pola "pasangan terdekat" atau "yang terakhir dibuka harus ditutup dulu": tanda kurung, undo, evaluasi ekspresi, DFS iteratif. Varian penting: monotonic stack, stack yang isinya dijaga selalu naik atau turun, untuk soal "elemen lebih besar berikutnya" (daily temperatures, next greater element).

Queue di JavaScript

JS tidak punya queue bawaan. arr.shift() itu O(n), jadi untuk BFS dengan ribuan node, ia bisa diam-diam membuat solusimu O(n²). Dua cara aman:

1. Simpan indeks head dan baca queue[head++] (lihat contoh kode).
2. Untuk BFS, iterasi for (let i = 0; i < queue.length; i++) sambil terus push.

Di interview, shift() untuk input kecil biasanya masih diterima, asal kamu menyebutkan bahwa itu O(n) dan bagaimana memperbaikinya. Kalimatnya: "I'm using shift for readability, but in production I'd use a head index or a deque since shift is O(n) in JavaScript."

Linked list

Node berisi val dan next. Operasi kuncinya:

Tiga teknik yang hampir selalu dipakai:

• Dummy node: node palsu sebelum head, supaya kasus "head berubah" tidak perlu kode khusus.
• Simpan next sebelum memutus: saat membalik list, kalau kamu langsung menimpa curr.next, sisa list hilang.
• Fast & slow pointer (Floyd's tortoise and hare): untuk deteksi siklus dan mencari tengah. Kalau ada siklus, pointer cepat pasti menyusul pointer lambat di dalam siklus, seperti pelari cepat yang menyusul pelari lambat di lintasan lari melingkar.

Gambarkan pointer saat interview. Di editor kode bersama, tulis komentar seperti // prev <- curr next -> ... sambil berbicara. Tech Interview Handbook juga menyarankan menggambar (visualize the problem) untuk soal linked list, tree, dan graph.

Contoh percakapan interview: reverse linked list

Interviewer: "Reverse a singly linked list."

Candidate: "Can the list be empty, and should I do it in place?"

Interviewer: "It can be empty, and yes, in place please."

Candidate: "I'll use three pointers: prev, curr, and next. At each step I save curr.next, point curr back to prev, then move prev and curr forward one node. When curr becomes null, prev is the new head. That's O(n) time and O(1) extra space. Let me draw it quickly: null ← 1, 2 → 3 → null, with prev on 1 and curr on 2..."

Interviewer: "Could you do it recursively?"

Candidate: "Yes. Reverse the rest of the list, then make head.next.next point back to head and set head.next to null. It's still O(n) time, but O(n) space because of the call stack, so for a very long list I'd prefer the iterative version."

Perhatikan pola jawabannya: klarifikasi dulu (kosong? in place?), rencana dalam satu kalimat, kompleksitas, lalu gambar. Saat ditanya versi alternatif, kandidat tidak hanya menjawab "bisa", tapi langsung menyebut trade-off ruang dari call stack. Itu sinyal yang dicari interviewer: kamu tahu kapan memakai tiap pendekatan, bukan hanya cara menulisnya.

Contoh kode

// Valid Parentheses dengan stack
function isValid(s) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of s) {
    if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;   // penutup harus cocok dengan pembuka terakhir
    } else stack.push(ch);
  }
  return stack.length === 0;                         // sisa pembuka = tidak valid
}
console.log(JSON.stringify(['()', '()[]{}', '(]', '([)]', '{[]}', '((', ''].map(isValid)));
// → [true,true,false,false,true,false,true]

// Queue yang benar-benar O(1): pakai indeks head, bukan shift()
class Queue {
  #items = []; #head = 0;
  enqueue(x) { this.#items.push(x); }
  dequeue() {
    if (this.#head >= this.#items.length) return undefined;
    const x = this.#items[this.#head++];
    if (this.#head > 1024 && this.#head * 2 > this.#items.length) {   // buang sisa sesekali
      this.#items = this.#items.slice(this.#head); this.#head = 0;
    }
    return x;
  }
  get size() { return this.#items.length - this.#head; }
}
const q = new Queue(); q.enqueue('a'); q.enqueue('b'); q.enqueue('c');
console.log(q.dequeue(), q.dequeue(), q.size, q.dequeue(), q.dequeue());
// → a b 1 c undefined

// Linked list
class ListNode { constructor(val, next = null) { this.val = val; this.next = next; } }
const fromArray = arr => arr.reduceRight((next, val) => new ListNode(val, next), null);
const toArray = head => { const out = []; while (head) { out.push(head.val); head = head.next; } return out; };

function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;   // simpan dulu sebelum diputus
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}
console.log(toArray(reverseList(fromArray([1, 2, 3, 4, 5]))), toArray(reverseList(fromArray([1]))), toArray(reverseList(null)));
// → [ 5, 4, 3, 2, 1 ] [ 1 ] []

// Deteksi siklus: Floyd (tortoise & hare), O(n) waktu, O(1) ruang
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next; fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}
const cyc = fromArray([3, 2, 0, -4]); cyc.next.next.next.next = cyc.next;  // -4 menunjuk balik ke 2
console.log(hasCycle(cyc), hasCycle(fromArray([1, 2])), hasCycle(null));
// → true false false

// Merge two sorted lists dengan dummy node
function mergeTwoLists(a, b) {
  const dummy = new ListNode(0); let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a ?? b;          // sambungkan sisa yang belum habis
  return dummy.next;
}
console.log(toArray(mergeTwoLists(fromArray([1, 2, 4]), fromArray([1, 3, 4]))), toArray(mergeTwoLists(null, fromArray([0]))));
// → [ 1, 1, 2, 3, 4, 4 ] [ 0 ]

Fungsi bantu fromArray dan toArray bukan bagian soal, tapi sangat berguna. Di interview kamu boleh bilang: "Let me write two small helpers so I can test this quickly." Itu menunjukkan kebiasaan testing yang baik.

Kesalahan umum

1. Lupa mengecek stack kosong. Untuk input ')', stack.pop() menghasilkan undefined; kode di atas aman karena undefined !== '(', tapi di bahasa lain atau logika lain bisa error. Sebutkan kasus ini saat testing.
2. Lupa mengecek sisa stack di akhir. '((' tidak punya penutup yang salah, tapi tetap tidak valid.
3. Kehilangan sisa list saat membalik. Cara benar: const next = curr.next sebelum curr.next = prev.
4. while (fast.next) tanpa cek fast. Akan error di list panjang genap. Cara benar: while (fast && fast.next).
5. Memakai shift() di BFS besar tanpa menyebut biayanya. Cara benar: indeks head, atau sebutkan trade-off-nya.

Latihan

1. Mudah, Buat MinStack dengan push, pop, top, dan getMin, semuanya O(1).
2. Sedang, Cari node tengah linked list. Untuk panjang genap, kembalikan tengah kedua.
3. Menantang, dailyTemperatures(t): untuk tiap hari, berapa hari lagi sampai suhu lebih hangat (0 kalau tidak ada). Target O(n) dengan monotonic stack.

// 1. Stack kedua menyimpan minimum sampai titik itu
class MinStack {
  #s = []; #mins = [];
  push(x) { this.#s.push(x); this.#mins.push(this.#mins.length ? Math.min(x, this.#mins.at(-1)) : x); }
  pop() { this.#mins.pop(); return this.#s.pop(); }
  top() { return this.#s.at(-1); }
  getMin() { return this.#mins.at(-1); }
}
const ms = new MinStack(); ms.push(-2); ms.push(0); ms.push(-3);
const m1 = ms.getMin(); ms.pop();
console.log(m1, ms.top(), ms.getMin());
// → -3 0 -2

// 2. Fast & slow: saat fast sampai ujung, slow ada di tengah
function middleNode(head) { let s = head, f = head; while (f && f.next) { s = s.next; f = f.next.next; } return s; }
console.log(middleNode(fromArray([1, 2, 3, 4, 5])).val, middleNode(fromArray([1, 2, 3, 4, 5, 6])).val);
// → 3 4

// 3. Stack berisi indeks hari yang belum menemukan hari lebih hangat (suhu menurun dari bawah ke atas)
function dailyTemperatures(t) {
  const ans = new Array(t.length).fill(0), stack = [];
  for (let i = 0; i < t.length; i++) {
    while (stack.length && t[i] > t[stack.at(-1)]) { const j = stack.pop(); ans[j] = i - j; }
    stack.push(i);
  }
  return ans;
}
console.log(JSON.stringify([dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]), dailyTemperatures([30, 60, 90]), dailyTemperatures([90, 60])]));
// → [[1,1,4,2,1,1,0,0],[1,1,0],[0,0]]

Ringkasan

• Stack (LIFO) untuk pasangan terdekat, undo, DFS iteratif; monotonic stack untuk "elemen lebih besar berikutnya".
• shift() di JS itu O(n); gunakan indeks head untuk queue yang efisien atau sebutkan trade-off-nya.
• Linked list: dummy node, simpan next sebelum memutus, dan fast/slow pointer.
• Floyd's cycle detection: O(n) waktu, O(1) ruang.
• Tulis helper fromArray/toArray agar bisa menguji soal linked list dengan cepat.