Linked Lists Explained

Linked lists are asked about far more often than they are used. Learn them because interviews use them to test pointer reasoning, not because your next feature needs one.

The structure

Each node holds a value and a reference to the next node. There is no index and no contiguous block - the nodes can be anywhere in memory, connected by references.

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

// 1 -> 2 -> 3 -> null
const head = new Node(1, new Node(2, new Node(3)))

function toArray(node) {
  const out = []
  while (node) {
    out.push(node.value)
    node = node.next
  }
  return out
}

console.log(toArray(head))  // [1, 2, 3]

while (node) is the traversal you will write a hundred times. It ends when next is null.

The honest comparison

• Access by index - array O(1), list O(n). The list has to walk.
• Insert or delete at the front - array O(n), list O(1).
• Insert or delete in the middle, given the node - array O(n), list O(1).
• Finding that node in the first place - O(n) either way.
• Memory - a list costs an extra reference per node, and the nodes are scattered, so it is slower to scan in practice than the Big O suggests.

That last point is why arrays win in real code more often than theory implies. Modern CPUs read contiguous memory much faster than they chase references.

Reversing, the classic

This is the question. It tests whether you can hold three references in your head at once.

function reverse(head) {
  let previous = null
  let current = head

  while (current) {
    const next = current.next   // remember where we were going
    current.next = previous     // turn the arrow around
    previous = current          // shuffle both forward
    current = next
  }

  return previous               // the old tail is the new head
}

const demoList = { value: 1, next: { value: 2, next: { value: 3, next: null } } }
let demoNode = reverse(demoList)
const demoOut = []
while (demoNode) { demoOut.push(demoNode.value); demoNode = demoNode.next }
console.log(demoOut)  // [3, 2, 1]

Saving next before overwriting current.next is the whole trick. Forget it and you have severed the rest of the list.

Doubly linked

Add a prev reference and you can walk backwards and delete a node given only that node. The cost is a second reference per node and two updates on every change. An LRU cache is the standard use - a doubly linked list for order, a Map for lookup.