Linked List — Saidul Islam Rajib

1. Core Structure

A linked list stores elements as nodes connected through references
rather than contiguous memory.

flowchart LR
    H["Head"] --> A["Node A"]
    A --> B["Node B"]
    B --> C["Node C"]
    C --> N["null"]

A typical singly linked node contains:

Node {
    Value
    Next
}

Unlike arrays, random access is not O(1) because reaching the k-th
node requires traversal.

2. Linked List Variants

flowchart TD
    L["Linked List"] --> S["Singly"]
    L --> D["Doubly"]
    L --> C["Circular"]

    S --> S1["next"]
    D --> D1["prev + next"]
    C --> C1["tail → head"]

Type Forward Backward Typical Use

Singly O(1) link No Simple chains
Doubly O(1) link O(1) link LRU, deques
Circular Cyclic Depends Round-robin
Circular Doubly Cyclic Cyclic Advanced caches/deques

3. Complexity

Operation Singly Doubly

Access by index O(n) O(n)
Search O(n) O(n)
Insert at head O(1) O(1)
Delete head O(1) O(1)
Insert after known node O(1) O(1)
Delete known node O(1)* O(1)
Insert at tail O(n) / O(1)** O(1)**

* Singly linked lists generally require the previous node unless the
problem provides a special trick.
** With a maintained tail pointer.

4. Pointer Invariants

Most advanced linked-list problems are about maintaining pointer
invariants.

For reversal:

flowchart LR
    P["prev"] --> A["current"]
    A --> B["next"]
    B --> C["..."]

During each iteration:

next = current.next
current.next = prev
prev = current
current = next

At every step:

prev points to the already-reversed prefix.
current points to the remaining unreversed suffix.
No node becomes unreachable.

5. Iterative Reversal

flowchart LR
    A["1"] --> B["2"]
    B --> C["3"]
    C --> D["4"]

    D2["4"] --> C2["3"]
    C2 --> B2["2"]
    B2 --> A2["1"]

Complexity: O(n) time and O(1) auxiliary space.

The same pattern generalizes to:

Reverse entire list
Reverse a subrange
Reverse in groups of k
Rotate a list
Reorder nodes

6. Fast & Slow Pointers

flowchart LR
    H["Head"] --> A["1"] --> B["2"] --> C["3"] --> D["4"] --> E["5"] --> F["6"]

    A -. "slow" .-> C
    A -. "fast" .-> E

The slow/fast pointer technique uses different movement speeds.

Common applications:

Find middle node.
Detect cycle.
Find cycle entry.
Check palindrome.
Split list for merge sort.

For a list of length n, moving slow by one and fast by two makes
slow reach the middle in O(n) time.

7. Floyd's Cycle Detection

flowchart LR
    A["1"] --> B["2"] --> C["3"] --> D["4"]
    D --> E["5"]
    E --> C

    S["slow: +1"] -.-> C
    F["fast: +2"] -.-> E

Algorithm:

Move slow one step.
Move fast two steps.
If they meet, a cycle exists.
Reset one pointer to head.
Move both one step.
Their next meeting point is the cycle entry.

Complexity: O(n) time, O(1) extra space.

8. Merge Two Sorted Lists

flowchart LR
    A["1 → 4 → 7"] --> M["Merge"]
    B["2 → 3 → 8"] --> M
    M --> R["1 → 2 → 3 → 4 → 7 → 8"]

The key invariant is:

The result prefix is always sorted, and every node already removed
from the input lists belongs to that prefix.

Complexity: O(n + m) time and O(1) auxiliary space for iterative
merging.

9. Merge Sort on Linked Lists

Linked lists pair naturally with merge sort because merging does not
require random access.

flowchart TD
    A["8 → 3 → 5 → 1 → 7 → 2"] --> B["Split"]
    B --> C["8 → 3 → 5"]
    B --> D["1 → 7 → 2"]

    C --> E["Sort"]
    D --> F["Sort"]

    E --> G["Merge"]
    F --> G
    G --> H["1 → 2 → 3 → 5 → 7 → 8"]

Complexity:

Time: O(n log n)
Auxiliary space: O(log n) with recursive implementation.
Can be implemented bottom-up to achieve O(1) auxiliary space.

10. Reverse in Groups of K

For:

1 → 2 → 3 → 4 → 5 → 6 → 7

with k = 3:

3 → 2 → 1 → 6 → 5 → 4 → 7

flowchart LR
    A["1 2 3"] --> R1["3 2 1"]
    B["4 5 6"] --> R2["6 5 4"]
    C["7"] --> R3["7"]

    R1 --> R2 --> R3

The difficult part is not reversal itself; it is correctly reconnecting:

Previous group
Current group
Reversed group
Remaining suffix

11. Palindrome Detection

A common O(n) / O(1) approach:

flowchart TD
    S["List"] --> M["Find middle"]
    M --> R["Reverse second half"]
    R --> C["Compare halves"]
    C --> X{"Equal?"}
    X -->|"Yes"| P["Palindrome"]
    X -->|"No"| N["Not palindrome"]

For production-quality implementations, consider restoring the second
half after comparison if the operation is expected to be
non-destructive.

12. LRU Cache

A classic advanced use of a doubly linked list + hash map.

flowchart LR
    M["HashMap<br/>key → node"] --> N["Doubly Linked List"]

    H["Most Recent"] --> A["A"] --> B["B"] --> C["C"] --> T["Least Recent"]

    M -. "O(1) lookup" .-> A
    M -. "O(1) lookup" .-> B
    M -. "O(1) lookup" .-> C

Why both structures?

Hash map → O(1) node lookup.
Doubly linked list → O(1) removal and insertion when the node is
known.
Together → get() and put() can be O(1).

The list maintains recency order; the map provides direct node access.

13. Common Edge Cases

Always test:

null / empty list
single node
two nodes
insert at head
delete head
delete tail
operation affects entire list
cycle exists
k = 1
k > list length
even / odd length
duplicate values

14. Interview Problem Flow

flowchart TD
    P["Linked List Problem"] --> Q{"What is required?"}

    Q -->|"Reverse"| R["Pointer Reversal"]
    Q -->|"Middle / Cycle"| FS["Fast + Slow"]
    Q -->|"Sorted Lists"| M["Two-Pointer Merge"]
    Q -->|"Palindrome"| PA["Middle + Reverse + Compare"]
    Q -->|"K Groups"| KG["Segment + Reverse + Reconnect"]
    Q -->|"Cache"| LRU["HashMap + Doubly Linked List"]
    Q -->|"Sort"| MS["Merge Sort"]
    Q -->|"Random Access"| A["Consider Array / Other Structure"]

15. Key Mental Models

Linked list = pointer manipulation problem.
Know the invariant before changing next.
Fast/slow pointers solve many structural problems.
Doubly linked lists trade memory for constant-time bidirectional
manipulation.
HashMap + DLL is the standard pattern behind an O(1) LRU
cache.
Merge sort is usually preferable to comparison-based array-style
sorting on linked lists.
Always protect the remaining suffix before rewiring pointers.