Intuition First: A Treasure Hunt#
A linked list is a treasure hunt. Each clue gives you one piece of information and tells you where to find the next clue. You can't jump straight to clue #5. You have to follow the chain from the start, hopping from one location to the next. An array is the opposite: every item sits at a known house number, so you can teleport directly to item #5 without visiting the others.
That single difference, follow the chain versus jump to an index, explains everything that follows: why a linked list makes inserting and deleting cheap (just rewrite a clue), and why it makes random access slow (you must walk the whole chain to reach the middle).
What Is a Linked List?#
A linked list is a linear data structure where each element (called a node) stores two things:
- Its value
- A pointer to the next node
Unlike arrays, linked list nodes are not stored contiguously in memory. They are scattered and connected by these pointers.
Arrays vs Linked Lists#
| Operation | Array | Linked List |
|---|---|---|
| Access by index | O(1) | O(N) |
| Insert at head | O(N) (shift everything) | O(1) |
| Insert at tail | O(1) amortized | O(N) (must traverse) |
| Delete from head | O(N) | O(1) |
| Memory layout | Contiguous | Scattered |
Linked lists work best when you frequently insert or delete at the head and don't need random access.
Implementation#
Interactive Lab#
Let's take the example of this visualization: the list 10 → 20 → 30 → 40 → 50, searching for 40. Press play and count the hops. The pointer starts at head and has to walk through 10, 20 and 30 before it can so much as look at 40. There is no jumping ahead, because no node knows where any node but its own successor lives. That walk is the O(N) access cost from the table above.
Core Operations#
Traversal: O(N)#
Start at head, follow next pointers until you reach null.
Insert at Head: O(1)#
Create a new node, point its next to the current head, update head.
Insert at Tail: O(N)#
Traverse to the last node (where next == null), attach the new node there.
Delete a Node: O(N) to find + O(1) to remove#
Find the node before the target, update its next to skip the target.
Types of Linked Lists#
Singly Linked: each node has one next pointer. Simple, less memory.
Doubly Linked: each node has prev and next. Allows backward traversal; used in browsers (back/forward history).
Circular Linked: the tail's next points back to the head. Used in round-robin schedulers.
Key Applications#
- Undo/redo in text editors (doubly linked)
- Browser history navigation
- Implementing stacks and queues (prepend/append operations)
- Hash map chaining: each bucket is a linked list of collisions
What to Remember#
Linked lists trade O(1) random access (arrays) for O(1) head insertion and deletion. Use them when your workload is heavy on insertions/deletions and light on index lookups. Many advanced data structures (stacks, queues, adjacency lists for graphs) are built on linked lists under the hood.