Unit 2: Sorting, Searching & Linked Lists

Industry Hook — The Real-World Problem First

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:

*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

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.

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

* O(1) if tail pointer maintained. ** Assumes tail pointer. † Must traverse to find predecessor.

Lab Program Implementations

Python
class Node:
    """A single node in the linked list."""
    def __init__(self, data):
        self.data = data
        self.next = None


class SinglyLinkedList:
    """Complete singly linked list with all operations.
    
    Industry parallel: Spotify's playlist is essentially this —
    each song node points to the next song in the queue.
    """
    def __init__(self):
        self.head = None
        self.size = 0

    # ─── TRAVERSAL ───
    def display(self):
        """Traverse and print all elements. O(n)."""
        current = self.head
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" → ".join(elements) + " → NULL")

    # ─── SEARCH ───
    def search(self, key):
        """Search for a value. Returns position (0-indexed) or -1.
        Time: O(n) — must traverse sequentially, no random access."""
        current = self.head
        position = 0
        while current:
            if current.data == key:
                return position
            current = current.next
            position += 1
        return -1  # Not found

    # ─── INSERT AT BEGINNING ── O(1) ───
    def insert_at_head(self, data):
        """Insert new node at the beginning. O(1).
        Like adding a song to the top of your Spotify queue."""
        new_node = Node(data)
        new_node.next = self.head  # Point to old head
        self.head = new_node        # Update head to new node
        self.size += 1

    # ─── INSERT AT END ── O(n) ───
    def insert_at_tail(self, data):
        """Insert new node at the end. O(n) — must traverse to last node."""
        new_node = Node(data)
        if not self.head:           # Empty list
            self.head = new_node
            self.size += 1
            return
        current = self.head
        while current.next:         # Traverse to last node
            current = current.next
        current.next = new_node     # Link last node to new node
        self.size += 1

    # ─── INSERT AFTER A VALUE ── O(n) search + O(1) insert ───
    def insert_after(self, target_value, data):
        """Insert after the first node containing target_value."""
        current = self.head
        while current:
            if current.data == target_value:
                new_node = Node(data)
                new_node.next = current.next  # New points to current's next
                current.next = new_node       # Current points to new
                self.size += 1
                return True
            current = current.next
        print(f"Value {target_value} not found.")
        return False

    # ─── DELETE AT HEAD ── O(1) ───
    def delete_at_head(self):
        """Remove the first node. O(1)."""
        if not self.head:
            print("List is empty.")
            return None
        removed_data = self.head.data
        self.head = self.head.next   # Move head forward
        self.size -= 1
        return removed_data

    # ─── DELETE BY VALUE ── O(n) ───
    def delete_by_value(self, key):
        """Delete first node with given value. O(n).
        Like removing a specific song from your playlist."""
        if not self.head:
            print("List is empty.")
            return False
        # Special case: deleting the head
        if self.head.data == key:
            self.head = self.head.next
            self.size -= 1
            return True
        # General case: find the node BEFORE the target
        current = self.head
        while current.next:
            if current.next.data == key:
                current.next = current.next.next  # Skip over target
                self.size -= 1
                return True
            current = current.next
        print(f"Value {key} not found.")
        return False


# === Driver Code ===
playlist = SinglyLinkedList()

# Build playlist
playlist.insert_at_tail("Shape of You")
playlist.insert_at_tail("Blinding Lights")
playlist.insert_at_tail("Tum Hi Ho")
playlist.insert_at_head("Kesariya")       # Add to top
playlist.insert_after("Shape of You", "Levitating")

print("Playlist:")
playlist.display()

print(f"\nSearch 'Tum Hi Ho': position {playlist.search('Tum Hi Ho')}")
print(f"Search 'Despacito': position {playlist.search('Despacito')}")

playlist.delete_by_value("Blinding Lights")
print("\nAfter removing 'Blinding Lights':")
playlist.display()
print(f"Size: {playlist.size}")

C
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

/* Create a new node */
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) { printf("Memory allocation failed!\n"); exit(1); }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

/* Display the list */
void display(struct Node* head) {
    struct Node* curr = head;
    while (curr) { printf("%d -> ", curr->data); curr = curr->next; }
    printf("NULL\n");
}

/* Search for a value — returns position or -1 */
int search(struct Node* head, int key) {
    struct Node* curr = head;
    int pos = 0;
    while (curr) {
        if (curr->data == key) return pos;
        curr = curr->next;
        pos++;
    }
    return -1;
}

/* Insert at head — O(1) */
void insertAtHead(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *head;   // Point to old head
    *head = newNode;          // Update head pointer
}

/* Insert at tail — O(n) */
void insertAtTail(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (!*head) { *head = newNode; return; }
    struct Node* curr = *head;
    while (curr->next) curr = curr->next;
    curr->next = newNode;
}

/* Delete by value — O(n) */
int deleteByValue(struct Node** head, int key) {
    if (!*head) return 0;
    // Deleting head
    if ((*head)->data == key) {
        struct Node* temp = *head;
        *head = (*head)->next;
        free(temp);           // CRITICAL in C — prevent memory leak!
        return 1;
    }
    struct Node* curr = *head;
    while (curr->next) {
        if (curr->next->data == key) {
            struct Node* temp = curr->next;
            curr->next = temp->next;  // Skip over target
            free(temp);
            return 1;
        }
        curr = curr->next;
    }
    return 0;
}

