Linked Lists & In-Place Reversal

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. Non-Contiguous Node Chains

Unlike arrays, a Linked List stores elements in separate heap-allocated nodes where each node contains a value and a pointer (next) referencing the following node.

2. Memory Structure: Array vs. Linked List

Array:        [ 10 | 20 | 30 ]  (Single contiguous block of memory addresses)

Linked List:  [ 10 | * ] ──> [ 20 | * ] ──> [ 30 | null ]  (Scattered memory nodes)
                Node 1         Node 2         Node 3

3. In-Place List Reversal

Reversing a linked list in-place requires 3 pointers (prev, curr, next) to reorient pointers without allocating new memory:

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function reverseList(head) {
  let prev = null;
  let curr = head;

  while (curr !== null) {
    const nextTemp = curr.next; // 1. Save reference to next node
    curr.next = prev;          // 2. Reverse pointer backwards
    prev = curr;               // 3. Move prev pointer forward
    curr = nextTemp;           // 4. Move curr pointer forward
  }

  return prev; // 'prev' is now the new head of the reversed list!
}

4. Visual 3-Pointer Step-by-Step

Before:  null <── [prev]      [curr] ──> [nextTemp] ──> ...
                       │         │
Action:                └─── [curr.next = prev]

5. Operation Complexities

6. Common Mistakes

• Losing the Next Reference: Forgetting to save curr.next before reassigning curr.next = prev severs the rest of the list, losing all remaining nodes in memory!

7. Next Steps

Use linked lists when frequent head insertions/deletions are required. Next, let's explore Stacks and the Monotonic Stack Pattern!