Linked Lists

An array keeps its items side by side in memory. Item 5 sits right after item 4, so the computer finds it with arithmetic and never looks at anything else.

A linked list gives that up. Each item is its own little box, anywhere in memory, holding a value and the address of the next box:

type Node = {value: number; next: Node | null};

That one change flips the entire cost table:

Nearly every bug is the same bug

You overwrote an address before you had finished reading it.

Reversing a list is the classic exercise, and it is entirely about that. Watch the arrows flip:

while (current !== null) {  const next = current.next;   // save it BEFORE severing  current.next = previous;     // flip this arrow  previous = current;  current = next;}return previous;               // the new head

The code

function reverse(head: Node | null): Node | null {
  let previous: Node | null = null;
  let current = head;

  while (current !== null) {
    const next = current.next;   // save the rest of the list
    current.next = previous;     // flip this arrow
    previous = current;          // both markers shuffle forward
    current = next;
  }

  return previous;               // current is null; previous is the new head
}

Three variables and four lines in the loop. Return previous, not current — by the time the loop ends current is null, and previous is standing on what used to be the last node.

The dummy node

Here is a problem you meet constantly. Deleting a node means pointing its predecessor at whatever comes next:

prev.next = prev.next.next;

But the first node has no predecessor. So every list function grows a special case at the top for “what if it is the head”, and that branch is the one you test least and get wrong most.

A dummy node — a fake node parked in front of the real head — removes the distinction entirely. Now everything has a predecessor:

function remove(head: Node | null, value: number): Node | null {
  const dummy: Node = {value: 0, next: head};

  let prev = dummy;
  while (prev.next !== null) {
    if (prev.next.value === value) prev.next = prev.next.next;
    else prev = prev.next;
  }

  // Return dummy.next, never `head` — head may be the node we just deleted.
  return dummy.next;
}

Two pointers at different speeds

The two-pointer idea works here too, but instead of starting at opposite ends the pointers move at different rates.

Advance one pointer two nodes for every one node of the other. When the fast one reaches the end, the slow one is exactly at the middle — one pass, and you never had to count the length.

The same trick detects a loop. If the list cycles, the fast pointer eventually laps the slow one and they land on the same node; if it does not, fast hits null. That is Floyd’s algorithm, and it uses no extra memory where the obvious solution needs a set of every node seen.

When to actually use one

Honestly, not often in application code.

Arrays win on real hardware for nearly everything you would reach for a list to do. Memory that sits side by side gets loaded into cache in blocks, so walking an array is close to free; walking a linked list is a cache miss per node, because the boxes are scattered.

Linked lists earn their place when you already hold the node and need to splice it out instantly: LRU caches, the free lists inside memory allocators, intrusive lists in operating-system kernels. In every case the win is that you never pay the walk to find it.