Day 15: Linked Lists

DAY 15 / 30 · WEEK 3

Goal of the day

• Build a singly linked list from scratch with a real Node class, and see why it’s a chain of pointers scattered in memory — not a contiguous block like an array.
• Implement insert-at-head, insert-at-tail, insert-at-position, and delete (by value or by position), and know exactly which two pointers move for each one.
• Understand why inserting/deleting once you’re already at the right node is O(1) — and why reaching that node in the first place is the part that actually costs O(k), the same order of cost as shifting an array.

Concept

Think of a scavenger hunt: each clue tells you where to find the next clue, but nothing tells you where clue #4 is directly — you have to physically walk clue 1 → clue 2 → clue 3 → clue 4, reading each one to learn where the next is hidden. A linked list is exactly that: to reach the 4th node, there’s no shortcut, you follow the chain one link at a time.

Every array lesson so far has relied on one fact: arr[i] is direct math — the engine computes a memory address from the base address plus i times the element size, in O(1). That direct math is exactly what makes inserting into the middle of an array expensive: to open up a slot at index i, every element from i onward has to physically shift over, which is O(n).

A linked list gives up direct math entirely. Each element (a node) holds a value and a pointer to the next node — nothing tells you where node 3 lives in memory until you’ve walked node 0 → node 1 → node 2 → node 3, one .next at a time. There is no arr[3] shortcut.

That trade produces the headline claim of this lesson, stated carefully: if you already have a pointer to the node just before where you want to insert or delete, the operation itself is O(1) — you rewire two pointers and you’re done, no shifting. But if you only have an index or a value and have to find that node first, the traversal to reach it costs O(k) (k = how far in), which is the same order of growth as an array shift. The win isn’t “linked lists are always faster” — it’s “the splice itself is free once you’re there.”

The classic rewire-order bug

Overwriting a .next pointer before you’ve saved a reference to what it used to point at permanently severs the rest of the list. Insert order: set the new node’s .next first, then repoint the previous node’s .next — never the reverse. Delete order: capture removed = prev.next before you touch prev.next — reverse those two lines and everything past removed is unreachable, permanently. Watch for this order explicitly in both animations below.

Diagram

Insert at a given position

prev (traversal position)new node (not linked yet)spliced in / done

Insert at a given position — running example: [10, 20, 30, 40, 50], insert 25 at position 2

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step↺ Reset🔀 Shuffle

Delete a node by value

prev (traversal position)checking prev.nextmarked for removal

Delete a node by value — running example: [10, 20, 30, 40, 50], delete 30

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step↺ Reset🔀 Shuffle

Code: a singly linked list

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

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  insertAtHead(val) {
    const node = new Node(val);
    node.next = this.head;      // save old head as new node's next FIRST
    this.head = node;            // then repoint head
    if (!this.tail) this.tail = node; // list was empty — new node is also the tail
    this.size++;
    return this;
  }

  insertAtTail(val) {
    const node = new Node(val);
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
    return this;
  }

  insertAt(index, val) {
    if (index <= 0 || !this.head) return this.insertAtHead(val);
    if (index >= this.size) return this.insertAtTail(val);
    const node = new Node(val);
    let prev = this.head;
    for (let i = 0; i < index - 1; i++) prev = prev.next; // walk to the node BEFORE index
    node.next = prev.next;   // ① new node points at what prev used to point at
    prev.next = node;         // ② now it's safe to repoint prev
    this.size++;
    return this;
  }

  deleteValue(val) {
    if (!this.head) return false;
    if (this.head.val === val) {
      this.head = this.head.next;
      if (!this.head) this.tail = null; // list is now empty — reset tail too
      this.size--;
      return true;
    }
    let prev = this.head;
    while (prev.next && prev.next.val !== val) prev = prev.next;
    if (!prev.next) return false; // reached the end — value not found
    const removed = prev.next;    // ① capture the reference before touching it
    prev.next = removed.next;      // ② now it's safe to bypass it
    if (!prev.next) this.tail = prev; // removed the old tail — fix the tail pointer
    this.size--;
    return true;
  }

  toArray() {
    const out = [];
    let cur = this.head;
    while (cur) {
      out.push(cur.val);
      cur = cur.next;
    }
    return out;
  }
}

Line by line:

