Linked Lists

Beads on a String
Nodes and Pointers
Where You Meet Linked Lists at Work
Linked List vs Array
Walking, Searching, and Inserting
Removing a Node
Doubly Linked Lists
Classic Problem: Reverse a List
Classic Problem: Cycle Detection
Classic Problems: Middle, Merge, and Nth From the End
Recipe: linked-list.ts for algolab
Try It Yourself

1. Beads on a String

An array is a row of lockers: numbered, side by side, and you can walk straight to locker 500. A linked list is a treasure hunt. Each clue tells you what is at this spot and where the next clue is hiding. To reach the 500th clue you have to follow 499 clues first.

That sounds like a worse deal, and for reading it is. But the treasure hunt has a superpower. To add a new clue between two existing ones, you only change what the neighbors point to. Nothing else has to move, and nothing gets copied. In the last chapter you saw that shift() and splice() on an array have to slide every later element. A linked list does the same job in a single step, once you are standing in the right place.

In this chapter you will:

build a linked list from scratch with nodes and pointers,
see exactly when it beats an array (and when it loses),
solve the four linked-list problems that show up again and again in interviews,
add a tested LinkedList class to algolab that the next chapter uses to build queues.

If you have not set up algolab yet, go back to Why Data Structures and Algorithms Matter. Everything below assumes src/ and the npx tsx --test command from that chapter.

2. Nodes and Pointers

A linked list is made of small objects called nodes. Each node holds two things: a value, and a pointer (a reference) to the next node. The last node points to null, meaning "nothing after me".

head                                tail
 |                                   |
 v                                   v
[ 10 | * ]--->[ 20 | * ]--->[ 30 | * ]--->[ 40 | null ]

In TypeScript, a node is a tiny class:

class ListNode<T> {
  next: ListNode<T> | null = null;

  constructor(public value: T) {}
}

The type ListNode<T> | null says "either the next node or nothing". TypeScript will make you check for null before you follow a pointer, which prevents a whole family of bugs.

You can build a list by hand:

const a = new ListNode(10);
const b = new ListNode(20);
const c = new ListNode(30);

a.next = b;
b.next = c;

// a -> b -> c -> null

The list is just the first node. We call it the head, and everything else is reached by following .next. If you lose the head, you lose the whole list, because nothing else points at the first node. Garbage collection then cleans it all up.

We also keep a second pointer to the last node, called the tail. You will see in a moment why it matters.

In memory the nodes can be anywhere. Unlike an array, the nodes do not sit next to each other. Each one is a separate object that happens to point to the next. This has two big consequences:

You cannot jump to item i. You must start at the head and walk.
Inserting or removing does not move any other node. You only change pointers.

A third, quieter consequence: modern CPUs love reading memory that sits side by side (arrays), because they load a whole chunk at once. Jumping between scattered nodes is slower in practice, even when the Big-O is the same.

3. Where You Meet Linked Lists at Work

You will rarely write class ListNode in an everyday web project, but the idea is everywhere:

Browser history. Back and forward go through a chain of pages, one step at a time. A doubly linked list fits perfectly.
Undo/redo and playlists. "Previous" and "next" song is a doubly linked list. Music apps also insert "play next" in the middle without rebuilding the queue.
LRU caches. A cache that evicts the least recently used item keeps items in a doubly linked list, so it can move an item to the front in O(1). This is one of the most famous interview questions.
Operating systems and memory allocators. Free memory blocks are tracked in linked lists.
Git. Every commit points to its parent commit, so a branch is a linked list of commits.
Other structures. Hash maps with chaining (chapter 3), queues (next chapter), graphs' adjacency lists, and blockchains are all built from nodes that point to other nodes.

Even if you never build one for production, interviewers love linked lists. They test whether you can think in pointers without losing track of the chain.

4. Linked List vs Array

Here are the costs side by side. n is the number of items. "Singly linked, with head and tail pointers" is what we build in this chapter.

Operation	Array	Singly linked list
Read item at index `i`	O(1)	O(n)
Add at the end	O(1) amortized	O(1) (with tail)
Add at the start	O(n)	O(1)
Remove from the start	O(n)	O(1)
Remove from the end	O(1)	O(n)
Insert in the middle (position known)	O(n)	O(1)
Find a value	O(n)	O(n)
Memory per item	just the value	value plus a pointer