int main() {
    struct Node* head = NULL;
    insertAtTail(&head, 10);
    insertAtTail(&head, 20);
    insertAtTail(&head, 30);
    insertAtHead(&head, 5);

    printf("List: "); display(head);
    printf("Search 20: pos %d\n", search(head, 20));

    deleteByValue(&head, 20);
    printf("After delete 20: "); display(head);
    return 0;
}

Python
class DNode:
    """Node for doubly linked list — has both prev and next."""
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None


class DoublyLinkedList:
    """Complete DLL — the backbone of browser history and undo systems.
    
    Key advantage over SLL: Given a node reference, you can delete it
    in O(1) because you have the prev pointer. In SLL, you'd need O(n)
    to find the predecessor.
    """
    def __init__(self):
        self.head = None
        self.tail = None    # Maintaining tail for O(1) tail operations
        self.size = 0

    # ─── DISPLAY FORWARD ───
    def display_forward(self):
        curr = self.head
        parts = []
        while curr:
            parts.append(str(curr.data))
            curr = curr.next
        print("NULL ◀ " + " ◀▶ ".join(parts) + " ▶ NULL")

    # ─── DISPLAY BACKWARD (impossible with SLL!) ───
    def display_backward(self):
        curr = self.tail
        parts = []
        while curr:
            parts.append(str(curr.data))
            curr = curr.prev
        print("NULL ◀ " + " ◀▶ ".join(parts) + " ▶ NULL")

    # ─── SEARCH ── O(n) ───
    def search(self, key):
        curr = self.head
        pos = 0
        while curr:
            if curr.data == key:
                return pos
            curr = curr.next
            pos += 1
        return -1

    # ─── INSERT AT HEAD ── O(1) ───
    def insert_at_head(self, data):
        new_node = DNode(data)
        if not self.head:     # Empty list
            self.head = self.tail = new_node
        else:
            new_node.next = self.head   # New points forward to old head
            self.head.prev = new_node   # Old head points back to new
            self.head = new_node         # Update head
        self.size += 1

    # ─── INSERT AT TAIL ── O(1) with tail pointer ───
    def insert_at_tail(self, data):
        new_node = DNode(data)
        if not self.tail:     # Empty list
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail   # New points back to old tail
            self.tail.next = new_node   # Old tail points forward to new
            self.tail = new_node         # Update tail
        self.size += 1

    # ─── INSERT AFTER A VALUE ── O(n) search + O(1) insert ───
    def insert_after(self, target, data):
        curr = self.head
        while curr:
            if curr.data == target:
                new_node = DNode(data)
                new_node.prev = curr           # Step 1: new.prev → curr
                new_node.next = curr.next      # Step 2: new.next → curr.next
                if curr.next:                  # Step 3: if next exists
                    curr.next.prev = new_node  #   next.prev → new
                else:
                    self.tail = new_node        #   new is the new tail
                curr.next = new_node           # Step 4: curr.next → new
                self.size += 1
                return True
            curr = curr.next
        print(f"'{target}' not found.")
        return False

    # ─── DELETE A NODE ── O(1) given the node ───
    def _delete_node(self, node):
        """Internal: delete a specific node. O(1).
        This is the DLL superpower — SLL needs O(n) for this."""
        if node.prev:
            node.prev.next = node.next    # Prev skips over node
        else:
            self.head = node.next          # Deleting head
        if node.next:
            node.next.prev = node.prev    # Next's prev skips over node
        else:
            self.tail = node.prev          # Deleting tail
        self.size -= 1

    # ─── DELETE BY VALUE ── O(n) search + O(1) delete ───
    def delete_by_value(self, key):
        curr = self.head
        while curr:
            if curr.data == key:
                self._delete_node(curr)
                return True
            curr = curr.next
        print(f"'{key}' not found.")
        return False

    # ─── DELETE AT HEAD ── O(1) ───
    def delete_at_head(self):
        if not self.head: return None
        data = self.head.data
        self._delete_node(self.head)
        return data

    # ─── DELETE AT TAIL ── O(1) with tail pointer ───
    def delete_at_tail(self):
        if not self.tail: return None
        data = self.tail.data
        self._delete_node(self.tail)
        return data


# === Driver Code: Browser History ===
print("=== Browser History (DLL) ===")
history = DoublyLinkedList()
history.insert_at_tail("google.com")
history.insert_at_tail("github.com")
history.insert_at_tail("stackoverflow.com")
history.insert_at_tail("leetcode.com")

print("Forward: ")
history.display_forward()
print("Backward (hitting Back button): ")
history.display_backward()

print(f"\nSearch 'github.com': position {history.search('github.com')}")

history.insert_after("github.com", "docs.github.com")
print("\nAfter inserting 'docs.github.com' after 'github.com':")
history.display_forward()

history.delete_by_value("stackoverflow.com")
print("\nAfter deleting 'stackoverflow.com':")
history.display_forward()
print(f"Size: {history.size}")

