Algocraft · Theory

Linked Lists: no index, just pointers

An array gives you arr[i] — jump straight to any element in O(1). A linked list gives up that shortcut entirely; the only way to reach a node is to walk there one link at a time. What you get in exchange is O(1) insert and delete anywhere you already have a pointer to, with no shifting of anything else. The entire skill of linked lists is keeping track of the right node references at the right moment — get that right and the rest is bookkeeping.

01 · Foundation

Arrays vs. linked lists — the actual trade-off

An array stores everything in one contiguous block, so the machine can compute the address of arr[i] directly — O(1) random access. The cost shows up the moment you insert or delete in the middle: every element after that point has to physically shift over to close (or open) the gap. That's O(n), even though the "logical" change was just one item.

A linked list flips both of those. Each node only knows about its neighbor(s) — there's no formula that gets you from "index" to "memory address," so reaching an arbitrary position means walking from the head, one .next at a time: O(n) just to arrive. But once you're standing at the right node, insertion or deletion is O(1) — it's nothing but re-pointing a couple of links. Nothing else in the list has to move.

The trade you're making: arrays are fast to reach into but expensive to rearrange; linked lists are expensive to reach into but essentially free to rearrange once you're there. Pick the structure based on which operation your problem actually does more of.

02 · Simplification

The dummy/sentinel head trick

Here's a nuisance that shows up in almost every linked-list problem: inserting or deleting at the very front of the list is a special case. Every other insert/delete works by taking the node before your target and re-pointing its .next — but the head has no node before it. So naive code ends up with an if (index == 0) branch that rewires the head variable itself, separate from the general-case logic.

The fix: add one fake node in front of the real head, and never treat it as real data. Now every position in the list — including position 0 — has a node before it (the dummy), so the exact same "find prev, relink prev.next" logic handles every case uniformly. No special-casing the head.

This is why you'll see linked-list solutions starting with a line like:

dummy = Node()
dummy.next = head
prev = dummy      # always has a "before"
# ... do the general-case logic ...
head = dummy.next # unwrap at the end

At the end, the real (possibly new) head is just dummy.next — the dummy itself gets discarded.

03 · Visualizing the surgery

Watching a reversal happen, one flip at a time

Reversing a linked list is the clearest way to see "pointer surgery" in action. The nodes themselves never move — only the direction their .next link points changes, one node at a time, as three pointers (prev, curr, next) sweep down the list.

Nodes never move — only the direction of each .next link changes. In the middle snapshot, next was saved before node 3's link gets overwritten, which is exactly why it still points at node 4 even as curr.next is about to flip to point at prev instead.

04 · Method

A repeatable framework

Almost every linked-list problem — reversal, insertion, deletion, LRU eviction — falls out of the same five habits.

1 Consider a dummy/sentinel headIf the problem involves inserting or deleting at position 0, a dummy node almost always removes the special case — see the section above.
2 Save the "before" pointer firstBefore you modify any link, make sure you already hold a reference to the node before the one you're changing. Once you overwrite a .next, whatever it used to point to is gone unless you saved it.
3 For reversal: three pointers, in orderTrack prev, curr, and next explicitly. Save next before you overwrite curr.next, flip curr.next to point at prev, then advance all three pointers forward.
4 List + hashmap = two different jobsWhen a problem combines a list with a hashmap (LRU Cache), the hashmap gives O(1) lookup of a node by key, and the list gives O(1) reordering/eviction. Neither structure alone gives you both.
5 Trace it on paper firstDraw a tiny 3-4 node example before writing code. Nearly every linked-list bug boils down to "which pointer did I overwrite before saving it."

05 · Worked example

Reversing `1 → 2 → 3 → 4`, step by step

The loop body is always the same four lines: next = curr.next; curr.next = prev; prev = curr; curr = next — repeated until curr is null. Below are the values of all three pointers at the top of each iteration.

step	prev	curr	next
1	null	1	2
2	1	2	3
3	2	3	4
4	3	4	null