Read the "insert in the middle" row carefully. It says "position known". To insert after the 500th node, you still have to walk 500 steps to get there. The actual pointer change is O(1), but finding the spot is O(n). The linked list only wins when you already hold a reference to the node, for example when a cache moves an item that it just looked up.

Remove-from-the-end is O(n) for a singly linked list because you need the node before the last one, and the only way to find it is to walk from the head. (A doubly linked list fixes that, see section 7.)

So when should you reach for a linked list?

You add and remove at the front all the time (a queue, or a stack).
You need to splice items in and out and you already hold the node.
You must never pay for a big array copy, even occasionally.

And when should you not? Almost always, if you need index access or you iterate over lots of items. In JavaScript the plain array is heavily optimized, and for small and medium sizes it often beats a hand-written list even where Big-O says it should lose. Treat the linked list as a tool you understand, rather than your default.

5. Walking, Searching, and Inserting

Nearly every linked-list operation starts with a loop that walks the chain. Memorize this shape:

let node = head;
while (node !== null) {
  // do something with node.value
  node = node.next;
}

Let's put the pieces into a class. It keeps head, tail, and a count, so asking for the size is O(1):

class LinkedList<T> {
  head: ListNode<T> | null = null;
  tail: ListNode<T> | null = null;
  private count = 0;

  get size(): number {
    return this.count;
  }
}

Adding to the front

prepend makes a new node, points it at the old head, and makes it the new head:

prepend(value: T): this {
  const node = new ListNode(value);
  node.next = this.head;
  this.head = node;
  if (this.tail === null) this.tail = node; // list was empty
  this.count++;
  return this;
}

The order of the two pointer lines matters. If you wrote this.head = node first, you would lose the only reference to the old list. Always connect the new node to the rest first, and only then move the head.

Returning this lets you chain calls: list.prepend(2).prepend(1).

Adding to the end

Without a tail pointer, append would walk the whole list: O(n). With one, it is a single step:

append(value: T): this {
  const node = new ListNode(value);
  if (this.tail === null) {
    this.head = node; // list was empty
  } else {
    this.tail.next = node;
  }
  this.tail = node;
  this.count++;
  return this;
}

Two cases: an empty list (the new node becomes both head and tail), and a non-empty list (the old tail points to the new node, which becomes the tail). Empty-list special cases are the number one source of linked list bugs. Whenever you write a method, ask "what if the list is empty?" and "what if it has exactly one item?".

Reading by index

get(index: number): T | undefined {
  if (index < 0 || index >= this.count) return undefined;
  let node = this.head;
  for (let i = 0; i < index; i++) node = node!.next;
  return node!.value;
}

This is O(n): the cost grows with the index. The ! after node tells TypeScript "I checked the range, this is not null".

Inserting in the middle

To insert at position index, stop at the node before the position, then rewire two pointers:

before:   prev --> X
after:    prev --> NEW --> X

insertAt(index: number, value: T): void {
  if (index < 0 || index > this.count) {
    throw new RangeError(`Index ${index} out of range`);
  }
  if (index === 0) {
    this.prepend(value);
    return;
  }
  if (index === this.count) {
    this.append(value);
    return;
  }
  let prev = this.head!;
  for (let i = 0; i < index - 1; i++) prev = prev.next!;
  const node = new ListNode(value);
  node.next = prev.next; // new node points to the rest...
  prev.next = node; // ...then the previous node points to it
  this.count++;
}

Again the order: first node.next = prev.next, then prev.next = node. Swap those two lines and prev.next would already point to the new node, so the new node would point to itself and the rest of the list would be lost.

6. Removing a Node

To remove a node, make the node before it skip over it:

before:   prev --> TARGET --> after
after:    prev -----------------> after

The target is left with nobody pointing to it, and the garbage collector reclaims it. Removing from the front is easy, because there is no previous node:

removeFirst(): T | undefined {
  if (this.head === null) return undefined;
  const node = this.head;
  this.head = node.next;
  if (this.head === null) this.tail = null; // list became empty
  this.count--;
  return node.value;
}

