Linked List - (Theory)

1. Introduction to Linked Lists

Definition: Linear data structure where elements (nodes) are linked via pointers.
Key Components:
- Node: Contains data + pointer(s) to next/previous nodes.
- Head: First node in the list.
- Tail: Last node in the list.

2. Types of Linked Lists

Singly Linked List
- Each node points only to the next node.
```
class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }
}
```
- Operations TC/SC:
  - Insertion: O(1) at head, O(n) at tail
  - Deletion: O(1) at head, O(n) at tail
  - Search/Traverse: O(n) time, O(1) space
Doubly Linked List
- Nodes point to both next and previous nodes.
```
class DoublyNode {
    int data;
    DoublyNode next, prev;
    DoublyNode(int data) { this.data = data; }
}
```
- Operations TC/SC:
  - Insertion/Deletion at ends: O(1)
  - Traversal: O(n) time, O(1) space

Circular Linked List

Singly Circular: Last node points back to head.
Doubly Circular: Last ↔ Head bidirectional.

// Singly Circular: Insertion
void insertHead(Node head, int data) {
    Node newNode = new Node(data);
    if (head == null) {
        newNode.next = newNode; // Self-loop
        head = newNode;
    } else {
        newNode.next = head.next;
        head.next = newNode;
    }
}

Operations TC/SC:
- Insertion/Deletion at ends: O(1)
- Traversal: O(n) time, O(1) space

3. Core Operations & Traversals

Common Operations (Singly Linked List)

public class SinglyLinkedList {
    Node head;

    // Insert at head (TC: O(1), SC: O(1))
    void insertHead(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Insert at tail (TC: O(n), SC: O(1))
    void insertTail(int data) {
        Node newNode = new Node(data);
        if (head == null) head = newNode;
        else {
            Node curr = head;
            while (curr.next != null) curr = curr.next;
            curr.next = newNode;
        }
    }

    // Delete by value (TC: O(n), SC: O(1))
    void delete(int key) {
        if (head == null) return;
        if (head.data == key) {
            head = head.next;
            return;
        }
        Node curr = head, prev = null;
        while (curr != null && curr.data != key) {
            prev = curr;
            curr = curr.next;
        }
        if (curr == null) return; // Key not found
        prev.next = curr.next;
    }

    // Search (TC: O(n), SC: O(1))
    boolean search(int key) {
        Node curr = head;
        while (curr != null) {
            if (curr.data == key) return true;
            curr = curr.next;
        }
        return false;
    }

    // Traversal (TC: O(n), SC: O(1))
    void traverse() {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }
}

Doubly Linked List Operations

public class DoublyLinkedList {
    DoublyNode head, tail;

    // Insert at head (TC: O(1), SC: O(1))
    void insertHead(int data) {
        DoublyNode newNode = new DoublyNode(data);
        if (head == null) head = tail = newNode;
        else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    // Delete at tail (TC: O(1), SC: O(1))
    void deleteTail() {
        if (tail == null) return;
        if (head == tail) head = tail = null;
        else {
            tail = tail.prev;
            tail.next = null;
        }
    }
}

4. Key Patterns & Template Code

Pattern 1: Two Pointers (Fast & Slow)

Use Cases: Middle node, cycle detection, palindrome check.

Template:

Node slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;        // Moves 1 step
    fast = fast.next.next;   // Moves 2 steps
}
return slow; // Middle node

TC: O(n), SC: O(1)

Pattern 2: Reverse Linked List

Iterative (TC: O(n), SC: O(1)):

Node reverse(Node head) {
    Node prev = null, curr = head;
    while (curr != null) {
        Node next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev; // New head
}

Pattern 3: Cycle Detection (Floyd’s Algorithm)

Template:

boolean hasCycle(Node head) {
    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;
}

TC: O(n), SC: O(1)

Pattern 4: Merge Two Sorted Lists

Template (TC: O(n+m), SC: O(1)):

Node merge(Node l1, Node l2) {
    Node dummy = new Node(-1);
    Node curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.data < l2.data) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Pattern 5: Remove Duplicates (Sorted List)

Template (TC: O(n), SC: O(1)):

void removeDuplicates(Node head) {
    Node curr = head;
    while (curr != null && curr.next != null) {
        if (curr.data == curr.next.data) 
            curr.next = curr.next.next;
        else 
            curr = curr.next;
    }
}

5. Advanced Patterns

Palindrome Check:
- Steps:
  1. Find middle (slow/fast pointers).
  2. Reverse second half.
  3. Compare both halves.
- TC: O(n), SC: O(1)

Add Two Numbers:

Node addTwoNumbers(Node l1, Node l2) {
    Node dummy = new Node(0);
    Node curr = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        if (l1 != null) { sum += l1.data; l1 = l1.next; }
        if (l2 != null) { sum += l2.data; l2 = l2.next; }
        carry = sum / 10;
        curr.next = new Node(sum % 10);
        curr = curr.next;
    }
    return dummy.next;
}

TC: O(max(m, n)), SC: O(max(m, n))

Intersection of Two Lists:
- Approach:
  1. Find lengths of both lists.
  2. Align pointers to same start.
  3. Traverse until nodes match.
- TC: O(m + n), SC: O(1)

6. Complexity Summary

Operation	Singly LL	Doubly LL	Circular LL
Insertion (Head)	O(1)	O(1)	O(1)
Insertion (Tail)	O(n)	O(1)	O(1)
Deletion (Head)	O(1)	O(1)	O(1)
Deletion (Tail)	O(n)	O(1)	O(n)
Search	O(n)	O(n)	O(n)
Traversal	O(n)	O(n)	O(n)

7. Full Template (Singly Linked List)

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }
}

public class LinkedList {
    Node head;
    
    // Insert at head
    void insertHead(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }
    
    // Insert at tail
    void insertTail(int data) {
        Node newNode = new Node(data);
        if (head == null) head = newNode;
        else {
            Node curr = head;
            while (curr.next != null) curr = curr.next;
            curr.next = newNode;
        }
    }
    
    // Delete by value
    void delete(int key) {
        if (head == null) return;
        if (head.data == key) head = head.next;
        else {
            Node curr = head, prev = null;
            while (curr != null && curr.data != key) {
                prev = curr;
                curr = curr.next;
            }
            if (curr != null) prev.next = curr.next;
        }
    }
    
    // Reverse (Iterative)
    void reverse() {
        Node prev = null, curr = head;
        while (curr != null) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        head = prev;
    }
    
    // Detect cycle
    boolean hasCycle() {
        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;
    }
    
    // Find middle node
    Node findMiddle() {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

Key Takeaways:

Patterns: Two pointers, reversal, cycle detection, merging, and traversal are foundational.
TC/SC: Most operations are O(n) time and O(1) space except recursion.
Use Cases: Dynamic memory allocation, stacks/queues, adjacency lists for graphs.