Academy
Linked Lists, Stacks & Queues

Lesson 1 of 8

Linked Lists

"I call it my billion-dollar mistake. It was the invention of the null reference in 1965." — Tony Hoare

An array is a street of identical houses, numbered and side by side: tell me the number and I walk straight to the door. A linked list is a treasure hunt. There is no street. Each stop is scattered somewhere in memory, and the only way to reach the next one is a clue — a pointer — tucked inside the one you're standing on. You cannot skip to the fifth clue; you must follow the chain from the first. That single design choice — chain instead of street — flips the entire performance profile of the structure, and understanding why is the foundation for the stacks, queues, and trees that fill the rest of this Volume. It is also, thanks to all those pointers to nothing, where you will meet Tony Hoare's billion-dollar mistake face to face.

The question this chapter answers

If arrays give you instant access by index, why would anyone chain nodes together with pointers instead — and what exactly do you gain, and give up, by doing so?

Core Concepts

A linked list is a chain of nodes, where each node holds a value and a reference to the next node. That's the whole idea. The list itself is nothing more than a variable — head — pointing at the first node; from there you follow next pointers until one of them is null, which is how you know you've reached the end.

head
 │
 ▼
[10 | •]───▶[20 | •]───▶[30 | ✕]      ✕ = null (end of list)

The crucial contrast with an array lives in memory. An array is contiguous: its elements sit in one unbroken run of cells, so the computer computes base + index × size and jumps straight there — that's why arr[9999] is as fast as arr[0]. A linked list is the opposite: its nodes are scattered anywhere the allocator found room, glued together only by the references they hold. There is no arithmetic that finds the tenth node. You have to walk.

Building and traversing a list

A node needs no special machinery — a plain object with two fields does it. To traverse, you start a cursor at head and follow next until you fall off the end into null.

JavaScript — Try it Yourself
Loading editor…
Console
Runs automatically. Edit the code to see it change.

Notice there is no .length you can read for free — you count by walking, so even asking "how big is it?" is O(n). That is the tax for giving up contiguous layout.

Everyday analogy

A scavenger hunt. Each clue tells you only where the next clue is hidden — never where clue #5 is directly. Want to reach the fifth stop? Follow the chain from the first: that's O(n) access. But splicing a new stop into the middle is trivial — you rewrite one clue to point at your new hiding spot, and hide a clue there pointing onward. No other clue moves. That is the linked list's superpower and its curse in one image: cheap to rewire, expensive to reach.

The fundamental trade-off vs arrays

Everything about linked lists follows from that image. Here is the honest ledger:

Operation Array Linked list
Access by index (random access) O(1) O(n) — must walk from head
Insert / delete at the head O(n) — shift everything O(1) — relink one pointer
Insert / delete at the tail O(1) amortized O(n), or O(1) with a tail pointer
Insert / delete at a known node O(n) — shift the rest O(1) to relink (but O(n) to find it)
Search by value O(n) O(n)
Memory contiguous, cache-friendly scattered + one pointer of overhead per node

A linked list wins when you insert and delete frequently at the ends or at nodes you already hold, when the size is unknown or wildly variable, and when you want to avoid the cost of shifting or reallocating a big array. It loses the moment you need indexing — and it loses more often than beginners expect, because of that last row. Arrays are laid out in one cache-friendly block, so a CPU streams through them fast; a linked list makes the processor chase pointers to random addresses, defeating the cache. In practice an array-based structure often beats a linked list with the identical Big-O for exactly this reason. Be honest about that in an interview — it's a senior signal.

Insert at head and tail

Inserting at the head is the linked list's party trick: point the new node at the old head, and it becomes the new head. Constant time, no shifting. Inserting at the tail without a tail pointer means walking the whole chain first — linear time.

JavaScript — Try it Yourself
Loading editor…
Console
Runs automatically. Edit the code to see it change.

That O(n) tail insert is annoying, and the fix is to remember the tail. A small class holding both head and tail pointers turns tail insertion into O(1) — you never walk again, you just relink the last node and advance tail. This is precisely how you'll build an efficient queue two chapters from now.

History changed here

Linked lists predate almost everything. In 1955–56 Allen Newell, Cliff Shaw, and Herbert Simon built IPL, a language whose entire memory model was linked lists, to power the first AI programs. Two years later John McCarthy's Lisp made the idea immortal with the cons cell: a pair of a value and a pointer to the rest — car and cdr. Your { val, next } node is a cons cell wearing modern clothes. An entire language, and a decade of AI, was built on nothing but this two-field object.

