A treasure hunt of nodes
A linked list stores each item in a node that points to the next one. There's no shifting when you insert — just re-point two arrows — but to reach the 500th item you must follow 500 pointers. Linked lists power queues, LRU caches and the undo stacks of editors.
Nodes and pointers
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
class LinkedList {
head = null;
size = 0;
prepend(value) { this.head = new Node(value, this.head); this.size++; }
insertAfter(node, value) { node.next = new Node(value, node.next); this.size++; }
find(value) {
for (let n = this.head; n; n = n.next) if (n.value === value) return n;
return null;
}
toArray() {
const out = [];
for (let n = this.head; n; n = n.next) out.push(n.value);
return out;
}
}
const route = new LinkedList();
route.prepend("Kitchen");
route.insertAfter(route.head, "Table 5");
route.insertAfter(route.find("Kitchen"), "Table 2");
console.log(route.toArray().join(" → "), "| size", route.size);