Linked List

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

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

  constructor(public value: T) {}
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  constructor(public value: T) {}
}

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

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

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

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

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

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

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

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

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

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

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 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) អរគុណ pointer tail
  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)៖ យើងត្រូវរក node មុន 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) នៅនឹងកន្លែង
  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) នៅពេលអ្នកកាន់ 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;
  }
}

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

npx tsx --test

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