Data Structures & Algorithms: Industry Edition
Unit 2: Sorting, Searching & Linked Lists
Singly linked lists, doubly linked lists, header linked lists — with real examples from Spotify India, Google Docs, and the Linux Kernel.
🏢 Real Projects | 💻 2 Lab Programs (Python + C) | 📝 25 MCQs | 🎯 3 Interview Questions
Industry Hook — The Real-World Problem First
🎵 The Spotify India Problem: 100 Million Songs, One Playlist at a Time
Spotify India has over 80 million users and a library of 100+ million tracks. When you create a playlist and hit "Add to Queue," "Remove Song," or "Shuffle," something fascinating happens behind the scenes.
If playlists were stored as arrays, inserting a song in the middle of a 500-song playlist would require shifting up to 499 elements — O(n) per operation. Do this 10 times per second across 80 million users, and you need 400 billion element-shifts per second. No server farm on Earth handles that.
Instead, Spotify's playlist engine uses a structure where:
- Adding a song at any position takes O(1) — just rewire two pointers
- Removing a song takes O(1) — unlink the node, done
- Moving songs around (drag-and-drop reorder) is O(1) per move
- Playing next/previous is O(1) — follow the forward or backward pointer
The same structure powers Google Docs (undo/redo history), the Linux kernel (process scheduling), and every browser's back/forward button.
This is exactly the problem linked lists solve. Let's understand how.
Concept Explanation — Theory, Earned
2.1 The Array Problem: Why We Need Linked Lists
In Unit 1, we learned that arrays give us O(1) random access. But arrays have a fatal flaw:
| Operation | Array | Linked List | Winner |
|---|---|---|---|
| Access by index | O(1) ✅ | O(n) ❌ | Array |
| Insert at beginning | O(n) ❌ | O(1) ✅ | Linked List |
| Insert at middle | O(n) ❌ | O(1)* ✅ | Linked List |
| Delete any element | O(n) ❌ | O(1)* ✅ | Linked List |
| Memory allocation | Contiguous (rigid) | Scattered (flexible) | Linked List |
| Memory overhead | None | Extra pointer per node | Array |
*O(1) once you have a reference to the position. Finding the position is O(n).
2.2 Singly Linked List
Layer 1 — Intuition
Imagine a treasure hunt where each clue card has two things: the treasure at that location, and directions to the next clue. You must follow clues in order — you can't jump to clue #7 directly. But adding a new clue in the middle is easy: just change the "next clue" direction on one card.
Layer 2 — Visual: Memory Representation
Memory Layout
head
│
▼
┌──────────────┐ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐
│ data: "Tum │───▶│ data: "Hi" │───▶│ data: "Se" │───▶│ data: "Pyaar"│───▶ NULL
│ next: 0x2000 │ │ next: 0x3000 │ │ next: 0x5000 │ │ next: NULL │
│ addr: 0x1000 │ │ addr: 0x2000 │ │ addr: 0x3000 │ │ addr: 0x5000 │
└──────────────┘ └──────────────┘ └──────────────┘ └──────────────┘
Key insight: Nodes can be ANYWHERE in memory (0x1000, 0x2000, 0x3000, 0x5000).
They are NOT contiguous like arrays. The 'next' pointer links them.
Insertion at Beginning — O(1)
Visual
Before: head → [10] → [20] → [30] → NULL
Step 1: Create new node [5]
Step 2: new_node.next = head (point to old first node)
Step 3: head = new_node (update head)
After: head → [5] → [10] → [20] → [30] → NULL
Only 2 pointer changes! No shifting!
Deletion of a Node — O(1) when you have the previous node
Visual
Before: head → [10] → [20] → [30] → NULL
Delete node with value 20:
Step 1: Find node before 20 (node with 10) ← This is O(n)
Step 2: prev.next = target.next ← This is O(1)
Step 3: Free/delete the target node
After: head → [10] → [30] → NULL
The node [20] is "unlinked" — it still exists in memory but
nothing points to it. In C, you must free() it. In Python,
garbage collector handles it.
Layer 3 — Complexity Table
| Operation | Best | Average | Worst | Space |
|---|---|---|---|---|
| Access by index | O(1) | O(n) | O(n) | O(1) |
| Search by value | O(1) | O(n) | O(n) | O(1) |
| Insert at head | O(1) | O(1) | O(1) | O(1) |
| Insert at tail | O(n) | O(n) | O(n) | O(1) |
| Insert after a given node | O(1) | O(1) | O(1) | O(1) |
| Delete head | O(1) | O(1) | O(1) | O(1) |
| Delete by value (search + delete) | O(1) | O(n) | O(n) | O(1) |
| Traversal | O(n) | O(n) | O(n) | O(1) |
The Linux kernel uses linked lists so heavily that it has its own custom implementation: struct list_head. Every process in Linux is a node in a doubly linked list. The kernel's task_struct uses linked lists for the process list, run queue, wait queue, children list, and sibling list — all simultaneously!
2.3 Header Linked Lists
A header linked list has a special header node at the beginning that doesn't store actual data. It stores metadata (like count, or a sentinel value) and simplifies insertion/deletion logic because you never have to handle the "empty list" or "insert at head" as special cases.
Grounded Header Linked List
Visual
header
│
▼
┌────────────┐ ┌─────┐ ┌─────┐ ┌─────┐
│ count: 3 │───▶│ 10 │───▶│ 20 │───▶│ 30 │───▶ NULL ← Grounded (ends at NULL)
│ (sentinel) │ │ │ │ │ │ │
└────────────┘ └─────┘ └─────┘ └─────┘
Advantage: Inserting before the "first real node" is just inserting
after the header — no special case needed!
Circular Header Linked List
Visual
header
│
▼
┌────────────┐ ┌─────┐ ┌─────┐ ┌─────┐
│ count: 3 │───▶│ 10 │───▶│ 20 │───▶│ 30 │──┐
│ (sentinel) │ │ │ │ │ │ │ │
└────────────┘ └─────┘ └─────┘ └─────┘ │
▲ │
└──────────────────────────────────────────┘ ← Last node points BACK to header
Traversal ends when we reach the header node again.
Used in: Circular buffers, round-robin scheduling, game turn management.
Header nodes eliminate edge cases. Without a header, every insert/delete function needs if (head == NULL) or if (target == head) checks. With a header, the first real element is always header->next, and you always insert/delete "after some node" — uniform logic, fewer bugs.
2.4 Two-Way (Doubly) Linked List
Layer 1 — Intuition
A singly linked list is like a one-way street — you can only go forward. A doubly linked list is a two-way street — you can go forward AND backward. This is how your browser's Back/Forward buttons work: each page knows both the previous page and the next page.
Layer 2 — Visual
Memory Layout
head tail
│ │
▼ ▼
NULL ◀── ┌──────┐ ◀──▶ ┌──────┐ ◀──▶ ┌──────┐ ◀──▶ ┌──────┐ ──▶ NULL
│ 10 │ │ 20 │ │ 30 │ │ 40 │
│ prev │ │ prev │ │ prev │ │ prev │
│ next │ │ next │ │ next │ │ next │
└──────┘ └──────┘ └──────┘ └──────┘
Each node has THREE fields:
1. data — the actual value
2. prev — pointer to previous node (NULL for head)
3. next — pointer to next node (NULL for tail)
DLL Insertion After a Given Node — O(1)
Visual
Insert 25 after node [20]:
Before: ... ◀──▶ [20] ◀──▶ [30] ◀──▶ ...
Step 1: Create [25]
Step 2: [25].next = [20].next → [25] points forward to [30]
Step 3: [25].prev = [20] → [25] points backward to [20]
Step 4: [30].prev = [25] → [30]'s back pointer updated
Step 5: [20].next = [25] → [20]'s forward pointer updated
After: ... ◀──▶ [20] ◀──▶ [25] ◀──▶ [30] ◀──▶ ...
4 pointer changes. Constant time. No shifting.
Layer 3 — DLL Complexity Table
| Operation | Singly LL | Doubly LL | Why DLL is better |
|---|---|---|---|
| Insert at head | O(1) | O(1) | Same |
| Insert at tail | O(n)* | O(1)** | DLL with tail pointer |
| Delete given node | O(n)† | O(1) | DLL has prev pointer — no need to find predecessor |
| Traverse backward | Impossible | O(n) | prev pointer enables reverse traversal |
| Memory per node | data + 1 ptr | data + 2 ptrs | SLL uses less memory |
* O(1) if tail pointer maintained. ** Assumes tail pointer. † Must traverse to find predecessor.
Google Docs uses a doubly linked list for its undo/redo stack. Every edit creates a node with prev pointing to the state before the edit and next pointing to the state after. "Undo" follows prev; "Redo" follows next. Why is a DLL better than two separate stacks for this? (Hint: think about what happens when you undo 5 times, then make a new edit.)