After step 4, curr becomes null and the loop stops — but prev is now sitting on node 4, which is exactly the new head. Reading the "curr" column top to bottom (1, 2, 3, 4) shows which node gets relinked on each pass; reading the final state of every node's .next gives you 4 → 3 → 2 → 1 → null. Open the Reverse a Linked List visualizer to watch this exact walk animate.

06 · Combining structures

LRU Cache — combining two structures

Primary: Linked Lists (this page) Secondary: Hashmap — full combo breakdown

A Least-Recently-Used cache needs two operations to both be fast, and they're fast for completely different reasons:

O(1) lookup by key — given a key, find its node instantly. A hashmap does this: key → node reference.
O(1) reorder / evict — move the accessed node to the "most recent" end, or drop the node at the "least recent" end, without walking the whole structure. A doubly-linked list does this: with a pointer straight to the node, you can unlink it from the middle in O(1) (you need both neighbors' links, hence doubly-linked) and splice it in at the front.

The two operations, concretely:

get(key) — look the node up in the hashmap in O(1), then move that node to the front of the list (the most-recently-used end).
put(key, value) — if the key exists, update it and move it to the front, same as get. If it's new and the cache is at capacity, remove the node at the back of the list (the least-recently-used end) — and remove it from the hashmap too — before inserting the new node at the front.

This is precisely why LRU Cache needs both structures: a hashmap alone can tell you a node exists, but it has no concept of order, so it can't tell you what to evict. A linked list alone can maintain order perfectly, but finding a node by key would mean walking the whole list — O(n), not O(1). Paired together, each covers the other's blind spot.

07 · Complexity

How to reason about time & space

Insert/delete at a node you already hold a pointer to — O(1). It's just re-pointing one or two links.
Reaching an arbitrary index — O(n). No random access, unlike an array — you must walk from the head.
Iterative reversal — O(n) time (one pass), O(1) extra space (three pointer variables, no matter how long the list is).
LRU Cache — O(1) time for both get and put, using O(capacity) total space for the hashmap entries and list nodes combined.

08 · Before you start coding

Common mistakes

Overwriting a node's .next before saving a reference to what it used to point to — this permanently severs the rest of the list; there's no way back.
Losing the head reference entirely while traversing — always advance a temporary pointer, never move head itself.
Forgetting to update the tail reference after deleting the last node, leaving it dangling on a node that's no longer in the list.
Not handling the empty-list or single-node edge cases — logic that quietly assumes "at least 2 nodes" breaks the moment it isn't.
For LRU Cache specifically: forgetting to move a node to the front on get (not just on put) — this silently breaks the recency ordering, and the bug won't show up until an eviction picks the wrong node.

09 · Patterns

The seven linked-list problems on this site

Each card links to the matching interactive visualizer.

Insert at head

new.next = head; head = new

O(1) insert when you already hold the head pointer — no shifting, unlike an array's insert(0, x).

Try Insert at Head →

Insert at tail

tail.next = new; tail = new

O(1) if you maintain a tail pointer; O(n) if you have to walk from the head to find the last node first.

Try Insert at Tail →

Insert at index

prev.next = new; new.next = curr

Walk to the node just before the target index — that walk is O(n), but the splice itself is O(1).

Try Insert at Index →

Delete at index

prev.next = curr.next

Bypass the target node by re-pointing its predecessor — the node itself is never touched, just skipped over.

Try Delete at Index →

Concatenate two lists

tailA.next = headB

Find the first list's tail and point it at the second list's head — O(1) with a tracked tail, O(n) without.

Try Concatenate Lists →

Reverse a list

next=curr.next; curr.next=prev; prev=curr; curr=next

The three-pointer sweep from the worked example above — one pass, O(1) extra space.

Try Reverse a List →

LRU Cache

map[key] → node, doubly-linked list for order

Hashmap for O(1) lookup, doubly-linked list for O(1) reordering and eviction — neither alone is enough.

Try LRU Cache →