shtabnoy.com / challenges / linked-list

✦ Algo & data structures

Building a Linked List
from scratch

Nodes pointing to nodes. No arrays, no indices — just pointers. Append, prepend, delete, insert, and reverse a list by rewiring references. Then step through reversal one pointer at a time.

linked listpointersreversalreferencesO(1) prepend

// try it

Build and manipulate a list

Add nodes, remove them, insert at any position, or reverse the whole chain. Watch the pointers rewire in real time.

head→null

Size: 0

append / prepend / delete

insertAt(index, value)

// step through

Reversing a linked list, one pointer at a time

Step through the reversal of [1 → 2 → 3]. Watch prev, node, and next move through memory. See exactly which address each variable holds at each step — and why reassigning one doesn't change the others.

Step 1 / 13

Memory

0xa0

1.next →0xb0

node

0xb0

2.next →0xc0

0xc0

3.next →null

null

node

0xa0

—

Code

let prev = null, node = head;

const next = node.next; // save

node.next = prev; // reverse

prev = node; // advance prev

node = next; // advance node

What just happened:

Start: prev = null, node = head (0xa0)

// why it works

Assignment copies addresses, not objects

The reason pointer manipulation works is that a = b copies the address b holds at that moment. It's a snapshot, not a subscription. Changing b later doesn't touch a. Step through below to see it.

Variables (hold addresses)

a=0xA0

b=null

Memory (objects live here)

0xA0{value: 1}← a

Code

let a = {value: 1};    // a holds 0xA0

Variable "a" stores the address 0xA0 — where the object lives in memory. It doesn't hold the object itself, just the address.

💡 The rule

Reassigning a variable (prev = node) only changes what that variable points to. Mutating a property (node.next = prev) changes the object, and anything else pointing to that object sees the change. That's two fundamentally different operations — and the entire linked list reversal depends on doing them in the right order.

⚠ This isn't just a JS thing

JavaScript, Python, Java, C#, Go, Rust — they all work this way with reference types. Variables hold addresses. Assignment copies addresses. Mutation goes through the address to change the underlying object. Once you internalize this, pointer code in any language clicks.

// the code

The full implementation

Generic, with append, prepend, delete, insertAt, and in-place reverse. No arrays used internally — just nodes and pointers.

linkedList.ts

type ListNode<T> = {
  value: T;
  next: ListNode<T> | null;
};

class LinkedList<T> {
  private _head: ListNode<T> | null = null;
  private _size: number = 0;

  append(value: T) {
    const newNode = { value, next: null };
    let node = this._head;
    while (node?.next) { node = node.next; }
    if (node) { node.next = newNode; }
    else { this._head = newNode; }
    this._size++;
  }

  prepend(value: T) {
    this._head = { value, next: this._head };
    this._size++;
  }

  deleteByValue(value: T): boolean {
    if (this._head?.value === value) {
      this._head = this._head.next;
      this._size--;
      return true;
    }
    let node = this._head;
    while (node) {
      if (node.next?.value === value) {
        node.next = node.next.next;
        this._size--;
        return true;
      }
      node = node.next;
    }
    return false;
  }

  insertAt(index: number, value: T): boolean {
    if (index >= this._size) return false;
    if (index === 0) { this.prepend(value); return true; }
    let node = this._head;
    for (let i = 0; i < index - 1; i++) { node = node!.next; }
    node!.next = { value, next: node!.next };
    this._size++;
    return true;
  }

  reverse() {
    let prev = null;
    let node = this._head;
    while (node) {
      const next = node.next;   // save next
      node.next = prev;         // reverse pointer
      prev = node;              // advance prev
      node = next;              // advance node
    }
    this._head = prev;
  }
}

// takeaways

What this exercise teaches

🔗

Nodes + pointers = list

A linked list is just objects pointing to other objects. No array, no indices. Traversal is always O(n) because you have to walk from head to find anything.

⚡

O(1) insert at head

Prepending is instant — create a node, point it to the old head, done. No shifting elements like an array. That's the linked list's killer feature.

🔄

Reversal = pointer juggling

Reversing in place requires three variables (prev, node, next) and careful sequencing. It's the most common interview question because it tests pointer manipulation under pressure.

📍

Assignment copies addresses