Linked List

How It Works

A linked list stores elements as separate nodes scattered anywhere in memory, where each node holds a value and a pointer (reference) to the next node. There's no contiguous block and no index arithmetic: to get to the fifth element, you have to walk the chain from the head, one next pointer at a time. That's the fundamental trade-off versus an array: you give up O(1) random access in exchange for O(1) insertion and deletion once you already have a reference to the node.

Core operations and their complexity:

• Access by position (get(i)): O(n). You must traverse from the head.
• Search by value: O(n). Same traversal requirement.
• Insert/delete at the head: O(1). Just repoint the head pointer.
• Insert/delete at the tail: O(1) if you maintain a tail pointer, otherwise O(n) to find it.
• Insert/delete in the middle: O(1) for the pointer rewiring itself, but O(n) to reach that node first.

A singly linked list only points forward (next); a doubly linked list also stores prev, which makes backward traversal and tail deletion cheap at the cost of extra memory per node. Linked lists shine when you need frequent insertions/deletions at the ends or middle without shifting everything else, the exact weakness of arrays.

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

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

  // O(1): append at the tail
  push(value) {
    const node = new ListNode(value);
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
    return this;
  }

  // O(1): insert at the head
  unshift(value) {
    const node = new ListNode(value);
    node.next = this.head;
    this.head = node;
    if (!this.tail) this.tail = node;
    this.size++;
    return this;
  }

  // O(n): must traverse to find the value
  find(value) {
    let current = this.head;
    while (current) {
      if (current.value === value) return current;
      current = current.next;
    }
    return null;
  }

  // Classic interview pattern: reverse a singly linked list, O(n) time, O(1) space
  reverse() {
    let prev = null;
    let current = this.head;
    this.tail = current;
    while (current) {
      const next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }
    this.head = prev;
    return this;
  }
}

Common Mistakes

• Losing the head reference: reassigning a traversal pointer instead of a separate variable, then losing the only way back to the start of the list.
• Forgetting to update the tail pointer: after appends, reversals, or deletions, an unmaintained tail silently breaks future O(1) appends.
• Off-by-one traversal: checking current.next vs current inconsistently, causing either an extra step or an early stop (especially when deleting a node, where you need the previous node, not the node itself).
• Not handling the empty-list or single-node edge cases: reversal and deletion logic that assumes at least two nodes will throw or silently corrupt state on head === null or head === tail.
• Creating accidental cycles: during in-place reversal or node removal, forgetting to null out a stale next pointer can leave a node pointing back into the list, causing infinite loops later.

Pattern Summary

Reach for a linked list when the problem involves frequent insertion or deletion at arbitrary positions without needing random access: LRU caches, merge-k-lists, and in-place reversal problems all lean on pointer manipulation rather than index math. The edge it gives you in interviews is O(1) structural changes and a clean mental model for two-pointer techniques like fast/slow (cycle detection) and dummy-head tricks that simplify edge cases.