Data structures
Linked List Visualiser
Nodes joined by references, with no indexes to jump by.
head is null: the list is empty.
A linked list is nodes joined by references. There are no indexes: to reach the fifth node you must walk through the four before it.
- Nodes
- 0
- Links followed
- 0
- Operations run
- 0
class LinkedList { head = null; addFirst(value) { this.head = { value, next: this.head }; } addLast(value) { const node = { value, next: null }; if (!this.head) return (this.head = node); let last = this.head; while (last.next) last = last.next; last.next = node; } remove(value) { let prev = null, node = this.head; while (node && node.value !== value) { prev = node; node = node.next; } if (!node) return false; if (prev) prev.next = node.next; else this.head = node.next; return true; } reverse() { let prev = null, node = this.head; while (node) { const next = node.next; node.next = prev; prev = node; node = next; } this.head = prev; }}The highlighted line is the one that produced the picture on the left.
What Linked List does
A linked list is a chain of nodes, each holding a value and a reference to the next one. There is no index arithmetic, so you cannot jump to the middle — but inserting and removing cost nothing once you are standing in the right place, because only a reference changes and nothing is shifted.
How it works, step by step
- addFirst makes a node pointing at the current head, then moves head to it. One step, whatever the length.
- addLast has to walk to the end first, unless the list keeps a tail reference.
- remove walks until it finds the value, then points the node before it at the node after it.
- reverse turns every next reference round in a single pass, keeping hold of the next node before overwriting the link.
What to watch for
- The links-followed counter: it only ever grows during a walk, and every operation that needs the end or the middle has to pay it.
- Removing a node shifts nothing. Compare that with an array, where removing from the front moves every later element.
- During a reverse, the list is briefly split in two. Losing hold of the rest of it is the classic bug, which is why `next` is saved before `node.next` is overwritten.
Cost
| addFirst | O(1) |
|---|---|
| addLast | O(n), or O(1) with a tail reference |
| remove by value | O(n) |
| Reach the nth node | O(n) |
| reverse | O(n), no extra space |
When to reach for it
When insertions and removals in the middle dominate and you are already holding the node — the LRU caches, free lists and adjacency lists inside systems code. For almost everything else an array wins, because it is contiguous in memory and the cache rewards that heavily.