Module 6: Linked List

Linked Lists teach one of the most important skills in DSA:
thinking in terms of pointers and references instead of indexes.

Most candidates fail linked list questions not because the logic is hard, but because they lose track of links.
This module builds that confidence step by step.

Singly Linked List

What is a Singly Linked List?

A singly linked list is a collection of nodes where:

• Each node contains data
• Each node points to the next node

Structure:

[data | next] → [data | next] → null

Node Definition (Java)

class Node {
    int data;
    Node next;
}

Basic Operations

• Insertion (head, tail, position)
• Deletion
• Traversal
• Searching

Traversal Example

Node curr = head;
while(curr != null){
    System.out.print(curr.data + " ");
    curr = curr.next;
}

Key Insight

No random access.
Traversal is always O(n).

Doubly Linked List

What is a Doubly Linked List?

Each node stores:

• Data
• Pointer to next node
• Pointer to previous node

Structure:

null ← [prev | data | next] ⇄ [prev | data | next] → null

Advantages

• Bidirectional traversal
• Easier deletion
• Used in LRU cache

Trade-Off

• Extra memory for prev pointer

Used in:

• Browser history
• Undo/redo operations

Circular Linked List

What is a Circular Linked List?

Last node points back to the head instead of null.

Structure:

head → node → node → head

Benefits

• Efficient rotation
• No null pointers
• Continuous traversal

Used in:

• Scheduling algorithms
• Multiplayer games
• Round-robin systems

Fast & Slow Pointer Technique

Core Idea

Use two pointers:

• Slow moves one step
• Fast moves two steps

Why It Works

Fast pointer reaches end earlier, helping detect patterns.

Used for:

• Cycle detection
• Finding middle
• Palindrome check

Reverse Linked List (Multiple Ways)

Method 1: Iterative Approach

Node prev = null;
Node curr = head;

while(curr != null){
    Node nextNode = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextNode;
}
head = prev;

Method 2: Recursive Approach

Node reverse(Node head){
    if(head == null || head.next == null)
        return head;

    Node newHead = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

Key Learning

Always store next before changing pointers.

Detect Cycle (Floyd’s Algorithm)

Problem

Determine if a linked list contains a loop.

Floyd’s Cycle Detection

• Fast and slow pointers
• If they meet → cycle exists

Node slow = head, fast = head;
while(fast != null && fast.next != null){
    slow = slow.next;
    fast = fast.next.next;
    if(slow == fast) return true;
}
return false;

Time: O(n)
Space: O(1)

Find Middle of Linked List

Approach

Fast & slow pointer.

Node slow = head, fast = head;
while(fast != null && fast.next != null){
    slow = slow.next;
    fast = fast.next.next;
}

• Slow pointer ends at middle

Used in:

• Merge sort on linked list
• Palindrome problems

Merge Two Sorted Linked Lists

Concept

Merge nodes by comparing values.

Node dummy = new Node(0);
Node tail = dummy;

while(l1 != null && l2 != null){
    if(l1.data < l2.data){
        tail.next = l1;
        l1 = l1.next;
    } else {
        tail.next = l2;
        l2 = l2.next;
    }
    tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;

Time: O(n + m)
Space: O(1)

Intersection Point of Linked Lists

Problem

Two linked lists intersect at some node.

Optimal Approach

• Find lengths
• Align starting points
• Traverse together

Alternative:

• Two pointers switching heads

Node a = headA, b = headB;
while(a != b){
    a = (a == null) ? headB : a.next;
    b = (b == null) ? headA : b.next;
}
return a;

Elegant and interview favorite.

LRU Cache (Advanced)

What is LRU Cache?

Stores most recently used items and removes least recently used.

Operations:

• get(key)
• put(key, value)

Data Structures Used

• HashMap for O(1) access
• Doubly Linked List for O(1) updates

Why Doubly Linked List?

• Easy knowing which node is least recently used
• Quick removal and insertion

High-Level Logic

• On access, move node to front
• On overflow, remove tail

This problem combines:

• Linked List
• HashMap
• Design thinking

Common Linked List Mistakes

• Losing head reference
• Not updating pointers properly
• Null pointer exceptions
• Infinite loops in circular lists