Lesson 12
Linked Lists: Following Pointers
Trade instant indexing for instant insertion anywhere you already stand.
01Why it matters & the intuition
Linked lists teach pointer manipulation — the exact skill needed for trees, graphs and LRU caches. They also appear in almost every interview loop.
Think of it like…
A treasure hunt: each clue tells you where the next clue is hidden. Adding a clue in the middle only means rewriting one note — no one else moves. But to reach clue #50 you must follow 49 clues first.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- walked
- result
- rewired
03Key ideas
Nodes and next
Each node stores a value and a next pointer. The list is just a reference to the head; the last node points to null.
O(1) splice
Given a node, inserting after it is two pointer writes: newNode.next = node.next; node.next = newNode.
No random access
Reaching index i means walking i nodes: O(n). There is no address arithmetic because nodes live anywhere in memory.
Tail pointer & doubly linked
Keeping a tail makes append O(1). Adding prev pointers (doubly linked) makes deleting a known node O(1) too — the basis of an LRU cache.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
class ListNode<T> {
constructor(public value: T, public next: ListNode<T> | null = null) {}
}
class LinkedList<T> {
head: ListNode<T> | null = null;
tail: ListNode<T> | null = null;
size = 0;
prepend(value: T): void {
this.head = new ListNode(value, this.head);
if (!this.tail) this.tail = this.head;
this.size++;
}
append(value: T): void {
const node = new ListNode(value);
if (!this.tail) this.head = this.tail = node;
else this.tail = this.tail.next = node;
this.size++;
}
remove(value: T): boolean {
let prev: ListNode<T> | null = null;
let cur = this.head;
while (cur && cur.value !== value) { prev = cur; cur = cur.next; }
if (!cur) return false;
if (prev) prev.next = cur.next; else this.head = cur.next;
if (cur === this.tail) this.tail = prev;
this.size--;
return true;
}
// Reverse by flipping every arrow — O(n) time, O(1) space.
reverse(): void {
let prev: ListNode<T> | null = null;
let cur = this.head;
this.tail = cur;
while (cur) {
const next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
this.head = prev;
}
}05Complexity
| Operation | Time | Space |
|---|---|---|
| Access by index | O(n) | — |
| Insert / delete at head | O(1) | — |
| Append (with tail pointer) | O(1) | — |
| Search | O(n) | — |
| Reverse | O(n) | O(1) |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Reverse a linked list
Write reverse_list(head) that reverses a singly linked list and returns the new head. Nodes look like { value, next }. (The harness converts arrays to lists and back for you.)
Nodes have .value and .next.