🔗 Linked Lists

The Train Cars Analogy

Picture a train with connected cars:

• Each car carries cargo (data)
• Each car has a coupler to the next car (pointer)
• To add a car, you just change the coupling
• No need to move other cars!

Linked lists work exactly like this.

Each "node" contains data and a pointer to the next node. Adding or removing is just reconnecting pointers - no shifting required.

How Linked Lists Are Structured

Singly Linked List

Each node typically stores a reference to the next node:

┌──────┬──────┐   ┌──────┬──────┐   ┌──────┬──────┐
│ Data │ Next ├──▶│ Data │ Next ├──▶│ Data │ None │
│  1   │   ─  │   │  2   │   ─  │   │  3   │      │
└──────┴──────┘   └──────┴──────┘   └──────┴──────┘
     Head                                 Tail

Doubly Linked List

Each node knows both previous and next:

        ┌──────┬──────┬──────┐   ┌──────┬──────┬──────┐
  None◀─│ Prev │ Data │ Next │──▶│ Prev │ Data │ Next │──▶ None
        │      │  1   │   ─  │◀──│  ─   │  2   │      │
        └──────┴──────┴──────┘   └──────┴──────┴──────┘
              Head                       Tail

Doubly linked lists can traverse backwards and delete nodes without needing the previous reference.

The Big Trade-off: Access vs Modification

Array Strengths = Linked List Weaknesses

"Get element at index 5"

Array:       arr[5] → instant access (O(1))
Linked List: head → node1 → node2 → node3 → node4 → node5
             (5 hops = O(n))

Linked List Strengths = Array Weaknesses

"Insert new element at position 3"

Array:       Shift elements 3, 4, 5, 6, 7... (O(n))
Linked List: Just change two pointers (O(1) if you have the node)

Time Complexity Comparison

* Amortized for dynamic arrays ** O(1) if you maintain a tail pointer *** O(1) when you already have a reference to the node

When to Use Linked Lists

Use Linked Lists When:

• Frequent insertions/deletions at known positions
• You don't need random access
• Data size is unpredictable
• Building stacks, queues, or LRU caches

Use Arrays When:

• Need fast access by index
• Data is mostly read, rarely modified
• Memory efficiency matters
• Cache performance is important

Real-world verdict: Arrays win most of the time. Linked lists shine in specific scenarios like implementing other data structures.

Common Linked List Patterns

Pattern 1: Fast and Slow Pointers

Two pointers moving at different speeds:

Find the middle of a list:

Slow: one step at a time
Fast: two steps at a time

When fast reaches the end, slow is at the middle!

Example: 1 → 2 → 3 → 4 → 5
Step 1: slow at 1, fast at 1
Step 2: slow at 2, fast at 3
Step 3: slow at 3, fast at 5 (end!)

Slow points to middle (3)

Also used for: Cycle detection (if fast catches slow, there's a cycle)

Pattern 2: Dummy Node

A placeholder node before the real head:

Without dummy: "What if we delete the head?"
              Special case handling everywhere!

With dummy:    dummy → head → node2 → node3
              Often delete "the next node"
              Return dummy.next as new head

Simplifies edge cases dramatically.

Pattern 3: Reverse Traversal

Change each pointer to point backwards:

Original:  1 → 2 → 3 → None

Process each node:
  temp = current.next     (save next)
  current.next = prev     (reverse pointer)
  prev = current          (advance prev)
  current = temp          (advance current)

Result:    None ← 1 ← 2 ← 3

Classic Interview Problems

Reverse a Linked List

Challenge: 1 → 2 → 3 → None becomes 3 → 2 → 1 → None

Key insight: At each node, flip its pointer backward
Keep track of: prev (where to point), current (node to flip), next (where to go)

Detect a Cycle

Challenge: Does the list loop back on itself?

Key insight: If fast pointer (2 steps) ever meets slow pointer (1 step), there's a cycle
Why? Fast catches up to slow inside the loop

Find the Middle

Challenge: Find the middle node

Key insight: Fast/slow pointers. Fast moves twice as fast.
When fast reaches end, slow is at middle.

Merge Two Sorted Lists

Challenge: 1 → 3 → 5 and 2 → 4 → 6 become 1 → 2 → 3 → 4 → 5 → 6

Key insight: Compare heads, take smaller, advance that list
Use dummy node to simplify

Singly vs Doubly Linked Lists

Common Mistakes

1. Losing the Reference

Problem: current = current.next; current.next = something
         But you didn’t save the original current.next

Solution: Usually save references before modifying pointers

2. Forgetting Edge Cases

Empty list, single node, deleting head - all need special handling (or use dummy node!).

3. Null Pointer Errors

Usually check that a node exists before accessing its properties.

4. Off-by-One on Position

When counting "nth from end," use n+1 gap between two pointers.

FAQ

Q: Why do people often use arrays?

Linked lists excel at frequent insertions/deletions at known positions, which is O(n) for arrays. Also, linked lists have no capacity limit.

Q: What's the dummy node trick?

A fake node before the head that simplifies edge cases. You often operate on "node.next" instead of handling the head specially.

Q: Why are two pointers so common?

Many problems involve finding positions relative to the end, detecting cycles, or finding midpoints - all solved elegantly with two pointers at different speeds.

Q: Are linked lists common in practice?

Not as standalone structures, but they're the foundation for stacks, queues, deques, and LRU caches.

Summary

Linked lists store elements in nodes connected by pointers, enabling O(1) insertions/deletions at known positions.

Key Takeaways:

• Each node has data + pointer to next (and prev for doubly)
• O(1) insert/delete if you have the node reference
• O(n) access by index (no random access)
• Fast/slow pointers solve many problems
• Dummy node simplifies edge cases
• Foundation for stacks, queues, LRU cache

Arrays beat linked lists for most use cases, but understanding linked lists is essential for interviews and building other data structures!