• Node is deliberately tiny: a val and a next pointer, initialized to null (meaning “nothing after this yet”).
• insertAtHead: node.next = this.head must run before this.head = node — if you reassigned this.head first, you’d have already lost the only reference to the old head, and node.next would have nothing to point at.
• insertAtTail keeps a dedicated tail pointer specifically so this is O(1) — without it, “insert at the end” would require walking the whole list first to find the last node, making it O(n).
• insertAt’s loop (for (let i = 0; i < index - 1; i++)) walks prev from head until it’s sitting on the node just before the target index — that walk is the O(k) part. The two lines after it are the actual splice, ordered on purpose: ① save what prev used to point at by handing it to the new node first, ② only then overwrite prev.next.
• deleteValue’s while loop walks prev until prev.next is the node we want gone (not prev itself — you always need the node before the target in a singly linked list, since you can’t go backward). const removed = prev.next captures the reference before prev.next gets overwritten.
• Both insertAtHead and deleteValue handle the empty-list case (!this.head) and the single-node case (deleting the only node resets both head and tail to null) explicitly — skipping either check throws on an empty list or leaves a stale tail pointer.

Dry run: insertAt(2, 25) on [10, 20, 30, 40, 50]

Step	prev	Action
1	index 0 (value 10)	prev = head — start the walk
2	index 1 (value 20)	i (0) < index-1 (1) — prev = prev.next
3	index 1 (value 20)	i (1) is no longer < index-1 (1) — loop stops here
4	—	Create new node, value 25 (not linked yet)
5	—	① new.next = prev.next → 25.next = node(30)
6	—	② prev.next = new → node(20).next = node(25)
7	—	Done: [10, 20, 25, 30, 40, 50]

The loop only ran once — that’s the whole O(k) traversal cost for k = 2. Everything from step 4 onward is O(1): two pointer writes, regardless of whether the list had 5 nodes or 5 million.

Complexity

Operation	Time	Space	Why
Insert at head	O(1)	O(1)	Two pointer writes (new.next, head) — no traversal, regardless of list size.
Insert at tail (with tail pointer)	O(1)	O(1)	tail already references the last node — one pointer write, no walk needed.
Insert at position k	O(k)	O(1)	Walking from head to the node before position k dominates; the splice itself is O(1) once you’re there.
Delete by value / position k	O(k)	O(1)	Same story as insert — finding the node before the target costs O(k); the rewire is O(1).
Search / traverse for a value	O(n)	O(1)	No random access — you must walk one .next at a time from head; worst case visits every node.

k = how far the target position/value is from head (worst case k = n, e.g. deleting the last node by value with no tail-ward search). n = list size. Every operation above is O(1) extra space — nodes are rewired in place, nothing is copied.

Delete Node in a Linked List — the reference-only trick

Given only a reference to a node (not head, not its predecessor), you can’t walk backward to find what points at it. The workaround: copy the next node’s value into this node, then skip over the next node (node.next = node.next.next). You’ve effectively deleted “the next node’s data” while making the current node disappear from the caller’s perspective. This only works if the given node isn’t the last one — say that constraint out loud even if the problem guarantees it.

Interview corner

Why is inserting/deleting at a known position “O(1)” for a linked list but O(n) for an array? An array has to shift every element after the insertion/deletion point to keep the block contiguous — O(n) moves. A linked list just rewires two pointers (the new node’s .next, and the previous node’s .next) — the size of the rest of the list doesn’t matter, as long as you’re already positioned at the right node.

Common follow-up

“So is a linked list always faster for inserting into the middle?” — No. If you don’t already hold a pointer to that spot, you have to traverse to find it first, and that traversal is O(k) — the same order of cost as an array shift. The O(1) claim is specifically about the splice itself once you’re already there (e.g. you’re handed the node, or you just visited it).

What’s the classic bug when rewiring .next pointers during insert or delete? Overwriting a .next pointer before you’ve saved a reference to what it used to point at.

Trap

In delete, writing prev.next = something before capturing const removed = prev.next permanently severs access to everything past that point. The safe order is always: read/save the pointer you still need, THEN overwrite.

How do you delete a node when you’re only given a reference to that node itself — not the head, not the previous node? This is the classic “Delete Node in a Linked List” trick: since a singly linked list can’t be walked backward, copy the next node’s value into the current node, then skip over the next node (node.next = node.next.next). You’ve effectively deleted “the next node’s data” while making the current node disappear from the caller’s perspective.

Trap

This only works if the given node is not the last node — there’s no next node to copy from. Say that constraint out loud even if the problem guarantees it.

What has to be handled differently for an empty list or a single-node list? Null-check head (and tail) before dereferencing anything. Deleting the only node in the list must reset both head and tail back to null — resetting only head leaves a stale tail pointing at a node no longer reachable from head, which silently corrupts the next insertAtTail call.

