Linked Lists
Dynamic memory allocation, O(1) insertion, cycle detection, reversal — linked lists appear in nearly every GATE CS paper. Master the pointer manipulations and classic algorithms.
Last updated: April 2026 | GATE CS 2024–2026 syllabus
Key Takeaways
- Linked list nodes store data + pointer(s) to next (and prev for doubly linked). Not contiguous in memory — no O(1) random access.
- Singly: one pointer (next). Doubly: two pointers (prev, next). Circular: last node points to head.
- Insert/delete at head: O(1). At tail (without tail pointer): O(n). At arbitrary position given pointer: O(1).
- Reversal (iterative): O(n) time, O(1) space — use three pointers prev/curr/next.
- Floyd’s cycle detection: slow + fast pointers. If cycle exists they meet. Cycle start found by resetting slow to head.
- Middle node: slow-fast pointer. Middle of merge sort split. Merge two sorted lists: O(m+n).
- Doubly linked list allows O(1) deletion given a pointer to the node — singly linked needs O(n) to find prev.
1. Types of Linked Lists
| Type | Structure | Extra Space | Backward Traversal |
|---|---|---|---|
| Singly linked | data | next | 1 pointer/node | No |
| Doubly linked | prev | data | next | 2 pointers/node | Yes, O(1) |
| Circular (singly) | Last node next = head | 1 pointer/node | No |
| Circular (doubly) | Both head and tail circular | 2 pointers/node | Yes |
On a 64-bit system, ptr_size = 8 bytes.
2. Operations and Complexity
| Operation | Singly LL | Doubly LL | Array |
|---|---|---|---|
| Access element i | O(n) | O(n) | O(1) |
| Insert at head | O(1) | O(1) | O(n) |
| Insert at tail | O(n) / O(1) with tail ptr | O(1) with tail ptr | O(1) amortised |
| Insert after node p | O(1) | O(1) | O(n) |
| Delete head | O(1) | O(1) | O(n) |
| Delete node p (given ptr) | O(n) — find prev | O(1) | O(n) |
| Search | O(n) | O(n) | O(n) / O(log n) sorted |
Key insight for GATE: Doubly linked list gives O(1) deletion of a given node because prev is stored. Singly linked list requires O(n) to traverse to the predecessor.
3. List Reversal
Iterative Reversal (Singly Linked List)
Loop while curr ≠ NULL:
next = curr.next
curr.next = prev
prev = curr
curr = next
New head = prev
Time: O(n) Space: O(1)
Recursive Reversal
if node.next == NULL: return node (new head)
newHead = reverse(node.next)
node.next.next = node
node.next = NULL
return newHead
Time: O(n) Space: O(n) (call stack)
GATE prefers iterative for space efficiency. Recognise that after reversal, the old head becomes the new tail (its next = NULL) and the old tail becomes the new head.
4. Floyd’s Cycle Detection Algorithm
slow = fast = head
while fast ≠ NULL and fast.next ≠ NULL:
slow = slow.next
fast = fast.next.next
if slow == fast: cycle exists, break
Phase 2 — Find cycle start:
Reset slow = head (fast stays at meeting point)
while slow ≠ fast:
slow = slow.next
fast = fast.next
Cycle starts at slow (= fast)
Time: O(n) Space: O(1)
Why it works
If cycle length is C and the cycle starts at distance D from head, when they first meet, slow has taken D + k steps inside the cycle. Setting slow back to head and advancing both by 1 makes them meet at the cycle start after exactly D more steps. GATE frequently asks to trace this or state the meeting position.
5. Merge Two Sorted Linked Lists
if l1 == NULL: return l2
if l2 == NULL: return l1
if l1.data ≤ l2.data:
l1.next = merge(l1.next, l2); return l1
else:
l2.next = merge(l1, l2.next); return l2
Time: O(m+n) Space: O(m+n) recursive / O(1) iterative
Used as the merge step in merge sort on linked lists. Merge sort on linked lists runs in O(n log n) time with O(log n) space (no extra array needed unlike array merge sort).
6. Slow-Fast Pointer Techniques
| Problem | Technique | Result |
|---|---|---|
| Find middle node | slow+1, fast+2 | slow at middle when fast at end |
| Find k-th from end | fast leads by k steps | slow at k-th from end when fast at NULL |
| Detect cycle | slow+1, fast+2 | Meet inside cycle if cycle exists |
| Find cycle start | Reset slow to head after meeting | Advance both +1, meet at start |
| Check palindrome | Find middle, reverse second half, compare | O(n) time, O(1) space |
7. GATE CS Solved Examples
Example 1 — Pointer after deletion (GATE CS 2019)
Q: In a singly linked list with n nodes, what is the time complexity of deleting a node whose pointer is given (not head, not tail)?
Answer: O(n). Even though we have the node pointer, we cannot set its predecessor’s next pointer without traversing from the head to find the predecessor. Exception: copy the next node’s data to this node and delete next — then O(1), but this fails for tail nodes.
Example 2 — Floyd’s cycle start (GATE CS 2016)
Q: A linked list has 6 nodes (1→2→3→4→5→6→3, cycle from 6 back to 3). Where do slow and fast pointers first meet?
Solution: Cycle starts at node 3, length = 4 (3,4,5,6). D = 2 (nodes before cycle). Slow enters cycle at step 2. Fast is at position 2×2 = 4 (mod 4 within cycle: position 4 = node 4… let’s trace: step 0: both at 1. Step 1: slow=2, fast=3. Step 2: slow=3, fast=5. Step 3: slow=4, fast=3. Step 4: slow=5, fast=5. Meet at node 5.
Example 3 — Merge sort on linked list (GATE CS 2014)
Q: What is the space complexity of merge sort on a linked list of n elements?
Answer: O(log n) for the recursion stack (splitting at middle each time). No auxiliary array is needed because merging linked lists can be done in-place by relinking pointers.
8. Common Mistakes
Mistake 1 — Losing the list during reversal
Forgetting to save next before overwriting curr.next. Always: next = curr.next, then curr.next = prev.
Mistake 2 — Fast pointer NULL check
In Floyd’s, check fast != NULL && fast.next != NULL before advancing. Missing one causes a null-pointer error on even-length lists without cycles.
Mistake 3 — O(1) deletion given pointer in singly LL
The “copy-next” trick (copy next node’s data here, delete next) achieves O(1) but fails for the last node. State this limitation in GATE answers.
Mistake 4 — Middle of even-length list
Slow-fast gives the second middle for even n. If GATE asks for “first middle”, adjust: advance fast only while fast.next != NULL and fast.next.next != NULL.
Mistake 5 — Circular list infinite loop
Traversal on a circular linked list without a termination condition loops forever. Always terminate when current == head (for exactly one full traversal).
9. FAQ
How does Floyd’s cycle detection algorithm work?
Slow (+1) and fast (+2) pointers. If a cycle exists, they meet inside it in O(n). Reset slow to head, advance both +1; they meet at the cycle start.
What is the time complexity of reversing a linked list?
O(n) time. Iterative: O(1) space. Recursive: O(n) space. GATE prefers the iterative version.
How do you find the middle of a linked list in one pass?
Slow (+1) and fast (+2). When fast reaches the end, slow is at the middle. O(n) time, O(1) space.
What are the advantages of a doubly linked list over a singly linked list?
O(1) deletion given a node pointer (prev is stored). O(1) backward traversal. Trade-off: double the pointer storage per node.