Linked Lists
A Linked List is a linear data structure where elements (nodes) are stored dynamically in heap memory. Instead of contiguous addresses, each node contains a value and a pointer to the next node.
Why It Exists
Arrays have fixed sizes. Resizing them is expensive (O(N) copy). Linked lists allocate memory dynamically on-demand, allowing constant-time O(1) insertions at head or tail.
Intuition for Beginners
“Think of a treasure hunt game. Each clue is a note containing a clue value and the address of the next clue. You cannot jump to clue 5 directly; you must follow the trail from start to finish.”
Visual Explanation
Singly Linked List Node Chain: [Head: 20] ---> [Node: 10] ---> [Node: 30] ---> [Tail: Null] (Val, Next) (Val, Next) (Val, Next)
Two Pointer Movement
Place both slow and fast pointers at the head of the linked list.
Complexity Analysis
| Operation | Time Complexity | Notes |
|---|---|---|
| Access/Search | O(N) | Must traverse links sequentially |
| Insert at Head | O(1) | Adjust pointers without copying |
| Delete Node | O(1) | Bypass node link if reference is held |
| Space | O(N) | Extra memory overhead for pointer addresses |
Production & Real World Applications
- •Garbage Collectors: Tracking memory allocations inside list tables.
- •Undo/Redo History: Doubly linked pointer references to previous states.
Algorithmic Patterns
Using tortoise and hare pointers to identify cycles or middle nodes.
Iteratively updating three pointer states (prev, curr, next) to flip node orders.
Defending the Design (Interview Q&A)
Common Traps & Mistakes
- ⚠️NullPointerExceptions (forgetting to check if `curr.next` is null before accessing).
- ⚠️Creating cyclic infinite loops during updates.