Linked Lists

A chain of nodes, not a block of memory — O(1) splicing, O(n) access, and the pointer tricks that make both safe

Nodes, not blocksvalue + next, chained one to the next
O(1) spliceinsert/delete at a known node, any list length
Two directionsa doubly linked list walks either way
Reverse in one passthree pointers, no extra list allocated

1.Singly linked list — node with value + next

Instead of one contiguous block like a list, a singly linked list is a chain of separate nodes — each one holds its own value plus a pointer to the NEXT node, ending in None.

Key features

A node is a small object with exactly two fields: value (the data) and next (a reference to the following node, or None)
head is the only entry point — lose the reference to it, and every node after it becomes unreachable, even though the nodes themselves still exist
The last node's next is None — that is what tells a traversal loop when to stop

A linked list is a chain of nodes, not a block of memory — head is the only way in, and every node is only reachable by following .next from something that came before it.

2.Doubly linked list — node with prev + next

A doubly linked list node carries TWO pointers instead of one — next forward and prev backward — so the list can be walked in either direction.

Key features

Removing a known node needs only that node's own .prev and .next — no separate search for its predecessor, unlike a singly linked list
The extra .prev pointer costs one more reference per node in memory — the classic space-for-capability trade
collections.deque is internally a doubly linked list of fixed-size blocks — that mechanism is exactly what gives it O(1) operations at both ends

A doubly linked list trades one extra pointer per node for O(1) removal of any known node, and the ability to walk backward — a singly linked list gives you neither.

3.Why linked lists give O(1) insert/delete at a known position but O(n) access by index

Inserting or deleting at a node you already have a reference to is just relinking a couple of pointers — O(1), no matter how long the list is. Reaching the k-th node has no shortcut: the only way in is to walk from the head, one .next at a time — O(n).

Key features

Insert after a known node: create the new node pointing at the old next, then point the known node at the new node — two pointer writes, regardless of list length
linked_list[5] has no meaning as an O(1) operation — getting to the 5th node costs walking through nodes 0 through 4 first, exactly like any other traversal
The O(1) insert/delete only holds if you already HAVE a reference to the position — finding that position by index or by value is itself O(n), which is easy to forget when reasoning about total cost

A linked list trades O(n) random access for O(1) insert/delete at a node you already hold a reference to — and always relink the new node's own pointer before you overwrite the old one.

4.Reversing a linked list (iterative and recursive)

Reversing means walking the list once, and at each node, flipping .next to point BACKWARD instead of forward — three variables track this: prev (the reversed portion built so far), curr (the node being flipped), and a saved copy of curr.next so the forward link is not lost the moment it is overwritten.

Key features

The three-variable dance (prev, curr, next_node) is the same shape whether written iteratively or recursively — recursion just uses the call stack instead of a loop to hold curr as it unwinds
The new head of the reversed list is the OLD tail — prev ends up pointing at whatever used to be the last node, which is what the function returns
Save curr.next BEFORE reassigning curr.next — reversing the order of those two lines is the single most common bug in this algorithm

Save curr.next before you touch it, flip curr.next to point at prev, then advance both prev and curr — do those three steps in any other order and the rest of the list is lost.

5.Detecting a cycle (Floyd's fast/slow pointer)

Move two pointers through the list at different speeds — one node at a time, and two nodes at a time. If they ever land on the same node, the list loops back on itself; if the fast one hits the end first, it does not.

Key features

This is the same two-speed pointer idea from the Two Pointers section, applied specifically to a linked list rather than an array
slow is fast is a correct identity check here — nodes are objects, and the algorithm cares whether the two pointers have converged on the same node, not whether their values happen to match
O(1) extra space is the whole point — a set of visited nodes would also detect a cycle, but at O(n) space instead

fast moves two nodes for every one of slow's — if a cycle exists, that gap can only shrink to zero, never skip past it, so they are guaranteed to meet.

6.Finding the middle of a list in one pass

Move a slow pointer one node at a time and a fast pointer two nodes at a time — when fast reaches the end, slow is standing exactly halfway, without ever counting the list's length.

Key features

No need to count the length first and walk it again — a length-then-walk approach also works, but costs two passes instead of one
On an EVEN-length list, this lands on the SECOND of the two middle nodes — a well-known, expected trait of this exact loop shape, not a bug
The loop condition is "while fast and fast.next" — the same guard cycle detection uses, so it never dereferences None

fast covers twice the distance slow does — when fast runs out of list, slow is standing exactly halfway, in one pass, no length count needed.

7.Merging two sorted linked lists

Walk both sorted lists at once, always splicing the smaller of the two current nodes onto the result and advancing that list — the same two-pointer merge idea used on arrays, but relinking existing nodes instead of copying values into a new one.

Key features

A dummy node sidesteps "which list's head wins?" as a special case — the merge always attaches to dummy.next first, then the result is read off that afterward
Once one list runs out, the rest of the OTHER list is already sorted — tail.next = a if a else b attaches whatever remains in one line, no further comparisons needed
This reuses the existing nodes from both input lists — nothing is copied, so it runs in O(1) extra space beyond the dummy node itself

Splice the smaller head onto the result and advance that list — reuse the nodes that already exist instead of building new ones, and a dummy node removes the "which head goes first?" special case.

8.Removing the Nth node from the end (two-pointer with a gap)

Send fast n steps ahead first, then move fast and slow together, one step at a time, keeping that n-node gap. When fast falls off the end, slow is sitting exactly one node before the one that needs removing.

Key features

A dummy node placed before head is what makes removing the head itself (n equals the list length) work with no special case — see the dummy/sentinel concept
slow needs to stop at the node BEFORE the one being removed, not the node itself — that is why the gap is opened to n, not n - 1, when starting from dummy
The classic off-by-one to watch: whether the gap-opening loop runs n or n + 1 times depends on whether slow starts at dummy or at head — mixing conventions is the most common source of bugs here

Open an n-node gap from a dummy node, walk both pointers together until fast runs out, then skip over slow.next — the dummy node is what makes removing the head itself work like every other case.

9.Dummy/sentinel head node trick (avoids edge-case branching)

Create one throwaway node that points at the real head, and do every insert/delete relative to IT instead of head directly — that way, removing or inserting at the head needs no special case, because there is always a real node before whatever position you are working on.

Key features

Without a dummy node, removing or inserting AT the head needs its own special-cased branch, because there is no real node before it to relink — with a dummy, that special case disappears
dummy.next is the answer to return — it is always the current real head, whether or not the head has changed since dummy was created
The dummy node itself is thrown away at the end — it never appears in the returned list, it only exists to give the algorithm somewhere to stand before node 1

A dummy node one slot before head turns "is this the head?" from a branch you have to write into a case that just falls out of the same code as everything else.

Spotted a mistake on this page? Tell us.

Read Sheet