Linked Lists

Picture a treasure hunt. You're handed a first clue; it tells you the treasure and where to find the next clue. That clue reveals the next, and the next, until one finally says "the trail ends here". You never hold a map of every location at once — you only ever know where you are and where to go next, following the chain link by link.

A linked list is exactly this idea as a data structure. It is a chain of little parcels called nodes. Each node holds two things:

some data — the value we actually want to store (a number, a name, a whole object);
a pointer (also called a reference or link) to the next node in the chain.

The list itself keeps hold of just one thing — a reference to the very first node, called the head. To use the list you start at the head and follow each node's "next" pointer along the chain. The final node has nothing after it, so its next pointer is null — the signal that says "the trail ends here".

The picture: nodes, arrows, and null

Here is a linked list holding the values 3, 7, 1, 9. Each box is a node; the left half is its data, the right half is the pointer to the next node. Follow the arrows from the head until you fall off the end into null:

Two features are worth naming out loud. First, the head is not a node — it is a single reference that lives outside the chain and points at the first node; it is your only way in. Second, the last node's next is null: that is how any traversal knows to stop. Lose track of "am I at null yet?" and you either stop too early or run off into nothing.

Building and walking a list in code

Let's make this concrete in TypeScript. A node is just an object with a value and a next, where next is either another node or null. We build the chain from the back forwards, then traverse it: start a "current" pointer at the head and keep hopping to current.next until we hit null. Press Run:

// A node holds a value and a link to the next node (or null at the end). interface Node { value: number; next: Node | null; } // Build the chain 3 → 7 → 1 → 9 → null (from the back forwards). const n4: Node = { value: 9, next: null }; // the last node points at null const n3: Node = { value: 1, next: n4 }; const n2: Node = { value: 7, next: n3 }; const head: Node = { value: 3, next: n2 }; // the head: our way in // Traverse: follow the "next" pointers until we fall off the end. let current: Node | null = head; while (current !== null) { console.log(current.value); current = current.next; // hop to the next node }

Notice the shape of that loop — it is the linked-list equivalent of counting through an array's indices, but instead of i++ we write current = current.next. The condition current !== null is what makes it stop cleanly at the end of the chain.

The party trick: inserting at the head

Here is where linked lists shine. To add a new value at the front of the list, you don't shuffle anything: you make a new node, point its next at the current head, and then move the head to the new node. Two pointer assignments — done, no matter how long the list is.

interface Node { value: number; next: Node | null; } // Start with 7 → 1 → 9 → null let head: Node | null = { value: 7, next: { value: 1, next: { value: 9, next: null } } }; // Insert 3 at the FRONT: new node points at the old head, then head moves. const fresh: Node = { value: 3, next: head }; // 1) link the new node to the chain head = fresh; // 2) the head now starts here // Walk it to prove 3 is now first. let current: Node | null = head; const seen: number[] = []; while (current !== null) { seen.push(current.value); current = current.next; } console.log("List is now:", seen.join(" -> ") + " -> null");

Compare that with an array: to put a new value at index 0 of an array, every existing element must slide up one place to make room — cheap for five items, painfully slow for five million. In a linked list, front insertion costs the same whether the list has three nodes or three billion.

Linked list vs array: the trade-off

Neither structure is "better" — they make opposite bargains, and A-level questions love to test which one you would pick for a job.

Insertion / deletion at the front (or anywhere you already stand): a linked list just re-points a couple of links — very cheap. An array must shift everything after the gap along.
Getting the i-th item: an array does it instantly — the address is a simple calculation from the index. A linked list has no instant index access: to reach the 500th node you must walk from the head through the 499 before it.
Memory layout: an array's elements sit in one contiguous block. A linked list's nodes needn't be contiguous — they can be scattered all over memory, tied together only by their pointers. That makes a list easy to grow one node at a time without reserving a big block up front.

Rule of thumb: reach for an array when you need fast random access by index; reach for a linked list when you're forever inserting and removing at the ends and don't need to jump to arbitrary positions.

The list we've drawn is singly linked: each node points only forwards, to its successor, so you can travel in one direction. A doubly linked list gives each node a second pointer, prev, back to the node before it, so you can walk the chain in both directions and delete a node without first hunting down its predecessor. The price is an extra pointer to store and keep correct in every node. Many real toolkits (e.g. the list behind a music player's "previous track" / "next track") are doubly linked for exactly that two-way freedom.

Linked lists punish careless pointer work. Three classic ways to lose everything:

Losing the head. The head reference is your only handle on the list. If you overwrite head without first saving the old value, every node it reached is now unreachable — the whole list is orphaned and the garbage collector reclaims it. It hasn't "moved"; it's simply gone.
Re-linking in the wrong order. When inserting, link the new node into the chain before you detach the old link. Writing prev.next = fresh first — before fresh.next = prev.next — throws away the pointer to the rest of the list, dropping everything after the insertion point. Always attach the new node's next first, then re-point the node in front of it.
Forgetting the terminating null. The last node's next must be null. Leave it pointing at some stray node (or at itself) and a traversal never sees null, so the while (current !== null) loop runs forever.

The safe habit for insertion: create the new node, set its next, and only then redirect the pointer that should now lead to it — new links first, old links last.