Linked Lists

1. The physical picture

An array is one contiguous block. A linked list is a collection of separately allocated nodes:

head
  ↓
[ value | next ] → [ value | next ] → [ value | null ]

The arrow is data. If you overwrite an arrow before saving where it led, the rest of the list can become unreachable. That is why linked-list code often looks like bookkeeping: the bookkeeping is the algorithm.

Use node identities while tracing:

n0(value 7) → n1(value 7) → n2(value 4)

Values can repeat, so saying “the node with value 7” is ambiguous. n0 and n1 are not.

2. Node models in C++ and JavaScript

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x = 0, ListNode* n = nullptr) : val(x), next(n) {}
};

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

The syntax differs, but the model is the same: next is either a reference to another node or null. Assigning a.next = b changes an edge; it does not copy b.

A doubly linked node also stores prev. Every change must maintain both directions:

null ← [A] ⇄ [B] ⇄ [C] → null

That extra pointer enables O(1) removal of a known node and is why an LRU Cache uses a doubly linked list.

3. The invariant

Every node that belongs in the result is reachable exactly once from the chosen head, and every next/prev edge agrees with the intended order.

For mutation problems, strengthen it into two regions:

• a processed prefix whose links are final;
• an unprocessed suffix that is still reachable from a saved pointer.

If you can point to both regions on paper after every assignment, you are controlling the list.

4. Operations and complexity

“Deletion is O(1)” is incomplete. Finding the node or its predecessor can still cost O(n). The constant-time claim applies only when the required node references are already known.

5. How you travel a list

Basic traversal owns one moving pointer:

for (ListNode* curr = head; curr; curr = curr->next) {
    // use curr->val
}

for (let curr = head; curr; curr = curr.next) {
  // use curr.val
}

Never move a pointer and then expect it to still name the old node. If the old node is needed for rewiring, save it first.

Three combinations solve most interview questions:

1. Dummy + tail: construct or merge a result without a special first insertion.
2. prev / curr / next: reverse edges without losing the suffix.
3. slow + fast: find a middle, detect a cycle, or preserve a gap from the end.

6. Dummy-head template

ListNode dummy;
ListNode* tail = &dummy;

tail->next = chosenNode;
tail = tail->next;

return dummy.next;

const dummy = new ListNode();
let tail = dummy;

tail.next = chosenNode;
tail = tail.next;

return dummy.next;

The dummy is not a hack and its value is irrelevant. It represents “the node before the answer.”

7. It is the answer when…

• The input is already a linked list and links must change in place.
• Frequent O(1) insertion/removal is needed after a known position.
• Recency order must coexist with O(1) lookup: map + doubly linked list.
• Several sorted streams expose only their current head.
• An array maps each index to another index, creating an implicit linked list.

Do not convert every list to an array. It can simplify reasoning, but it often violates O(1) auxiliary-space requirements and avoids the pointer skill the interview is testing.

8. Classic mistakes

1. Losing the suffix: writing curr.next = prev before saving curr.next.
2. Comparing values instead of node identity: equal values do not mean two pointers met.
3. Forgetting the new head: after reversal, the old head is usually the tail.
4. Breaking only one direction: a doubly linked removal must update both neighbors.
5. Dereferencing null: check fast and fast.next before a two-edge move.

Learning gate

On paper, draw four named nodes and perform these without code:

1. insert X between n1 and n2;
2. delete the real head using a dummy;
3. reverse all four nodes while writing prev, curr, and next after every move;
4. explain why random access is O(n), even if the list contains numeric labels.

If an arrow disappears without its target being saved elsewhere, restart the drawing.