Linked List

Explanation

Each node in a linked list is an object with two fields: data (the stored value) and next (a reference to the next node). The list itself only stores a reference to the head node; everything else is reached by following pointers. The last node's next pointer is null, signaling the end. This design gives linked lists a fundamentally different performance profile than arrays. Insertions and deletions are O(1) if you have a reference to the node before the insertion/deletion point — you just reroute pointers without moving any other elements. This is linked lists' superpower. But access by index is O(n) because you must traverse from head to find the nth node — there's no arithmetic shortcut like with arrays. There are three main variants: singly linked (each node has only next), doubly linked (each node has both next and prev, enabling O(1) backward traversal and tail insertions), and circular (the tail's next points back to the head, useful for round-robin scheduling). In practice, directly using raw linked lists in JavaScript is rare — but they underpin stacks, queues, and hash table collision chains. The DOM itself is a tree of nodes connected by parent/child pointers, conceptually similar to a linked list. Memory-wise, linked lists have overhead: each node allocates a separate object on the heap, plus the pointer itself. For large datasets, the non-contiguous layout also hurts cache performance compared to arrays. This is why, despite O(1) insertions in theory, linked lists are often slower than arrays in practice for small-to-medium datasets.

Code Example

// Minimal singly linked list in JavaScript

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

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

  // O(1) — prepend to front
  prepend(val) {
    this.head = new ListNode(val, this.head);
  }

  // O(n) — append to back (no tail pointer)
  append(val) {
    const node = new ListNode(val);
    if (!this.head) { this.head = node; return; }
    let curr = this.head;
    while (curr.next) curr = curr.next;
    curr.next = node;
  }

  // O(n) — traverse and collect values
  toArray() {
    const result = [];
    let curr = this.head;
    while (curr) { result.push(curr.val); curr = curr.next; }
    return result;
  }
}

const list = new LinkedList();
list.prepend(3); list.prepend(2); list.prepend(1);
console.log(list.toArray()); // [1, 2, 3]

Why It Matters for Engineers

Linked lists are the gateway to understanding pointer-based data structures — trees, graphs, and hash tables all use the same mental model of nodes connected by references. If you're fuzzy on how a linked list works, you'll also be fuzzy on how a binary tree traversal works or why removing a node from a DOM tree is O(1) given the right reference. Interview problems involving linked lists (reversing a list, detecting a cycle, merging sorted lists) test your ability to manipulate references and think in terms of before/current/next — a skill that transfers directly to understanding how any pointer-based system (like a React fiber tree or a database B-tree) works under the hood.