Search and delete

Searching is an honest O(n) walk — there is no shortcut on an unsorted chain. Deletion is where pointers get subtle: to remove a node you must relink the node before it, so you walk with a prev cursor trailing one step behind.

JavaScript — Try it Yourself
Loading editor…
Console
Runs automatically. Edit the code to see it change.

See that if (head.val === target) return head.next line? It exists only because the head has no predecessor to relink. Every real linked-list function grows one of these awkward special cases — and there is a classic trick to make it vanish.

The dummy (sentinel) head node

Add a fake node before the real head — a dummy or sentinel — and suddenly every node, including the first real one, has a predecessor. The head is no longer special. You delete uniformly, then return dummy.next as the (possibly new) real head. Watch the empty-list and delete-the-head cases handle themselves for free:

JavaScript — Try it Yourself
Loading editor…
Console
Runs automatically. Edit the code to see it change.

No head.val === target special case, no crash on the empty list — the sentinel absorbs both. Whenever a linked-list problem makes you nervous about the head, reach for a dummy node first. Interviewers notice.

The engineer's notebook

Habits that separate clean pointer code from buggy pointer code:

• Save before you overwrite. Before reassigning a next, ask "am I about to lose the only reference to the rest of the list?" If so, stash it in a temp first.
• Reach for a dummy head. Any time the head might change or vanish, a sentinel deletes the special case along with the bug.
• Keep a tail pointer if you insert at the end a lot — it turns an O(n) append into O(1).
• Draw the boxes and arrows on paper before you type. Two minutes of sketching prevents an hour of null-pointer debugging.

Real-world example — chika.ng Academy

You will almost never hand-write a linked list in the Academy's application code — arrays, and the MySQL tables behind Drizzle, cover the day job. But you depend on them constantly without seeing them. Every Academy page is rendered by React, and React organises its component tree as a Fiber structure whose sibling elements are a singly linked list, walked node-by-node through a .sibling pointer — the exact while (cur) cur = cur.next loop from this chapter, running thousands of times per render. The structures you learn to reason about here are the ones your framework is already running underneath you.

Common Mistakes

  • Losing the rest of the list. Writing cur.next = fresh before saving cur.next orphans everything downstream — the classic reversal bug. Always stash const after = cur.next; first.
  • Null-pointer errors at the ends. cur.next.val explodes when cur is the last node and cur.next is null. Guard with while (cur && cur.next), or use a dummy head so the boundary disappears.
  • Off-by-one in traversal. while (cur.next !== null) stops on the last node (good for appending); while (cur !== null) visits every node (good for reading). Mixing them up skips the tail or over-runs the end.
  • Forgetting to update head. When you insert at or delete the head, the head pointer itself moves. If your function doesn't return and reassign the new head, you keep pointing at a stale — or deleted — node.
  • Assuming random access. list[3] doesn't exist. Reaching the fourth node is an O(n) walk, and doing it inside a loop silently builds an O(n²) algorithm.
  • Not handling the empty list. head === null is a real, common input. Every operation needs an answer for it — which, again, a dummy head often provides for free.
Thought experiment

