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 excel when you frequently insert or delete at the head and don't need random access.
Implementation#
Interactive Lab#
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
Key Takeaway#
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.