Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Data structures

Linked List Visualiser

Nodes joined by references, with no indexes to jump by.

Operations

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

  1. addFirst makes a node pointing at the current head, then moves head to it. One step, whatever the length.
  2. addLast has to walk to the end first, unless the list keeps a tail reference.
  3. remove walks until it finds the value, then points the node before it at the node after it.
  4. 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

addFirstO(1)
addLastO(n), or O(1) with a tail reference
remove by valueO(n)
Reach the nth nodeO(n)
reverseO(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.

Read more