After covering the foundations and recursion/backtracking, it's time to study one of the most useful dynamic data structures in competitive programming: the linked list.
Linked lists are not flashy. They don't offer random access like arrays, and they don't always win on raw speed. But they excel at flexible insertion, deletion, and pointer-based problem solving — and they double as a training ground for the kind of careful, invariant-driven thinking that shows up everywhere else in CP.
Let's build the idea from the ground up.
What Is a Linked List?
A linked list is a linear data structure used to store records, where elements — called nodes — are connected using pointers rather than sitting in contiguous memory.
Each node typically contains:
- data — the value being stored
- a pointer to the next node
The last node points to NULL (or nullptr, depending on the language), signalling the end of the list.
Key properties:
- It can grow or shrink dynamically, without reallocating a whole block of memory
- It doesn't require contiguous memory — nodes can live anywhere in the heap
- It trades that flexibility for extra memory spent on pointers
A Real-World Analogy
Think of a treasure hunt. Each clue tells you where to find the next one. You don't need every clue laid out side by side — you just follow the chain, one step at a time. That's the spirit of a linked list.
Why Use a Linked List?
Linked lists shine when:
- Frequent insertion and deletion are required, especially in the middle of the structure
- The total size of the data isn't known in advance
- You want to avoid the cost of shifting elements, which arrays require on insert/delete
Main operations: insert, delete.
Auxiliary operations: delete the full list, count the nodes, get the nth element.
Linked List vs Array
Arrays and linked lists are optimised for different things, and understanding the trade-off is the whole point of learning both.
Array
- Memory is allocated as one contiguous block
- Access by index is O(1) — direct memory address calculation
- Inserting or deleting in the middle costs O(n), because every subsequent element must shift
Dynamic Array (like Python's list or C++'s vector)
- Expands by allocating a larger block and copying existing elements over
- Typically grows by a multiplicative factor (often 2×) when full
- This is the same amortized analysis from Session 1 — most appends are O(1), but a resize is O(n)
Linked List
- No contiguous memory required — nodes can be scattered across the heap
- Insertion and deletion are O(1) if you already have a pointer to the right position
- Accessing a specific element is O(n) because you must traverse node by node — there's no jumping to "index 5"
- Extra memory is spent on pointers (one for singly linked, two for doubly linked)
The trade-off in one line: arrays win on indexing, linked lists win on structural flexibility.
Complexity at a Glance
Operation Linked List Array
─────────────────────────────────────────────────────────────────────────────
Access ith element O(n) O(1)
Insert at start O(1) O(n)
Insert at end O(n) without tail, O(1) with tail O(1) amortized
Delete at start O(1) O(n)
Delete in middle O(n) to find + O(1) to unlink O(n) to shift
The key takeaway: a linked list avoids shifting elements, but it pays for that flexibility with slower traversal. There is no free lunch — you're choosing which operation gets to be fast.
Types of Linked Lists
Singly Linked List
Each node points only to the next node. This is the most common and simplest form — easy to implement, memory-efficient, and the default choice unless you specifically need backward traversal.
Supports insertion and deletion at the start, end, or middle, though operations at the end require either a tail pointer or a full traversal.
Doubly Linked List
Each node stores two pointers — one to the next node, one to the previous node.
Advantage: traversal in both directions, and deletion of a known node becomes O(1) without needing to find its predecessor first.
Disadvantage: more memory per node, and every insertion or deletion requires updating two sets of pointers instead of one.
Useful whenever backward traversal matters — for example, implementing an undo feature or a browser's back/forward navigation.
Circular Linked List
The last node points back to the first node instead of to NULL. There is no natural "end."
Particularly useful in rotation-based problems and queue-style simulations — anything that cycles back to the beginning, like round-robin scheduling.
Special Linked List Variants
These aren't essential for beginner CP, but they're worth knowing about once the fundamentals are solid.
Memory-Efficient (XOR) Doubly Linked List
Instead of storing two separate pointers, a memory-efficient doubly linked list stores the XOR of the previous and next node's addresses in a single field. Traversal direction is recovered by XOR-ing the stored value with the address of the node you came from.
This halves the pointer overhead of a standard doubly linked list, but it's significantly trickier to implement and debug — not something you want to encounter for the first time mid-contest.
Unrolled Linked List
An unrolled linked list stores a small block of multiple elements inside each node, rather than just one. The nodes themselves are still linked together.
Benefits: better cache performance (since several elements sit together in memory), and reduced pointer overhead relative to the amount of data stored — often genuinely faster in practice than a standard linked list.
Trade-off: insertions and deletions are more complex, since each node must maintain a roughly balanced number of elements.
Skip List
A skip list is a probabilistic alternative to a balanced binary search tree. It maintains multiple "levels" of forward pointers, where higher levels skip over larger chunks of the list — allowing search to jump ahead instead of checking every node.
Why it's interesting: average-case search, insert, and delete are all O(log n), and the implementation is considerably simpler than a self-balancing tree like a Red-Black tree or AVL tree.
Trade-off: more pointer storage per node, and the performance guarantee is probabilistic rather than strict.
Common Linked List Problem Patterns
This is where linked lists become genuinely useful to study — these patterns recur across a huge range of CP and interview problems.
Traversing the List
Since there's no index-based access, reaching the nth element means walking node by node. The most common approaches: traverse once while counting nodes, use two pointers moving at different speeds, or use a hash table when repeated lookups are needed.
Detecting a Cycle
A linked list can accidentally — or intentionally, in a problem — contain a loop.
The brute-force approach stores every visited node in a hash table; seeing a repeated node confirms a cycle. It works, but costs O(n) extra space.
Floyd's Cycle Detection (the "tortoise and hare") does it in O(1) space: a slow pointer advances one step at a time, a fast pointer advances two. If the list has a cycle, the fast pointer will eventually lap the slow one and they'll meet. If the fast pointer reaches NULL, there's no cycle. This is one of the most famous tricks in all of linked list problems, and it generalises to detecting cycles in functional graphs too.
Finding the Middle
Two common methods: count the total nodes first, then traverse to n/2 — or use the same slow/fast pointer trick from cycle detection. When the fast pointer reaches the end, the slow pointer is sitting exactly at the middle. Elegant, and reusable across several other problems on this list.
Determining Odd or Even Length
The fast pointer technique extends naturally here too — whether the fast pointer lands exactly on the last node or overshoots past it tells you the parity of the list's length, without ever counting nodes explicitly.
Finding the Merge Point of Two Lists
When two linked lists share a common tail (they intersect and become one list at some node), the standard approach is:
- Find the length of both lists
- Advance the pointer of the longer list forward by the length difference
- Move both pointers forward together, one step at a time
- The first node where they coincide is the merge point
This works because once both pointers are equidistant from the end, walking them together guarantees they hit the shared node simultaneously.
Merging Two Sorted Linked Lists
Given two sorted lists, merge them into one sorted list — the same idea as the merge step in merge sort, just applied to linked nodes instead of array slices. A single pointer-based comparison walks both lists, always picking the smaller current node and advancing that list's pointer.
Reversing in Pairs or Groups of k
Example: 1 → 2 → 3 → 4 becomes 2 → 1 → 4 → 3 when reversed in pairs. The same idea generalises to reversing every group of k nodes. This is an excellent exercise for practicing recursive pointer rewiring, since each group's reversal depends on correctly reconnecting to the result of reversing the next group.
Checking for a Palindrome
A linked list reads the same forward and backward. Two common approaches: push every value onto a stack while traversing, then compare against a second traversal — or find the middle, reverse the second half in place, and compare the two halves directly (more space-efficient, since it avoids the extra stack).
The Josephus Problem
A classic circular linked list problem: people stand in a circle, and every k-th person is eliminated until one remains. It's often solved through circular traversal combined with modular arithmetic, and it's a great test of whether you can reason cleanly about circular structures under elimination.
When You Need to Move Backward but Can't
Sometimes a problem hands you a pointer to the k-th node and expects you to access earlier elements — but a standard singly linked list offers no way to go backward.
A few options: maintain extra references as you traverse forward, switch to a doubly linked list if backward access is a recurring requirement, or reach for an XOR linked list in memory-constrained scenarios where the added complexity is worth the savings.
The right choice depends entirely on how often backward access is needed — a one-off lookup doesn't justify restructuring the whole list.
Why Linked List Problems Matter in CP
Linked list problems teach far more than the data structure itself. They train you to think rigorously about pointers, traversal, invariants, edge cases, and structural modification under constraints — skills that transfer directly to trees, graphs, recursion-heavy problems, and anything involving merging or restructuring data.
In other words: a small structure with an outsized learning impact.
Summary
Linked lists are dynamic, pointer-based structures, strong on insertion and deletion, weaker on random access. We covered singly, doubly, and circular linked lists, the advanced variants (XOR lists, unrolled lists, skip lists), and the problem patterns that show up again and again — cycle detection, finding the middle, merging, reversing in groups, and palindrome checking.
Final takeaways:
- Arrays win when you need fast indexing
- Linked lists win when you need structural flexibility
- Slow traversal is the price paid for cheap insertion and deletion
- The slow/fast two-pointer technique solves a surprising number of linked list problems elegantly, and is worth internalising as a reusable pattern
This series documents concepts as I learn them — follow along for each new session.
Top comments (0)