C
#include <stdio.h>
#include <stdlib.h>

struct DNode {
    int data;
    struct DNode* prev;
    struct DNode* next;
};

struct DNode* createDNode(int data) {
    struct DNode* n = (struct DNode*)malloc(sizeof(struct DNode));
    n->data = data; n->prev = NULL; n->next = NULL;
    return n;
}

void displayForward(struct DNode* head) {
    printf("NULL <-> ");
    while(head) { printf("%d <-> ", head->data); head = head->next; }
    printf("NULL\n");
}

void insertHead(struct DNode** head, int data) {
    struct DNode* n = createDNode(data);
    n->next = *head;
    if(*head) (*head)->prev = n;
    *head = n;
}

void insertTail(struct DNode** head, int data) {
    struct DNode* n = createDNode(data);
    if(!*head) { *head = n; return; }
    struct DNode* curr = *head;
    while(curr->next) curr = curr->next;
    curr->next = n;
    n->prev = curr;
}

int deleteByValue(struct DNode** head, int key) {
    struct DNode* curr = *head;
    while(curr) {
        if(curr->data == key) {
            if(curr->prev) curr->prev->next = curr->next;
            else *head = curr->next;          // Deleting head
            if(curr->next) curr->next->prev = curr->prev;
            free(curr);
            return 1;
        }
        curr = curr->next;
    }
    return 0;
}

int search(struct DNode* head, int key) {
    int pos = 0;
    while(head) {
        if(head->data == key) return pos;
        head = head->next; pos++;
    }
    return -1;
}

int main() {
    struct DNode* head = NULL;
    insertTail(&head, 10);
    insertTail(&head, 20);
    insertTail(&head, 30);
    insertHead(&head, 5);
    displayForward(head);
    printf("Search 20: pos %d\n", search(head, 20));
    deleteByValue(&head, 20);
    printf("After delete 20: "); displayForward(head);
    return 0;
}

Industry Case Studies

Chapter Project — "Build It Yourself"

Interview Corner — "Crack It at Google/Amazon"

Python
def reverse_list(head):
    """Reverse by redirecting all next pointers.
    Uses three pointers: prev, current, next_node."""
    prev = None
    current = head
    
    while current:
        next_node = current.next   # Save next (would be lost)
        current.next = prev        # Reverse the pointer
        prev = current              # Move prev forward
        current = next_node         # Move current forward
    
    return prev  # prev is the new head

List: 1 → 2 → 3 → NULL

Step 1: prev=NULL, curr=1, next=2  →  1→NULL     prev=1, curr=2
Step 2: prev=1,    curr=2, next=3  →  2→1→NULL   prev=2, curr=3  
Step 3: prev=2,    curr=3, next=NULL → 3→2→1→NULL prev=3, curr=NULL

Return prev (node 3) = new head. Result: 3 → 2 → 1 → NULL ✓

Python
def has_cycle(head):
    """Floyd's Tortoise and Hare algorithm.
    Two pointers: slow (1 step), fast (2 steps).
    If they meet → cycle exists. If fast reaches NULL → no cycle.
    """
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next           # Move 1 step
        fast = fast.next.next       # Move 2 steps
        if slow == fast:
            return True            # They met — cycle!
    return False                  # Fast reached end — no cycle

Python
def merge_sorted(list1, list2):
    """Merge two sorted lists. Like merge step of merge sort.
    Uses a dummy head to simplify edge cases."""
    dummy = Node(0)   # Dummy node avoids special-case for empty result
    tail = dummy
    
    while list1 and list2:
        if list1.data <= list2.data:
            tail.next = list1      # Append smaller node
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next
    
    # Append remaining nodes (one list might not be empty)
    tail.next = list1 if list1 else list2
    
    return dummy.next  # Skip dummy, return real head

MCQ Assessment Bank — 25 Questions

Level 1 — Recall ⭐ (5 Questions)

Level 2 — Conceptual Understanding ⭐⭐ (6 Questions)

Level 3 — Application ⭐⭐ (8 Questions)

Level 4 — Analysis & Tradeoff ⭐⭐⭐ (6 Questions)

Chapter Summary

Master Comparison Table

* Amortized with dynamic array. ** O(1) with tail pointer. † O(1) if deleting head. ‡ Given a node reference.

Coming Up Next: Unit 3 — Stacks, Queues & Recursion

You now understand how linked lists enable O(1) insertion and deletion. But what if you need a disciplined data structure — one where elements can only enter and exit from specific ends? Imagine Swiggy's order processing system: 50,000 orders come in per hour during peak dinner time (7-9 PM IST). Each order must be processed in the order it arrived (First-In-First-Out). But the system also needs to "undo" the last payment if a card is declined (Last-In-First-Out).

In Unit 3, we'll build stacks (LIFO — like Paytm's transaction rollback) and queues (FIFO — like Swiggy's order pipeline) using both arrays and linked lists. We'll convert mathematical expressions using Polish notation, solve the Tower of Hanoi, and implement Merge Sort and Quick Sort using recursion. These structures are everywhere — from function calls in your CPU to undo buttons in every app you use.