Notice the line if (this.head === null) this.tail = null. If you removed the last remaining node and forgot it, tail would keep pointing at a dead node, and the next append would attach to the wrong place.

Removing from the end is the awkward one. We must find the node before the tail, and a singly linked list can only walk forward:

removeLast(): T | undefined {
  if (this.head === null) return undefined;
  if (this.head === this.tail) return this.removeFirst();
  let prev = this.head;
  while (prev.next !== this.tail) prev = prev.next!;
  const value = this.tail!.value;
  prev.next = null;
  this.tail = prev;
  this.count--;
  return value;
}

It is O(n) even though we have a tail pointer. The tail pointer helps us reach the last node, but not the one before it.

Removing a value from the middle walks with two variables: node (the one we are looking at) and prev (the one behind it):

remove(value: T): boolean {
  let prev: ListNode<T> | null = null;
  let node = this.head;
  while (node !== null) {
    if (node.value === value) {
      if (prev === null) {
        this.removeFirst();
      } else {
        prev.next = node.next;
        if (node === this.tail) this.tail = prev;
        this.count--;
      }
      return true;
    }
    prev = node;
    node = node.next;
  }
  return false;
}

Three cases hide in there: the first node (no prev), a middle node, and the last node (so tail must move back to prev). Writing out the cases like this, before coding, is the trick to getting pointer code right the first time.

7. Doubly Linked Lists

A doubly linked list gives every node a second pointer, prev, that points backward:

null <-- [10] <--> [20] <--> [30] --> null

class DNode<T> {
  prev: DNode<T> | null = null;
  next: DNode<T> | null = null;

  constructor(public value: T) {}
}

The extra pointer costs memory, and every insert and remove must fix four pointers instead of two. In exchange you get:

walking in both directions (browser back and forward),
removing a node in O(1) when you hold the node itself, even from the end, because node.prev is right there.

class DoublyLinkedList<T> {
  head: DNode<T> | null = null;
  tail: DNode<T> | null = null;
  size = 0;

  append(value: T): DNode<T> {
    const node = new DNode(value);
    node.prev = this.tail;
    if (this.tail) this.tail.next = node;
    else this.head = node;
    this.tail = node;
    this.size++;
    return node; // hand back the node so callers can remove it later
  }

  // O(1) when you already hold the node
  removeNode(node: DNode<T>): void {
    if (node.prev) node.prev.next = node.next;
    else this.head = node.next;
    if (node.next) node.next.prev = node.prev;
    else this.tail = node.prev;
    node.prev = node.next = null;
    this.size--;
  }
}

Notice that append returns the node. That is the trick behind an LRU cache: a hash map from key to node gives O(1) lookup, and the doubly linked list gives O(1) "remove this node and put it at the front". You will use that combination in the exercises.

Here is removeNode at work:

const list = new DoublyLinkedList<string>();
list.append("a");
const b = list.append("b");
list.append("c");

list.removeNode(b);
// list is now a <-> c

8. Classic Problem: Reverse a List

"Reverse a singly linked list" is the most common linked-list interview question. The idea: walk the list once, and flip each pointer so it points backward instead of forward.

before:  1 -> 2 -> 3 -> null
after:   null <- 1 <- 2 <- 3     (head is now 3)

You need three variables: prev (the part already reversed), node (the one we are fixing), and next (saved, so we do not lose the rest of the list when we overwrite node.next):

reverse(): this {
  let prev: ListNode<T> | null = null;
  let node = this.head;
  this.tail = this.head; // the old head becomes the new tail
  while (node !== null) {
    const next: ListNode<T> | null = node.next; // 1. remember the rest
    node.next = prev; // 2. flip the pointer
    prev = node; // 3. step forward
    node = next;
  }
  this.head = prev;
  return this;
}

Trace it on 1 -> 2 -> 3:

Step	`prev`	`node`	`next`	List so far
start	null	1
1	1	2	2	`1 -> null`
2	2	3	3	`2 -> 1 -> null`
3	3	null	null	`3 -> 2 -> 1 -> null`

When node becomes null, prev is the new head. The reversal takes O(n) time and O(1) extra space, because it changes the pointers in place and creates no new nodes.

