Free lesson · DSA Mastery - Interview Prep, End to End
Introduction to Linked Lists
Introduction to Linked Lists
A linked list is the first data structure in this course that abandons contiguous memory. Where an array stores elements side by side and reaches any of them by index arithmetic, a linked list scatters its elements anywhere in memory and threads them together with pointers - each node holds a value and a reference to the next node. That single change - replacing "the next element is at i+1" with "the next element is wherever this node points" - reshapes everything about how you traverse, insert, delete, and reason about the structure.
This introduction lays out the node model, the trade-offs against arrays, the pointer-manipulation discipline that every linked-list problem demands, and the three technique families this module is organized around: basic pointer surgery, in-place reversal, and fast-and-slow pointers.
What a Linked List Is
A singly linked list is a chain of nodes. Each node stores a value and a single pointer, next, to the following node. The list is identified by a reference to its first node, the head. The last node's next is null, marking the end.
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
To visit every element you start at the head and follow next until you hit null. There is no random access: reaching the fifth node means walking through the first four. This is the defining cost - and the defining freedom - of the structure.
graph LR
H["head"] --> A["1 | next"]
A --> B["2 | next"]
B --> C["3 | next"]
C --> D["null"]
style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style D fill:#dc2626,stroke:#ef4444,color:#f1f5f9
This diagram shows a singly linked list. A head reference points to the first node holding value one, which points to a node holding two, then three, and finally to null marking the end. Each node stores a value and a pointer to the next node.
Interactive animation: A value, a pointer, nothing else.
Why Linked Lists Exist: The Array Trade-off
Arrays give O(1) random access but pay for it at the edges: inserting or deleting at the front (or middle) requires shifting every later element, an O(n) operation. Linked lists invert this. There's no index arithmetic, so reaching position k is O(k) - but once you hold a pointer to a node, splicing a new node in or cutting one out is O(1): you just rewire a couple of next pointers, no shifting.
| Operation | Array | Singly Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert/delete at head | O(n) | O(1) |
| Insert/delete after a known node | O(n) | O(1) |
| Search by value | O(n) | O(n) |
| Memory per element | value only | value + pointer |
The linked list trades random access for cheap structural edits. That's why it shines in problems about rearranging a sequence - reversing, merging, partitioning, reordering - and struggles in problems about indexing into one.
Interactive animation: What a list buys, and what it pays - Each node also pays for its pointer: value plus next, against value only.
Variants You'll Encounter
- Singly linked: one
nextpointer per node. The default in this module and most interview problems. - Doubly linked: each node also has a
prevpointer, enabling backward traversal and O(1) deletion given only the node. Used where the problem needs it - Design Linked List, Flatten a Multilevel List, and the circular-list insertion problem. - Circular: the last node points back to the head (or some node) instead of null, forming a loop. Appears in circular-list problems and, accidentally, as the cycle that fast-and-slow pointers detect.
This module uses the singly linked ListNode above as its canonical type, introducing prev only where a problem genuinely requires a doubly linked node.
Interactive animation: The only way in is to walk.
The Pointer-Manipulation Discipline
Every linked-list bug comes from the same family of mistakes: losing a reference before you've used it, dereferencing null, or rewiring pointers in the wrong order. Three habits prevent almost all of them.
Save before you overwrite. When you're about to change a node's next, first store whatever you might still need. The canonical reversal step - nextNode = cur.next; cur.next = prev; prev = cur; cur = nextNode; - saves cur.next before clobbering it, because once cur.next is reassigned, the rest of the list is unreachable through cur.
Use a dummy (sentinel) head. Many operations special-case the head: deleting the first node, inserting before the first, merging from empty. A dummy node placed before the real head means the head is no longer special - every node has a predecessor you can rewire. You return dummy.next at the end. This single trick eliminates a whole class of edge-case branches.
Draw the pointers. Before writing the rewiring code, sketch the nodes and arrows, then sketch the desired after-state. The code is just the sequence of pointer assignments that transforms one into the other. Linked-list problems are visual; solving them on paper first is faster than debugging them in your head.
graph TD
A["About to rewire cur.next?"] --> B["Save cur.next first"]
B --> C["Then reassign cur.next"]
D["Head might be special-cased?"] --> E["Add a dummy node before head"]
E --> F["Return dummy.next"]
style A fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style B fill:#16a34a,stroke:#10b981,color:#f1f5f9
style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
This diagram summarizes two core habits. Before reassigning a node's next pointer, save the old next so the rest of the list stays reachable. And when the head might be special-cased, add a dummy node before it so every real node has a predecessor, returning dummy-dot-next at the end.
Interactive animation: Three habits, almost no bugs - The reversal step saves cur.next before flipping it - habit one, in one line.
The Three Technique Families
This module is organized around the patterns that solve the vast majority of linked-list problems.
Basic pointer surgery (15.2–15.19). Splicing, deleting, merging, partitioning, and rearranging nodes by careful next rewiring. This is where you build fluency with the dummy-head trick, two-pointer gaps (for "nth from end"), and traversal-with-a-trailing-pointer. The bulk of the module lives here because it's the foundation everything else builds on.
In-place reversal (15.20–15.24). Reversing all or part of a list using O(1) extra space by walking the list and flipping each next pointer backward. The three-pointer prev / cur / next dance is one of the most important micro-patterns in all of interviewing, and it scales up to reversing sublists and reversing in k-sized groups.
Fast and slow pointers (15.25–15.28). Moving two pointers at different speeds to find the middle, detect a cycle, or locate a cycle's entrance - Floyd's tortoise-and-hare. The same idea even escapes linked lists entirely to solve Happy Number, where the "list" is an implicit sequence of computed values.
Interactive animation: Delete = one rewired arrow.
When to Reach for a Linked List
In interviews you rarely choose a linked list - the problem hands you one. The skill is recognizing which technique family a given linked-list problem calls for:
- Rearranging or removing nodes by position or value → pointer surgery, usually with a dummy head.
- Anything involving reversing, or comparing the list against its reverse (palindrome) → in-place reversal.
- Finding the middle, detecting or locating a loop, or any "two speeds" insight → fast and slow pointers.
The unifying thread is that you almost never need extra data structures or O(n) space - the elegance of linked-list solutions comes from manipulating the existing pointers directly, in place.
A Note on Testing Your Code Mentally
Because linked lists are pointer-based, the cheapest way to verify a solution is to trace it on a tiny example - two or three nodes - drawing the pointer state after each line. Most off-by-one and null-dereference bugs surface immediately on a list of length 0, 1, or 2. Throughout this module, every algorithm is accompanied by a frame-by-frame pointer trace for exactly this reason: seeing the arrows move is how linked-list intuition is built.
Let's begin with the basics. The first problem, Intersection of Two Linked Lists, is a gentle but clever introduction to multi-pointer traversal - finding where two lists merge using nothing but two walking pointers and a beautiful length-equalizing trick.