↩ 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.

Core operations

• insertFront(x) — make a new node point at the current head, then become the head. O(1).
• insertBack(x) — point the current tail at a new node, then that node becomes the tail. O(1), but only if the list keeps a tail pointer — without one, you'd have to walk the whole chain first to find the last node.
• deleteValue(x) — walk from the head until you find a node holding x, then relink its predecessor's pointer past it. O(n) to find the node, O(1) to actually remove it once found.
• find(x) — walk from the head comparing values, return the position or "not found". O(n) — there's no shortcut, you must visit every node up to it.

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.

Where linked lists show up

• Building other structures. A stack or queue implemented on top of a linked list gets O(1) operations at the relevant end(s) without ever needing to resize or compact an underlying array — the trade-off section above is exactly why.
• LRU caches. A common implementation pairs a hash map (for O(1) lookup) with a doubly linked list (a node points both directions) so the least-recently-used item — whichever end of the list that is — can be evicted in O(1) once found, and any node can be unlinked and moved to the front in O(1) too.
• Undo history with branches, or any structure that grows/shrinks by relinking rather than shifting. Anywhere insertions and deletions vastly outnumber random lookups, a linked list's O(1) splice beats an array's O(n) shift.
• The call stack of a language runtime, conceptually. Some interpreters implement their internal frame stack as a linked chain rather than a flat array, for exactly the "cheap to grow, no resize" reason above.

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.