A common mistake is forgetting to save next before overwriting node.next. Then node = node.next just goes back where you came from, and the loop never ends.

The recursive version is a nice exercise for chapter 6, but the loop is what interviewers expect first.

9. Classic Problem: Cycle Detection

What if a node's next points back to an earlier node?

1 -> 2 -> 3 -> 4
          ^    |
          |____|

Walking such a list with while (node !== null) loops forever. A bug like that can freeze a program, so we need a way to detect it.

First idea: remember every node we have seen in a Set. If we meet one twice, there is a cycle. It works and takes O(n) time, but also O(n) extra memory.

Better idea, Floyd's tortoise and hare: use two pointers. The slow one (tortoise) moves one step at a time. The fast one (hare) moves two. If there is no cycle, the hare reaches the end. If there is a cycle, the hare enters it first and keeps lapping around, and eventually catches up to the tortoise from behind. They land on the same node, so we know there is a cycle.

function hasCycle<T>(head: ListNode<T> | null): boolean {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Time O(n), extra space O(1). Two details matter:

The loop checks fast !== null && fast.next !== null, because the hare jumps two nodes and must not step off the end.
We compare nodes (=== on references), not values. Two different nodes can hold the same value.

Test it:

const list = LinkedList.from(["a", "b", "c", "d"]);
console.log(hasCycle(list.head)); // false

list.tail!.next = list.head!.next; // d now points back to b
console.log(hasCycle(list.head)); // true

Be careful: after you create a cycle on purpose, do not call toArray() or any method that walks the list until the end. It never ends.

Why does this work? Imagine two runners on a circular track. The faster one gains one step per round on the slower one. Sooner or later the gap becomes zero. The gap shrinks by exactly one each time, so it cannot jump over zero.

10. Classic Problems: Middle, Merge, and Nth From the End

The same two-pointer idea solves several more problems.

Find the middle

Move fast twice as fast as slow. When fast reaches the end, slow is at the middle. One pass, no need to know the length:

function findMiddle<T>(head: ListNode<T> | null): ListNode<T> | null {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow;
}

For 1, 2, 3 it returns the node with 2. For 1, 2, 3, 4 there are two middles, and this version returns the second one, 3. State your choice out loud in an interview.

Merge two sorted lists

Given two lists already in ascending order, produce one sorted list by relinking the existing nodes. This is the same "merge" step that merge sort uses (you will meet it in the sorting chapter).

The trick is a dummy node: a fake node placed before the real result. It removes the special case of "what is the head of the result?", because you can always attach to tail.next.

function mergeSorted(
  a: ListNode<number> | null,
  b: ListNode<number> | null,
): ListNode<number> | null {
  const dummy = new ListNode<number>(0);
  let tail = dummy;
  while (a !== null && b !== null) {
    if (a.value <= b.value) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a ?? b; // attach whatever is left over
  return dummy.next;
}

Walk through 1 -> 4 -> 6 and 2 -> 3 -> 7 -> 8:

Compare	Take	Result so far
1 vs 2	1	1
4 vs 2	2	1, 2
4 vs 3	3	1, 2, 3
4 vs 7	4	1, 2, 3, 4
6 vs 7	6	1, 2, 3, 4, 6
(first list empty)	rest of second	1, 2, 3, 4, 6, 7, 8

Time is O(n + m) for lists of length n and m, and extra space is O(1) because no new nodes are created.

Using <= instead of < takes from a on ties, which keeps the merge stable: equal items stay in their original order. Stability becomes important in the sorting chapter.

Remove the nth node from the end

"Remove the 2nd node from the end" without first counting the length. Use two pointers a fixed gap apart. Move lead ahead by n steps, then move both until lead hits the last node. Now lag sits right before the node to remove.

function removeNthFromEnd<T>(
  head: ListNode<T> | null,
  n: number,
): ListNode<T> | null {
  const dummy = new ListNode<T>(undefined as T);
  dummy.next = head;
  let lead: ListNode<T> | null = dummy;
  let lag: ListNode<T> = dummy;
  for (let i = 0; i < n; i++) lead = lead!.next;
  while (lead!.next !== null) {
    lead = lead!.next;
    lag = lag.next!;
  }
  lag.next = lag.next!.next;
  return dummy.next;
}

The dummy node pays off again: if n equals the list length, the node to remove is the head, and lag is the dummy, so no special case is needed. Removing the 2nd from the end of 1, 2, 3, 4, 5 gives 1, 2, 3, 5.

The problems in this chapter follow patterns worth remembering:

Problem	Pattern
Reverse	three pointers: `prev`, `node`, `next`
Cycle	slow and fast pointers
Middle	slow and fast pointers
Merge	dummy head plus a moving tail
Nth from end	two pointers with a fixed gap, plus dummy head

11. Recipe: linked-list.ts for algolab

Create src/linked-list.ts in algolab. It collects everything from this chapter, and the Queue in the next chapter builds on it:

export class ListNode<T> {
  next: ListNode<T> | null = null;

  constructor(public value: T) {}
}

export class LinkedList<T> implements Iterable<T> {
  head: ListNode<T> | null = null;
  tail: ListNode<T> | null = null;
  private count = 0;

  get size(): number {
    return this.count;
  }

  // O(1)
  prepend(value: T): this {
    const node = new ListNode(value);
    node.next = this.head;
    this.head = node;
    if (this.tail === null) this.tail = node;
    this.count++;
    return this;
  }

  // O(1) thanks to the tail pointer
  append(value: T): this {
    const node = new ListNode(value);
    if (this.tail === null) {
      this.head = node;
    } else {
      this.tail.next = node;
    }
    this.tail = node;
    this.count++;
    return this;
  }

  // O(n)
  get(index: number): T | undefined {
    if (index < 0 || index >= this.count) return undefined;
    let node = this.head;
    for (let i = 0; i < index; i++) node = node!.next;
    return node!.value;
  }

  // O(n)
  insertAt(index: number, value: T): void {
    if (index < 0 || index > this.count) {
      throw new RangeError(`Index ${index} out of range`);
    }
    if (index === 0) {
      this.prepend(value);
      return;
    }
    if (index === this.count) {
      this.append(value);
      return;
    }
    let prev = this.head!;
    for (let i = 0; i < index - 1; i++) prev = prev.next!;
    const node = new ListNode(value);
    node.next = prev.next;
    prev.next = node;
    this.count++;
  }

  // O(1)
  removeFirst(): T | undefined {
    if (this.head === null) return undefined;
    const node = this.head;
    this.head = node.next;
    if (this.head === null) this.tail = null;
    this.count--;
    return node.value;
  }

  // O(n): we must find the node before the tail
  removeLast(): T | undefined {
    if (this.head === null) return undefined;
    if (this.head === this.tail) return this.removeFirst();
    let prev = this.head;
    while (prev.next !== this.tail) prev = prev.next!;
    const value = this.tail!.value;
    prev.next = null;
    this.tail = prev;
    this.count--;
    return value;
  }

  // O(n)
  remove(value: T): boolean {
    let prev: ListNode<T> | null = null;
    let node = this.head;
    while (node !== null) {
      if (node.value === value) {
        if (prev === null) {
          this.removeFirst();
        } else {
          prev.next = node.next;
          if (node === this.tail) this.tail = prev;
          this.count--;
        }
        return true;
      }
      prev = node;
      node = node.next;
    }
    return false;
  }

  // O(n)
  indexOf(value: T): number {
    let i = 0;
    for (const v of this) {
      if (v === value) return i;
      i++;
    }
    return -1;
  }

  // O(n), in place
  reverse(): this {
    let prev: ListNode<T> | null = null;
    let node = this.head;
    this.tail = this.head;
    while (node !== null) {
      const next: ListNode<T> | null = node.next;
      node.next = prev;
      prev = node;
      node = next;
    }
    this.head = prev;
    return this;
  }

  *[Symbol.iterator](): Iterator<T> {
    let node = this.head;
    while (node !== null) {
      yield node.value;
      node = node.next;
    }
  }

  toArray(): T[] {
    return [...this];
  }

  static from<T>(values: Iterable<T>): LinkedList<T> {
    const list = new LinkedList<T>();
    for (const v of values) list.append(v);
    return list;
  }
}

// Floyd's tortoise and hare
export function hasCycle<T>(head: ListNode<T> | null): boolean {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

export function findMiddle<T>(
  head: ListNode<T> | null,
): ListNode<T> | null {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow;
}

export function mergeSorted(
  a: ListNode<number> | null,
  b: ListNode<number> | null,
): ListNode<number> | null {
  const dummy = new ListNode<number>(0);
  let tail = dummy;
  while (a !== null && b !== null) {
    if (a.value <= b.value) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}

export function removeNthFromEnd<T>(
  head: ListNode<T> | null,
  n: number,
): ListNode<T> | null {
  const dummy = new ListNode<T>(undefined as T);
  dummy.next = head;
  let lead: ListNode<T> | null = dummy;
  let lag: ListNode<T> = dummy;
  for (let i = 0; i < n; i++) lead = lead!.next;
  while (lead!.next !== null) {
    lead = lead!.next;
    lag = lag.next!;
  }
  lag.next = lag.next!.next;
  return dummy.next;
}

export class DNode<T> {
  prev: DNode<T> | null = null;
  next: DNode<T> | null = null;

  constructor(public value: T) {}
}

export class DoublyLinkedList<T> {
  head: DNode<T> | null = null;
  tail: DNode<T> | null = null;
  size = 0;

  append(value: T): DNode<T> {
    const node = new DNode(value);
    node.prev = this.tail;
    if (this.tail) this.tail.next = node;
    else this.head = node;
    this.tail = node;
    this.size++;
    return node;
  }

  // O(1) when you already hold the node
  removeNode(node: DNode<T>): void {
    if (node.prev) node.prev.next = node.next;
    else this.head = node.next;
    if (node.next) node.next.prev = node.prev;
    else this.tail = node.prev;
    node.prev = node.next = null;
    this.size--;
  }

  toArray(): T[] {
    const out: T[] = [];
    for (let n = this.head; n; n = n.next) out.push(n.value);
    return out;
  }
}

Now the tests. Create src/linked-list.test.ts:

import { test } from "node:test";
import assert from "node:assert/strict";
import {
  LinkedList,
  ListNode,
  DoublyLinkedList,
  hasCycle,
  findMiddle,
  mergeSorted,
  removeNthFromEnd,
} from "./linked-list.ts";

test("append, prepend and size", () => {
  const list = new LinkedList<number>();
  list.append(2).append(3).prepend(1);
  assert.deepEqual(list.toArray(), [1, 2, 3]);
  assert.equal(list.size, 3);
});

test("get, insertAt, indexOf", () => {
  const list = LinkedList.from([10, 20, 40]);
  list.insertAt(2, 30);
  assert.deepEqual(list.toArray(), [10, 20, 30, 40]);
  assert.equal(list.get(2), 30);
  assert.equal(list.get(9), undefined);
  assert.equal(list.indexOf(40), 3);
  assert.equal(list.indexOf(99), -1);
  assert.throws(() => list.insertAt(9, 1), RangeError);
});

test("removeFirst, removeLast, remove", () => {
  const list = LinkedList.from([1, 2, 3, 4]);
  assert.equal(list.removeFirst(), 1);
  assert.equal(list.removeLast(), 4);
  assert.equal(list.remove(2), true);
  assert.equal(list.remove(99), false);
  assert.deepEqual(list.toArray(), [3]);
  assert.equal(list.tail?.value, 3);
  list.removeLast();
  assert.equal(list.head, null);
  assert.equal(list.tail, null);
  assert.equal(list.removeFirst(), undefined);
});

test("reverse", () => {
  const list = LinkedList.from([1, 2, 3]);
  list.reverse();
  assert.deepEqual(list.toArray(), [3, 2, 1]);
  assert.equal(list.tail?.value, 1);
  list.append(0);
  assert.deepEqual(list.toArray(), [3, 2, 1, 0]);
});

test("hasCycle", () => {
  const list = LinkedList.from([1, 2, 3, 4]);
  assert.equal(hasCycle(list.head), false);
  list.tail!.next = list.head!.next;
  assert.equal(hasCycle(list.head), true);
  assert.equal(hasCycle(null), false);
});

test("findMiddle", () => {
  assert.equal(findMiddle(LinkedList.from([1, 2, 3]).head)?.value, 2);
  assert.equal(findMiddle(LinkedList.from([1, 2, 3, 4]).head)?.value, 3);
});

test("mergeSorted", () => {
  const a = LinkedList.from([1, 4, 6]);
  const b = LinkedList.from([2, 3, 7, 8]);
  const merged = mergeSorted(a.head, b.head);
  const out: number[] = [];
  for (let n = merged; n; n = n.next) out.push(n.value);
  assert.deepEqual(out, [1, 2, 3, 4, 6, 7, 8]);
});

test("removeNthFromEnd", () => {
  const head = removeNthFromEnd(LinkedList.from([1, 2, 3, 4, 5]).head, 2);
  const out: number[] = [];
  for (let n = head; n; n = n.next) out.push(n.value);
  assert.deepEqual(out, [1, 2, 3, 5]);
  const single = removeNthFromEnd(new ListNode(1), 1);
  assert.equal(single, null);
});

test("DoublyLinkedList removeNode", () => {
  const list = new DoublyLinkedList<string>();
  list.append("a");
  const b = list.append("b");
  list.append("c");
  list.removeNode(b);
  assert.deepEqual(list.toArray(), ["a", "c"]);
  assert.equal(list.size, 2);
});

Run the tests:

npx tsx --test

You should see every test pass. If one fails, read the message: it shows the expected and actual values, which usually points straight at the pointer you forgot to update.

Try the list in a small script, demo.ts:

import { LinkedList, findMiddle } from "./src/linked-list";

const list = LinkedList.from([1, 2, 3, 4]);
list.prepend(0);
console.log(list.toArray().join(" -> "), "| size", list.size);
console.log(list.get(2), list.indexOf(4));

list.reverse();
console.log(list.toArray().join(" -> "));

list.reverse();
console.log(findMiddle(list.head)?.value);

npx tsx demo.ts

0 -> 1 -> 2 -> 3 -> 4 | size 5
2 4
4 -> 3 -> 2 -> 1 -> 0
2

For a feel of the cost difference, queue up 100,000 numbers in a plain array and remove them all with shift(), then do the same with append and removeFirst() on the list. The array version has to slide the remaining items on every removal (engines optimize this heavily, so the gap may be smaller than the Big-O suggests), while the list does the same constant amount of work every time. Time both with performance.now() as you did in chapter 1, and try 1,000,000 items too. Pay attention to how the gap changes as the input grows. That growth is what Big-O describes.

12. Try It Yourself

Size without a counter. Write a function length(head) that counts nodes by walking the list. Then explain why LinkedList stores a count instead. What does it cost to keep it up to date?
Insert in sorted order. Add a method insertSorted(value) to a list of numbers that is already in ascending order, placing the new value in the correct spot. What is the Big-O? What happens when the value is smaller than everything, or larger than everything?
Palindrome list (interview). Given a singly linked list of digits, return true if it reads the same forward and backward, in O(n) time and O(1) extra space. Hint: find the middle, reverse the second half, then compare both halves. Does your solution restore the list?
Remove duplicates. Given a sorted list 1, 1, 2, 3, 3, 3, remove duplicates in place so each value appears once. One pass, no extra structure. Then solve the unsorted version using a Set, and compare the trade-off.
Find the cycle start (interview). Extend hasCycle so it returns the node where the cycle begins, or null. Hint: after the tortoise and hare meet, put one pointer back at the head and move both one step at a time. They meet at the start of the cycle. Try to convince yourself why.
LRU cache. Using a Map<string, DNode<...>> and DoublyLinkedList, build a cache with capacity n. get(key) moves the item to the back (most recent) and returns its value. put(key, value) adds the item and, if the cache is full, removes the item at the front. Both operations must be O(1). You will need to store the key inside each node, and a way to move a node to the back (remove it, then re-append it).

Linked lists trade fast access for fast rearrangement, and the pointer skills from this chapter (saving next, dummy nodes, two-speed pointers) come back in trees and graphs. In the next chapter, Stacks and Queues, we use a plain array and your new LinkedList to build two of the most useful structures in programming: one that undoes, and one that waits in line.