You have a singly linked list of one million nodes and you hold a direct reference to one node in the middle, node k. Deleting k should be O(1) — just relink around it — but you can't, because you need the node before k to do the relinking, and finding it means walking from the head: O(n). Now the clever bit: is there a way to "delete" k in true O(1) without its predecessor? Yes — copy the next node's value into k, then delete the next node instead. You didn't remove k's box; you removed its identity. When does this trick fail? (Answer: when k is the last node — there's nothing after it to copy.)

Interview Corner

Interview Corner — the same idea at three levels. Answer yours; recognise the one above it.
Junior
"What is a linked list, and how does it differ from an array?"
Model answer — "A linked list is a chain of nodes; each node holds a value and a pointer to the next node, and the list is reached through a head reference. Unlike an array it isn't stored contiguously, so I can't index into it — reaching the kth node is O(n). In exchange, inserting or deleting at the front is O(1) because I just relink a pointer instead of shifting elements."
Follow-up they'll throw: "So which is better?" → Neither — it's a trade-off. Arrays for indexing and cache-friendly scans; linked lists for cheap insert/delete at the ends and unknown size.
Intermediate
"Reverse a singly linked list in place."
Model answer — "Three pointers — prev, cur, next. Walk once; at each node save next = cur.next, flip cur.next = prev, then slide prev = cur and cur = next. When cur is null, prev is the new head. O(n) time, O(1) space. The key is saving next before overwriting cur.next, or I orphan the rest of the list."
Follow-up: "Do it recursively?" → Yes, but that's O(n) stack space — an honest downgrade from the iterative version, and it can overflow on long lists.
Senior
"Your event queue is a linked list. A colleague's is array-backed. Same Big-O everywhere, yet theirs is measurably faster under load. Why — and what do you do?"
Model answer — "Big-O hides the constant that matters here: cache locality. An array-backed queue lives in one contiguous block the CPU prefetches and streams through; my linked list scatters nodes across the heap, so every next is a cache miss — pointer chasing to random addresses — plus per-node allocation and GC pressure. Same complexity, far worse constant. The fix is a structure that keeps the ends cheap but restores locality: an array-backed ring buffer, or a chunked linked list where each node holds an array of many elements. I'd measure first, then pick based on the real access pattern."
This is a systems answer wearing an algorithms costume — the senior move is knowing that identical Big-O does not mean identical performance, and being able to say why at the hardware level.
Company lens — how the same topic gets asked
micro1Live and conversational. Narrate your pointers out loud — "save next, flip, advance" — as you code the reversal. Talking through the pointer dance is exactly what the AI interviewer is listening for.
GoogleWants rigor and edge cases: empty list, single node, and the exact space cost of iterative vs recursive. Expect "can you do it in O(1) space?" and be ready to prove it.
MetaSpeed and clean code on the canonical patterns — reverse, merge two sorted lists, detect a cycle with fast/slow pointers. They want the dummy-head and two-pointer tricks at your fingertips.
AmazonPractical and operational: when would you choose a linked list in production, and what does pointer chasing cost at scale? Tie your answer to memory, cache, and throughput.
Hands-on exercise
  1. In the editor above, extend the traversal block with a getAt(head, k) that returns the value at index k. State its time complexity out loud and explain why it can't be O(1) like an array.
  2. Write reverse(head) using the three-pointer technique, then run it on fromArray([1,2,3,4,5]) and confirm you get [5,4,3,2,1]. Say the invariant out loud: "save next before flipping."
  3. Rewrite insertTail as a small class holding both head and tail so appends are O(1). Test it, and state the new complexity.
  4. Using a dummy head, write insertSorted(head, val) that inserts into an already-sorted list keeping it sorted. Note which edge cases the sentinel made disappear.

Chapter Summary

  • A linked list is a chain of { val, next } nodes reached from a head; unlike an array, its nodes are scattered in memory and linked only by references.
  • The core trade-off: O(1) insert/delete at a known position (just relink) but O(n) random access (you must walk) — the mirror image of an array's O(1) index and O(n) middle insert.
  • Traversal, search, length, and tail-insert (without a tail pointer) are all O(n); head-insert is O(1); a tail pointer restores O(1) appends.
  • Deletion needs the previous node, so you walk with a trailing prev cursor and relink around the target.
  • The dummy/sentinel head gives every real node a predecessor, erasing the delete-the-head and empty-list special cases.
  • The signature bugs: overwriting next before saving it, dereferencing null at the ends, off-by-one traversal, and forgetting to update head when it moves.
  • Identical Big-O ≠ identical speed: arrays' cache locality often beats linked lists in practice. Be honest about it.
Narrative bridge

Our list can only ever move forward — reach a node and the one before it is gone, which is why deletion forced that awkward trailing prev cursor. What if every node knew both its neighbours? And what if the tail pointed back to the head, so the chain had no end at all? Those two ideas — a backward pointer, and a loop — unlock cheaper deletions, backward traversal, and the circular buffers behind real schedulers. That's next: Doubly & Circular Linked Lists.

Editorial reflection — beginners dismiss the linked list as a toy — "I'd just use an array." They're often right in application code, and that's fine. But the linked list is not really here to be used; it's here to teach you to think in pointers. Once you can see data as boxes joined by arrows, and can rewire those arrows without dropping anything, trees, graphs, and hash-table buckets stop being intimidating — they're all just linked nodes in fancier arrangements. Learn the humble list well, and half of data structures is already in your hands.

Enrol to track progress

Q&A · 0

Enrol to ask questions and join the discussion.

No questions yet — be the first to ask.