What’s the difference between “insert X after node Y” and “insert X before node Y”? “After Y” is easy with just a reference to Y: newNode.next = Y.next; Y.next = newNode. “Before Y” is not directly possible with only a reference to Y — a singly linked list only lets you see forward, so you’d need the node before Y (found by traversing from head), or a doubly linked list with a prev pointer. Confirm which direction a problem means before writing any pointer code.

How to talk through it out loud: narrate three things, in order, before you touch a pointer. First, which reference you need to save before you change anything — “I need a pointer to the node just before where I’m inserting or deleting.” Second, the rewire itself, naming the exact order — “the new node’s next first, then the previous node’s next — never the reverse, or I lose the rest of the list.” Third, the two edge cases you’re handling — empty list, and single-node list. Interviewers watching a linked-list solution are listening specifically for whether you say the rewire order out loud before you draw it, because that’s exactly where the classic bug lives.

Practice problems

1. Delete Node in a Linked List — Easy

LeetCode: Delete Node in a Linked List

You’re given a reference to a node (guaranteed not the tail) to delete — but no reference to head and no way to reach the node before it.

Hint

You can’t reach backward in a singly linked list, and you’re not given head. But you don’t have to remove this node’s memory to make it look deleted — you can borrow data from the node just ahead of it instead.

Show solution

function deleteNode(node) {
  node.val = node.next.val;
  node.next = node.next.next;
}

2. Remove Duplicates from Sorted List — Easy

LeetCode: Remove Duplicates from Sorted List

Given the head of a sorted linked list, delete all duplicate values so each element appears only once, and return the (still sorted) list.

Hint

The list is sorted, so any duplicates are always adjacent — you never need to look more than one node ahead. Compare a node to its immediate next and decide whether to advance past it or skip over it.

Show solution

function deleteDuplicates(head) {
  let cur = head;
  while (cur && cur.next) {
    if (cur.val === cur.next.val) cur.next = cur.next.next;
    else cur = cur.next;
  }
  return head;
}

3. Add Two Numbers — Medium

LeetCode: Add Two Numbers

Two non-empty linked lists represent non-negative integers, one digit per node, digits stored in reverse order. Add the two numbers and return the sum as a linked list in the same format.

Hint

Reverse-order digits mean “head to tail” is already “least significant to most significant” — add the same way you would on paper, carrying overflow into the next position as you go. Build the result with a dummy head node so the first digit isn’t a special case.

Show solution

function addTwoNumbers(l1, l2) {
  const dummy = new Node(0);
  let cur = dummy;
  let carry = 0;
  while (l1 || l2 || carry) {
    const sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + carry;
    carry = Math.floor(sum / 10);
    cur.next = new Node(sum % 10);
    cur = cur.next;
    l1 = l1 ? l1.next : null;
    l2 = l2 ? l2.next : null;
  }
  return dummy.next;
}

Quiz

Quiz: 1. Why can inserting at the head of a linked list be O(1) while inserting at the front of an array is O(n)?

Arrays must shift every existing element to make room; a list only repoints two pointers, no shifting

Arrays need O(n) shifts to keep the block contiguous; a linked list only rewires two pointers (new node’s next, and head) — no shifting, regardless of list size.

Quiz: 2. In insertAt(index, val), what determines the real time cost of the operation?

The traversal needed to reach the node just before index — the splice itself is O(1)

Walking prev from head to the node just before the target index is O(index) — the actual splice (two pointer writes) is O(1) once you’re there. The traversal is what actually costs time.

Quiz: 3. Why must you capture a node’s next pointer (or the node itself) before reassigning any pointer during a delete?

Overwriting a pointer before saving the reference it holds permanently loses everything after it

Overwriting a .next pointer before saving the reference it holds permanently loses access to everything past that point — that’s why deleteValue captures removed = prev.next before touching prev.next.

Quiz: 4. What must be reset when the only node in a linked list is deleted?

Both head and tail must be set to null

Deleting the only node must reset both head and tail to null. Leaving tail stale means the next insertAtTail call writes into a node that’s no longer reachable from head.

Quiz: 5. Given only a reference to a node (not head, not its predecessor), how does the classic “Delete Node in a Linked List” trick remove it?

Copy the next node’s value into this node, then skip over the next node

With only a reference to the node (no head, no predecessor), you copy the next node’s value into it, then skip over the next node (node.next = node.next.next) — this is the classic Delete Node in a Linked List trick, and it fails only if the given node is the last one.