Cairn
data structures · O(1) insert at either end · O(n) search

↩ back to Linear

Linked List

A linked list holds a sequence of items the way a scavenger hunt holds a sequence of clues: each node stores a value and a pointer to the next node, and you can only get from one to the next by following that pointer. There's no single block of memory holding everything, the way an array has — just nodes scattered wherever, connected by arrows. The list itself only needs to remember where the chain starts (the head) and, for the version below, where it ends (the tail).

That's a real trade against a dynamic array. You give up O(1) random access — "give me the 5th element" means walking 5 pointers, there's no arithmetic shortcut to an address. In exchange, inserting or removing a node you already have a reference to costs O(1): relink a couple of pointers, nothing has to shift over. A stack or queue backed by a linked list gets that O(1) guarantee at both ends for free, with no array-resize or compaction tricks required.

Try it

Insert at the front or back, delete the first node matching a value, or find a value's position by walking the chain from the head. The highlighted node is the head — the only node the list can reach without following pointers through everything before it.

Loaded a sample list. Insert, delete, find, or clear — try deleting a value that isn't there.

Core operations

Reference implementation

class LinkedList {
  #head = null;
  #tail = null;
  #size = 0;

  get size() { return this.#size; }
  isEmpty() { return this.#size === 0; }

  insertFront(x) {
    const node = { value: x, next: this.#head };
    this.#head = node;
    if (this.#tail === null) this.#tail = node;
    this.#size++;
  }

  insertBack(x) {
    const node = { value: x, next: null };
    if (this.#tail === null) {
      this.#head = this.#tail = node;
    } else {
      this.#tail.next = node;
      this.#tail = node;
    }
    this.#size++;
  }

  deleteValue(x) {
    if (this.#head === null) return false;
    if (this.#head.value === x) {
      this.#head = this.#head.next;
      if (this.#head === null) this.#tail = null;
      this.#size--;
      return true;
    }
    let prev = this.#head;
    let curr = this.#head.next;
    while (curr !== null) {
      if (curr.value === x) {
        prev.next = curr.next;
        if (curr === this.#tail) this.#tail = prev; // deleted node was the tail
        this.#size--;
        return true;
      }
      prev = curr;
      curr = curr.next;
    }
    return false;
  }

  find(x) {
    let curr = this.#head;
    let i = 0;
    while (curr !== null) {
      if (curr.value === x) return i;
      curr = curr.next;
      i++;
    }
    return -1;
  }
}

The fiddly part is the bookkeeping: insertFront on an empty list must set both head and tail to the new node, and deleteValue must special-case deleting the head (there's no predecessor to relink) and update the tail pointer if the deleted node happened to be the last one. Verified against a naive array-backed model over 200,000 randomized operations, plus edge cases (empty list, single-node list, deleting the tail), before publishing — see /tmp/linked_list_test.js, not committed, it's scratch.

Pitfalls

Losing the head. If you ever overwrite the head pointer before you're done using the old value — head = head.next before you've saved what you needed from the old head — the rest of the chain becomes unreachable. There's no "undo," the list is just gone from that point on.

Forgetting the tail on deletion. A list with a tail pointer has to actively maintain it. Delete the last node without checking whether it was the tail, and the tail pointer keeps pointing at a node that's no longer in the chain — the next insertBack silently attaches to a dangling node instead of the real list.

Treating it like an array. list[3] isn't a thing — getting the 3rd element means three .next hops, not an index lookup. Code that loops with an index and expects array-speed access to each one will work, but silently degrade to O(n²) for what looks like an O(n) loop.

Measure it instead of taking "silently degrades" on faith. This race builds a list and an array of the same n values, then reads every index 0 through n-1 once each — the loop shape that looks identical on both structures — and counts every real node/element touched: the list version walking .next from the head for each index, against the array's direct arr[i].

Press "Run race" to count real node hops and array reads for both structures over an indexed 0..n-1 read loop.

At n = 1,000 — reading every index 0..999 once — the indexed .next-walk touches 500,500 nodes total (index i costs i+1 hops from the head); the plain array touches 1,000 — a 500.5x difference. That ratio isn't fixed: at n = 200 it's 100.5x, and at n = 5,000 it's 2,500.5x, growing linearly with n itself — exactly the extra factor of n that turns an O(n)-looking loop into real O(n²) work.

Where linked lists show up

Complexity

Time: insertFront and insertBack (with a tail pointer) are O(1). find and deleteValue are O(n) — dominated by the search, since removing a node you've already found is O(1). Random access by index is O(n), unlike an array's O(1) — this is the core trade the structure makes. Space: O(n) for n nodes, plus one pointer per node (two for a doubly linked list) that an array doesn't need to spend.

This site's guide, Choosing a Linear Data Structure, compares this entry against the other six Linear structures side by side.