Linked Lists

Linked list: nodes chained via pointers. O(1) insert/remove at known positions, but no random access - walking n nodes to reach index i means arrays win for most application code.

A linked list is a chain of nodes; each node holds a value and a reference (pointer) to the next node. There is no underlying contiguous block of memory, which means inserting or removing a node at a known position is O(1) - you just rewire two pointers. The trade-off is that there is no index: to get item number 50 you have to follow the chain 50 times.

A minimal singly-linked list needs a Node class and a LinkedList class. prepend adds to the front in O(1). append walks to the last node and attaches there - O(n). An iteration helper (or a standard [Symbol.iterator]) lets you loop over the values with a for...of loop.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
 
class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
 
  prepend(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    this.size++;
  }
 
  append(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next; // walk to the last node
      }
      current.next = node;
    }
    this.size++;
  }
 
  [Symbol.iterator]() {
    let current = this.head;
    return {
      next() {
        if (!current) return { done: true, value: undefined };
        const value = current.value;
        current = current.next;
        return { done: false, value };
      },
    };
  }
}
 
const list = new LinkedList();
list.append("a");
list.append("b");
list.append("c");
 
for (const val of list) {
  console.log(val); // "a", "b", "c"
}
 
console.log(list.size); // 3

The key limitation of a linked list is the absence of random access. Getting the item at index i requires starting at the head and following i pointers. With an array the same operation returns instantly because the runtime can compute the memory address directly from the index.

class LinkedList {
  // ... (same as above)
  get(index) {
    let current = this.head;
    let i = 0;
    while (current) {
      if (i === index) return current.value;
      current = current.next;
      i++;
    }
    return undefined; // index out of bounds
  }
}
 
// Linked list: O(n) - must walk from the head
const list = new LinkedList();
for (let i = 0; i < 1000; i++) list.append(i);
console.log(list.get(999)); // 999 - walked 1000 nodes
 
// Array: O(1) - computed from base address + offset
const arr = Array.from({ length: 1000 }, (_, i) => i);
console.log(arr[999]); // 999 - instant lookup

In production

Pointer chasing (following a chain of references scattered across the heap) destroys CPU cache locality: each node read is likely a cache miss, which is far slower than reading a contiguous array. In V8, arrays win for almost every application-code use case. The real production scenario where a linked list earns its keep is a doubly-linked list inside an LRU cache: you need O(1) insertion and O(1) removal at arbitrary positions, and you always have a direct reference to the node you want to move, so you never have to scan.

← PreviousStacks and Queues Next →Trees

Enjoyed this? Get more essays on software craft delivered to your inbox.

Subscribe free