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.