1.4Linked lists
The idea
A linked list stores each element in a node that points to the next one; there is no random access.
Think of it like this: A treasure hunt where each clue tells you where the next clue is.
Why it exists
Pointer manipulation (reversal, deletion, middle) is the core of code-reading questions.
How it works
- To reverse: keep prev, cur, next.
- Save next, point cur back to prev, then advance both.
- Slow and fast pointers find the middle and detect cycles.
- Deleting a node needs its predecessor in a singly linked list.
Worked example: Reverse 1 → 2 → 3 → 4
Three pointers walk along; each step flips one arrow. After four rounds head = 4 and the list reads 4 → 3 → 2 → 1 in O(n) time and O(1) space.
Now play with it
- →Step through the reversal and watch the next pointers flip.
- →Read the comparison table for singly vs doubly linked costs.
- prev = NULL, cur = head
- save next = 2
- reverse the link: node 1 now points to NULL
- advance: prev = 1, cur = 2
- save next = 3
- reverse the link: node 2 now points to 1
- advance: prev = 2, cur = 3
- save next = 4
- reverse the link: node 3 now points to 2
- advance: prev = 3, cur = 4
- save next = NULL
- reverse the link: node 4 now points to 3
- advance: prev = 4, cur = NULL
- head = prev = 4. The list is reversed in O(n) time and O(1) space.
| Task | Singly linked | Doubly linked |
|---|---|---|
| Insert after a known node | O(1) | O(1) |
| Delete a known node | O(n) (find predecessor) | O(1) |
| Insert / delete at head | O(1) | O(1) |
| Delete the tail | O(n) | O(1) with a tail pointer |
| Search by value | O(n) | O(n) |
| Access the k-th element | O(k) | O(k) |
| Find the middle | O(n), one pass with slow and fast pointers | same |
| Detect a cycle | O(n) time, O(1) space (Floyd) | same |
Check yourself
Deleting the last node of a singly linked list (no tail pointer) takes
Exam notes (the dense version)
Each node holds data and a pointer. Insert or delete at a known position is O(1), but finding the position is O(n); there is no random access. Deleting a node needs its predecessor in a singly linked list, but not in a doubly linked list. Classic tasks: reverse a list (three pointers), find the middle (slow and fast pointers), detect a cycle (Floyd), merge two sorted lists.
Previous year questions: Arrays, Stacks, Queues & Linked Lists (14)
PYQs are grouped by topic, so this is the full set for Arrays, Stacks, Queues & Linked Lists; try the ones that match this subtopic. Open all 14 on the topic page.