Definition
A linked list is a sequence whose order is held in links rather than positions: each node stores a value and a reference to the next node. In a doubly linked list, each node also refers to the one before it.
After Cormen et al., Introduction to Algorithms, §10.2
01Change the finishing order
“Put this job after that one.”
You have almost certainly never typed new LinkedList() at work. Yet if you
write React, every component with state, refs, or effects is holding one. Hooks like useState and useEffect each get a node in a chain, in the order
you call them, each pointing to the next. Put a hook inside an if and the chain
stops lining up with the calls. That is the whole reason the rule exists.
The bindery worklist starts Pocket guide → Annual report → Poetry collection. Insert Repair manual after Annual report, then move that same held job after Pocket guide.
An array is a fair choice for occasional edits: find the position, splice. A linked list makes a different promise. Once you are holding a particular node, you can change its neighbors without shifting anything after it. The condition is the point: once you are holding the node. If all you have is the name “Annual report,” someone still has to go and find it. This lesson keeps that search visible.
A linked list keeps order through links: each node holds a value and a reference to the next node. Ours is doubly linked, so each node also knows the one before it. The list holds a head and a tail. Head has no previous; tail has no next. Walk next from head and you visit every live node once. Walk previous from tail and you get the reverse. Both directions have to agree. Empty means neither end.
Is the order where the nodes sit in memory?Logical order and storage layout
No. TypeScript and Go link nodes by reference. Rust keeps nodes in an owned arena and links them by index. What makes it a linked list is how order is represented, not where the bytes live.
02Read the model
Find the anchor. Change the links.
TypeScript and Go have no linked list you would reach for by default, and Rust’s has no handles (see the next sections). To see the links, this lesson spells out a small model: a doubly linked list whose insert and move return or take a node. In real code, use your language’s own sequence unless callers really hold the items they rearrange.
This is the whole program the lab runs: the list, then three jobs, a find, one insert and one move.
type ListNode<T> = { value: T; prev: ListNode<T> | null; next: ListNode<T> | null };
class LinkedList<T> {
head: ListNode<T> | null = null;
tail: ListNode<T> | null = null;
push(value: T): ListNode<T> {
const node: ListNode<T> = { value, prev: this.tail, next: null };
if (this.tail) this.tail.next = node;
else this.head = node;
this.tail = node;
return node;
}
find(value: T): ListNode<T> | null {
for (let node = this.head; node; node = node.next) {
if (node.value === value) return node;
}
return null;
}
insertAfter(anchor: ListNode<T>, value: T): ListNode<T> {
const node: ListNode<T> = { value, prev: anchor, next: anchor.next };
if (anchor.next) anchor.next.prev = node;
else this.tail = node;
anchor.next = node;
return node;
}
moveAfter(node: ListNode<T>, anchor: ListNode<T>): void {
if (node === anchor || anchor.next === node) return;
// Unhook from the old neighbors.
if (node.prev) node.prev.next = node.next;
else this.head = node.next;
if (node.next) node.next.prev = node.prev;
else this.tail = node.prev;
// Hook in after the anchor.
node.prev = anchor;
node.next = anchor.next;
if (anchor.next) anchor.next.prev = node;
else this.tail = node;
anchor.next = node;
}
values(): T[] {
const out: T[] = [];
for (let node = this.head; node; node = node.next) out.push(node.value);
return out;
}
}
const jobs = new LinkedList<string>();
const pocket = jobs.push('Pocket guide');
jobs.push('Annual report');
jobs.push('Poetry collection');
// The caller has a name, not a node: find walks from the head to get one.
const annual = jobs.find('Annual report');
if (!annual) throw new Error('Annual report is not on the worklist');
const repair = jobs.insertAfter(annual, 'Repair manual');
console.log(jobs.values().join(' → '));
jobs.moveAfter(repair, pocket);
console.log(jobs.values().join(' → '));The caller has only the name “Annual report”, so find walks from the head, following next
one link at a time, until it reaches that node: the search half of the work. Then insert
Repair manual after it: the new node points back to Annual report and on to Poetry
collection, and both neighbors point to it (four link writes). The job never moves
in memory; only links change. moveAfter takes a node the caller already holds, joins
its old neighbors to each other, and hooks it in after the anchor. Moving a node after itself,
or after the node already before it, does nothing.
Reading the TypeScriptA generic node type and null links
ListNode<T> is a plain object type; prev and next are ListNode<T> | null, so the compiler makes every walk check for the
end. push and insertAfter return the node they made: that return value
is the handle the rest of the program holds.
What a production worklist addsOpaque handles, names, removal, and a checked call site
The same list, generic over its values. Insert-after hands you a new handle. Move-after
keeps an existing one. Remove hands back the value and retires the handle. No destination
means “at the front.” On top, Worklist owns everything about names: what counts
as one, that repeats are allowed, that Find is exact and returns the first match in current
order. The list never sees a name rule.
declare const handleType: unique symbol;
export type Handle<T> = Readonly<{ id: number; [handleType]: T }>;
export type Lookup<T> = { found: true; value: T } | { found: false };
export type LinkWrite = {
node: number | null;
field: 'head' | 'tail' | 'prev' | 'next';
from: number | null;
to: number | null;
};
export type Trace = { visits: number[]; writes: LinkWrite[] };
export type View<T> = {
head: number | null;
tail: number | null;
size: number;
nodes: { id: number; value: T; prev: number | null; next: number | null }[];
};
type Node<T> = { handle: Handle<T>; value: T; prev: Node<T> | null; next: Node<T> | null };
export class LinkedList<T> {
#head: Node<T> | null = null;
#tail: Node<T> | null = null;
#size = 0;
#nextId = 1;
#nodes = new WeakMap<Handle<T>, Node<T>>();
#trace: Trace = { visits: [], writes: [] };
constructor(private readonly captureTrace = false) {}
get size() {
return this.#size;
}
front(): Handle<T> | null {
return this.#head?.handle ?? null;
}
back(): Handle<T> | null {
return this.#tail?.handle ?? null;
}
has(handle: Handle<T>): boolean {
return this.#nodes.has(handle);
}
#begin() {
this.#trace = { visits: [], writes: [] };
}
#record(
node: Node<T> | null,
field: LinkWrite['field'],
from: Node<T> | null,
to: Node<T> | null
) {
if (this.captureTrace && from !== to)
this.#trace.writes.push({
node: node?.handle.id ?? null,
field,
from: from?.handle.id ?? null,
to: to?.handle.id ?? null
});
}
#end(field: 'head' | 'tail', to: Node<T> | null) {
this.#record(null, field, field === 'head' ? this.#head : this.#tail, to);
if (field === 'head') this.#head = to;
else this.#tail = to;
}
#link(node: Node<T>, field: 'prev' | 'next', to: Node<T> | null) {
this.#record(node, field, node[field], to);
node[field] = to;
}
#attach(node: Node<T>, after: Node<T> | null) {
const next = after ? after.next : this.#head;
this.#link(node, 'prev', after);
this.#link(node, 'next', next);
if (after) this.#link(after, 'next', node);
else this.#end('head', node);
if (next) this.#link(next, 'prev', node);
else this.#end('tail', node);
}
#detach(node: Node<T>) {
if (node.prev) this.#link(node.prev, 'next', node.next);
else this.#end('head', node.next);
if (node.next) this.#link(node.next, 'prev', node.prev);
else this.#end('tail', node.prev);
}
insertAfter(after: Handle<T> | null, value: T): Handle<T> | null {
this.#begin();
const anchor = after === null ? null : this.#nodes.get(after);
if (anchor === undefined) return null;
const handle = Object.freeze({ id: this.#nextId++ }) as Handle<T>;
const node: Node<T> = { handle, value, prev: null, next: null };
this.#nodes.set(handle, node);
this.#attach(node, anchor);
this.#size++;
return handle;
}
moveAfter(handle: Handle<T>, after: Handle<T> | null): 'moved' | 'unchanged' | 'invalid-handle' {
this.#begin();
const node = this.#nodes.get(handle);
const anchor = after === null ? null : this.#nodes.get(after);
if (!node || anchor === undefined) return 'invalid-handle';
if (node === anchor || node.prev === anchor) return 'unchanged';
this.#detach(node);
this.#attach(node, anchor);
return 'moved';
}
remove(handle: Handle<T>): Lookup<T> {
this.#begin();
const node = this.#nodes.get(handle);
if (!node) return { found: false };
this.#detach(node);
this.#link(node, 'prev', null);
this.#link(node, 'next', null);
this.#nodes.delete(handle);
this.#size--;
return { found: true, value: node.value };
}
find(matches: (value: T) => boolean): Handle<T> | null {
this.#begin();
for (let node = this.#head; node; node = node.next) {
if (this.captureTrace) this.#trace.visits.push(node.handle.id);
if (matches(node.value)) return node.handle;
}
return null;
}
// Metadata and outer sequences are independent; arbitrary payloads are not deep-cloned.
view(): View<T> {
const nodes: View<T>['nodes'] = [];
for (let node = this.#head; node; node = node.next)
nodes.push({
id: node.handle.id,
value: node.value,
prev: node.prev?.handle.id ?? null,
next: node.next?.handle.id ?? null
});
return {
head: this.#head?.handle.id ?? null,
tail: this.#tail?.handle.id ?? null,
size: this.#size,
nodes
};
}
reverseValues(): T[] {
const values: T[] = [];
for (let node = this.#tail; node; node = node.prev) values.push(node.value);
return values;
}
trace(): Trace {
return {
visits: [...this.#trace.visits],
writes: this.#trace.writes.map((write) => ({ ...write }))
};
}
}
export type Job = Handle<string>;
export class Worklist {
#list: LinkedList<string>;
#trace: Trace = { visits: [], writes: [] };
constructor(captureTrace = false) {
this.#list = new LinkedList(captureTrace);
}
insertAfter(
after: Job | null,
label: string
): { status: 'inserted' | 'invalid-label' | 'invalid-handle'; handle: Job | null } {
this.#trace = { visits: [], writes: [] };
if (!/^[\x20-\x7e]{1,40}$/.test(label) || !/[^ ]/.test(label))
return { status: 'invalid-label', handle: null };
const handle = this.#list.insertAfter(after, label);
this.#trace = this.#list.trace();
return { status: handle ? 'inserted' : 'invalid-handle', handle };
}
find(label: string): Job | null {
const handle = this.#list.find((value) => value === label);
this.#trace = this.#list.trace();
return handle;
}
moveAfter(handle: Job, after: Job | null) {
const status = this.#list.moveAfter(handle, after);
this.#trace = this.#list.trace();
return status;
}
remove(handle: Job): Lookup<string> {
const result = this.#list.remove(handle);
this.#trace = this.#list.trace();
return result;
}
has(handle: Job): boolean {
return this.#list.has(handle);
}
view(): View<string> {
return this.#list.view();
}
reverseValues(): string[] {
return this.#list.reverseValues();
}
trace(): Trace {
return {
visits: [...this.#trace.visits],
writes: this.#trace.writes.map((write) => ({ ...write }))
};
}
}The call site checks Find succeeded before inserting after its result, because “not found” must never quietly turn into “insert at the front.”
export function runExample(): void {
const sheet = new Worklist(true);
const lights = sheet.insertAfter(null, 'Pocket guide').handle!;
const music = sheet.insertAfter(lights, 'Annual report').handle!;
sheet.insertAfter(music, 'Poetry collection');
const found = sheet.find('Annual report');
if (!found) throw new Error('The expected job is missing.');
console.log(`find: #${found?.id}; visited=${sheet.trace().visits.length}`);
const spot = sheet.insertAfter(found, 'Repair manual').handle!;
const order = () =>
sheet
.view()
.nodes.map((node) => node.value)
.join(' > ');
console.log(`insert: ${order()}; links=${sheet.trace().writes.length}`);
sheet.moveAfter(spot, lights);
console.log(`move: ${order()}; links=${sheet.trace().writes.length}; same=#${spot.id}`);
sheet.remove(spot);
console.log(`removed: ${order()}; stale=${sheet.moveAfter(spot, lights)}`);
}The handle is a branded type, and a private WeakMap checks the actual token
object at runtime, so building { id: 4 } yourself does not get
you job #4. Each list has its own lookup. Removal deletes the entry and clears the
node’s links. The tagged removal result tells absence apart from a stored undefined. A Find predicate must not mutate the list mid-walk.
03Predict the move
The job moves. Is it the same job?
04Meet it in your language
The links are there, whether or not you wrote them.
In TypeScript you meet linked lists inside the tools you use: React keeps each component’s hooks as a list of records walked in call order. Here is a small model of it; real React keeps the same list on each component’s fiber.
// A component's hooks, the way React keeps them: one record per call,
// linked in call order, and read back in that order on every render.
type Hook = { state: string; next: Hook | null };
let first: Hook | null = null; // the component's list, kept between renders
let current: Hook | null = null; // the record the next call reads
let previous: Hook | null = null;
function useState(initial: string): string {
if (current) {
// A later render: take the next record in the list, whatever it held.
const hook = current;
previous = hook;
current = hook.next;
return hook.state;
}
// The first render: link a new record after the last one.
const hook: Hook = { state: initial, next: null };
if (previous) previous.next = hook;
else first = hook;
previous = hook;
return initial;
}
function render(component: () => string): string {
current = first;
previous = null;
return component();
}
let onCall = true;
// The bug: which hook is called second depends on onCall.
function Profile(): string {
const name = useState("Ada");
const note = onCall ? useState("on call") : "";
const theme = useState("dark");
const away = onCall ? "" : useState("back at 3");
return `${name} | ${note || away} | ${theme}`;
}
console.log(render(Profile));
onCall = false;
console.log(render(Profile));
// The fix: call every hook on every render, and decide what to show after.
first = null;
onCall = true;
function ProfileFixed(): string {
const name = useState("Ada");
const note = useState("on call");
const theme = useState("dark");
const away = useState("back at 3");
return `${name} | ${onCall ? note : away} | ${theme}`;
}
console.log(render(ProfileFixed)); // Ada | on call | dark
onCall = false;
console.log(render(ProfileFixed)); // Ada | back at 3 | darkCall every hook on every render, at the top level, and decide what to show after. The list can only line up with the calls if the calls are the same each time.
05Count the work
Finding a node and relinking it are separate operations.
Here is every operation at a glance, with n live nodes. Look down the time column and you can see the split this whole lesson has been circling: finding is linear, and changing what you already hold is constant.
| Operation | Time | Extra space | Why |
|---|---|---|---|
| Read head or tail | O(1) | O(1) | Both ends are stored. |
| Find a value | O(n) | O(1) | Walks from the head until it finds a match or runs out. |
| Reach the kth node | O(k) | O(1) | Not a method in this lesson’s code, because a linked node has no index. Any positional access walks k links. |
| Insert after a held node | O(1) | O(1) auxiliary | You already hold the handle. At most 4 link fields change, plus a new node. |
| Move a held node | O(1) | O(1) | At most 6 link fields change. The value itself is never copied. |
| Remove a held node | O(1) | O(1) | Needs the previous link, which is why this list is doubly linked. |
| Scan all n, against an array | O(n), slower | Two links a node | Same O(n), but each step follows a pointer to a separate allocation; an array reads one block the cache loads in runs. |
The production code’s own costsRust’s arena, building a view, stale handles
| Operation | Time | Extra space | Why |
|---|---|---|---|
| Insert after a held node | O(1); Rust O(1) amortized | O(1) auxiliary | A Rust arena that grows its Vec may relocate O(I) slots, where I is total insertions. |
| Build a view | O(n); Rust adds clone cost | O(n); Rust adds clone space | Walks each live occurrence once and allocates O(n) view records. TypeScript shares payload references; Go copies each T value shallowly; Rust clones each T. |
| Retained node storage | — | TS O(n); Go O(n+r); Rust O(I) | Live nodes carry two links plus a value. In Go, r stale handles a caller keeps hold r cleared node shells. Rust keeps one arena slot per insertion; removed slots stay until the list is dropped. |
In Rust, growing the arena can move existing storage during an insert: that is where its amortized O(1) comes from.
Find is a walk. With n live jobs it may visit all n before it finds a match or gives up. Reaching “the 40th job” is a walk too; a linked node has no index. Comparing big payloads makes every visit dearer.
Relinking is not a walk. Once you hold valid handles, this doubly linked list changes a fixed handful of fields. The story’s insertion changed four: the new node’s two links and one link on each neighbor. The move changed six: unhook from the old neighbors, hook in at the destination. A block of held nodes moves the same way, with the same six writes however long it is: the links inside the block already say what they need to. An array would shift every element between the two places.
The counting rule, here and in the lab: a link write is each assignment to a node’s previous or next field, whether or not the value changes, and a link read is each time code follows one, a step along the list. The list’s head and tail are not counted. A no-op move returns before it writes anything. Relinking uses O(1) auxiliary space; the small link count is a promise about relinking, not about total API work (allocation and payload cleanup are left out).
The six writes for a block hold only if you hold both ends of the block. Find one end by walking and the move costs that walk too.
Previous links cost space. A singly linked list carries less, but a node on its own cannot tell you who precedes it, so removing an interior node needs that predecessor already in hand or another walk to find it. The one shortcut, copying the next node’s value over it and removing that one instead, fails on the tail and silently changes which node is which, the very identity this lesson depends on.
06Choose another structure
Use it when callers hold the items they change.
A linked list earns its place when callers hold particular items and insert, move or remove around them, and nothing should shift. Most of the time something else is simpler:
- Dynamic array: you append, scan and read by position. One block of slots is one step to index and kind to the cache; inserting in the middle shifts, which is fine for occasional edits.
- Queue or deque: work only at the ends. A deque gives O(1) at both without a node per item.
- Hash map: you look items up by name. A map from name to node is how a linked list gets its handles, and the two together are an LRU cache.
You have used the handle idea already: a React list’s key is a handle.
React matches each key to the component it rendered last time, so a row keeps its state
when the list is reordered. Using the index as the key makes it a label for a position,
and the state stays with the position instead of the row.
Linked-list patterns interviews ask aboutSentinel, reversal, two pointers
- A sentinel head: a dummy node before the first, so inserting or removing at the front is the same code as anywhere else; the head and tail cases this lesson handles separately disappear.
- Reversal: walk once, turning each next link around, keeping the previous node and the next one in two variables: O(n) time, O(1) space.
- Fast and slow pointers: one walker moves two links per step, the other one. When the fast one reaches the end, the slow one is at the middle; if they ever meet, the list has a cycle.
07Choose by what you hold
A job label is not a node handle.
A worklist a thousand entries long. Someone tells you “inserting into a linked list is constant time.” Before you agree, look at what the caller is holding.
Before you open the answer below, say it in your own words: what does a linked list hold instead of positions, what does a handle buy you, and when is a linked list the wrong structure?
One way to say itLinks, handles, and the walk you cannot skip
A linked list keeps order in links: each node points to the next, and in a doubly linked list to the previous too. If you hold a node, you can insert after it, move it or remove it by rewriting a fixed handful of links, whatever the list’s length, and nothing else shifts. But a name or a position is not a node: finding one walks the list, O(n). So a linked list pays off only when callers keep handles, often from a map of name to node. When you read by position, scan, or work only at the ends, an array or a deque is simpler and faster.
Practice in the lab
A rail yard keeps each freight train as a doubly linked list of cars, and its yard tool holds handles to the cars it works on: the lesson’s worklist, with cars for jobs. The cars come from the checker’s plumbing, which counts every link read (each step along the train) and every link write, so the checker can tell a correct operation that walks from one that relinks, however the code is written. Each level starts from the previous level’s finished code, so you can begin at any of them.
- LINKED-LIST-101 (easy) A car cannot be uncoupled
- LINKED-LIST-102 (medium) Moving a block of cars rebuilds the train car by car Pro
- LINKED-LIST-103 (hard) Review: flagged cars stay on, and shunting plans crawl Pro