DAY 15 / 30 · WEEK 3

Linked Lists

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."

Diagram: anatomy of a linked list

Diagram: insert order matters

Diagram: delete order matters

Interactive visualization: insert at a given position

Interactive visualization: delete a node by value

The 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, and they're 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 — reverse those two lines and the rest of the list past removed is unreachable, permanently.
• 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]

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

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.

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

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

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;
}

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