Lesson 03 of 16 · 17:04
Linked lists
A linked list stores values in separate nodes connected by references. You cannot jump to index i; you must follow links from a known node. In exchange, inserting or removing a known node changes only a few references and does not shift the rest of the collection.
Linked-list interview questions test precision more than syntax. Draw the nodes, name the references that will be lost if overwritten, and decide whether a dummy node can turn a special head case into the ordinary case.
What you should be able to do after this lesson
- Reason about edges instead of indices
- Preserve references before rewiring
- Use sentinels to remove head and tail special cases
The mental model
A node is not an index. You reach it only by following links, but once you hold the right node references, local insertion and deletion can be constant time.
Recognize it when: Use list-pointer techniques for in-place reversal, cycle detection, merge/reorder tasks, and positions defined relative to the head or tail.
The invariant to say aloud: Before changing a link, save every node you still need. After changing it, the processed chain is valid and the unprocessed chain remains reachable.
Learn the ideas one at a time
Concept 1 of 4
Singly linked
Watch from 0:00 ↗Each node stores a value and next pointer. Head insertion is O(1); indexed access and tail discovery are O(n) unless an extra pointer is maintained.
Each node knows only its successor. A head insertion is O(1), but finding the kth node or the tail requires walking one edge at a time. Deleting after a known predecessor is O(1); finding that predecessor may still be O(n). Keep those two costs separate.
Walk through an example
For A → B → C, inserting X after A requires X.next = B and A.next = X. The final chain is A → X → B → C, and no other node moves.
In an interview
State whether you are given the node, its predecessor, or only the head. That detail changes the real complexity of deletion.
Concept 2 of 4
Doubly linked
Watch from 0:00 ↗Each node also points backward. Given the node, deletion can reconnect prev and next in O(1), at the cost of extra memory and twice the link maintenance.
A doubly linked node points both forward and backward. Given a node, its two neighbors can be reconnected directly, which makes deletion and reverse traversal convenient. The tradeoff is extra memory and more invariants: every forward link should agree with the corresponding backward link.
Walk through an example
Deleting B from A ⇄ B ⇄ C sets A.next = C and C.prev = A. If B is at an edge, a sentinel can stand in for the missing neighbor.
In an interview
When mutating, verify both directions. Updating next without the matching prev produces a list that works in one traversal direction and fails in the other.
Concept 3 of 4
Local rewiring
Watch from 0:00 ↗Insertion changes a small number of edges. The hard part is update order: capture the original successor before overwriting next.
Pointer algorithms are safest when treated as a small graph rewrite. First capture every edge you will still need, then create the new edges. In reversal, next_node = current.next must happen before current.next = previous or the unseen suffix becomes unreachable.
Walk through an example
Reverse A → B → C: save B, point A to null, advance to B; save C, point B to A, advance to C; point C to B. The previous pointer always heads the reversed prefix.
In an interview
Say the invariant aloud: previous is the fully reversed prefix, current is the first unprocessed node, and the saved next pointer protects the remaining suffix.
Concept 4 of 4
Sentinels
Watch from 0:00 ↗A dummy head or tail turns edge cases into ordinary link updates. It is especially useful for merges and deletions where the real head may change.
A sentinel is a deliberately fake boundary node. It gives the first real node a predecessor, so deletion, merging, and construction can use the same assignment at every position. The returned head is usually dummy.next, not the dummy itself.
Walk through an example
To remove values from [2, 2, 3], place dummy before the first 2. The predecessor can remain at dummy while matching nodes are skipped, then connect directly to 3.
In an interview
Reach for a dummy node when the real head may change. It usually replaces branching with one stable predecessor invariant.
Before you call this lesson done
- Draw the nodes and arrows
- Save references before overwriting
- Separate traversal cost from local mutation cost
- Return the real head after using a sentinel
