Linked Lists

Singly Linked List:
 
[head]
  ↓
[10 | •]──→[23 | •]──→[45 | •]──→[67 | •]──→ null
  node 0     node 1     node 2     node 3
 
[val | next]  ← each box is one Node object in memory

Singly:
  [val|next] → [val|next] → [val|next] → null
  (can only go forward)
 
Doubly:
  null ← [prev|val|next] ↔ [prev|val|next] ↔ [prev|val|next] → null
  (can go forward AND backward — needed for LRU cache)
 
Circular:
  [val|next] → [val|next] → [val|next]
       ↑__________________________|
  (last node points back to head — used in round-robin schedulers)

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;  // for doubly: also this.prev = null
  }
}
 
class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
 
  // Insert at head — O(1)
  prepend(val) {
    const node = new Node(val);
    node.next = this.head;
    this.head = node;
    if (!this.tail) this.tail = node; // first element
    this.size++;
  }
 
  // Insert at tail — O(1) with tail pointer
  append(val) {
    const node = new Node(val);
    if (!this.tail) {
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
  }
 
  // Delete head — O(1)
  deleteHead() {
    if (!this.head) return null;
    const val = this.head.val;
    this.head = this.head.next;
    if (!this.head) this.tail = null; // list is now empty
    this.size--;
    return val;
  }
 
  // Convert to array for debugging
  toArray() {
    const result = [];
    let curr = this.head;
    while (curr) { result.push(curr.val); curr = curr.next; }
    return result;
  }
}

List with cycle:
1 → 2 → 3 → 4 → 5
            ↑       ↓
            8 ← 7 ← 6
 
slow: 1, 2, 3, 4, 5, 6, 7, 8, 4, 5 ...
fast: 1, 3, 5, 7, 4, 6, 8, 5 ...
They meet inside the cycle → cycle detected!

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true; // same node object
  }
  return false;
}
 
// Find middle — slow stops at middle when fast reaches end
function findMiddle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow; // middle node
}

Before: null ← 1 → 2 → 3 → 4 → null
 
Step 1: prev=null, curr=1, next=2
        curr.next = prev  →  null ← 1   2 → 3 → 4
        prev=1, curr=2
 
Step 2: prev=1, curr=2, next=3
        curr.next = prev  →  null ← 1 ← 2   3 → 4
        prev=2, curr=3
 
...and so on until curr is null
After: null ← 1 ← 2 ← 3 ← 4  (prev = new head = 4)

function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next; // save next before overwriting
    curr.next = prev;       // reverse the pointer
    prev = curr;            // advance prev
    curr = next;            // advance curr
  }
  return prev; // prev is now the new head
}

function removeElements(head, val) {
  const dummy = new Node(-1);
  dummy.next = head;
  let curr = dummy;
  while (curr.next) {
    if (curr.next.val === val) curr.next = curr.next.next; // skip it
    else curr = curr.next;
  }
  return dummy.next; // real head (may have changed)
}

Remove 2nd from end: 1 → 2 → 3 → 4 → 5
 
fast = 5 (moved 2 steps ahead)
slow = 1
 
Move both: slow=2 (slow.next = 4 → skip 3 → slow.next = slow.next.next)
Fast reaches end when it's at 5, so slow is at 3 which is before the 2nd from end

function removeNthFromEnd(head, n) {
  const dummy = new Node(0);
  dummy.next = head;
  let fast = dummy, slow = dummy;
  for (let i = 0; i <= n; i++) fast = fast.next; // advance fast by n+1
  while (fast) { fast = fast.next; slow = slow.next; }
  slow.next = slow.next.next; // remove the target
  return dummy.next;
}