Dustin Boston

/**
 * @file Linked List
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

/**
 * Represents a node in a circular doubly linked list.
 *
 * @template ValueType - The type of the value stored in the node.
 */
export class LinkedListNode<ValueType> {
  /** Points to the next node in the list. */
  next: LinkedListNode<ValueType> = this;

  /** Points to the previous node in the list. */
  previous: LinkedListNode<ValueType> = this;

  /**
   * Creates a new node with an optional value.
   *
   * @param value - The value stored in the node.
   */
  constructor(public value?: ValueType) {}
}

/**
 * A circular doubly linked list implementation.
 *
 * @template ValueType - The type of the values stored in the list.
 */
export class LinkedList<ValueType> {
  count = 0;

  /**
   * Sentinel node used to eliminate boundary conditions. This node connects
   * the list's head and tail in a circular manner.
   */
  sentinel: LinkedListNode<ValueType> = new LinkedListNode<ValueType>();

  /**
   * Searches for a node containing the specified value.
   *
   * @remarks
   *   If the sentinel node is returned, the value was not found.
   * @param valueToFind - The value to search for in the list.
   * @returns The node containing the specified value, or the sentinel node if
   *   not found.
   * @complexity O(n) in the worst case.
   */
  search(valueToFind: ValueType): LinkedListNode<ValueType> | undefined {
    let currentNode = this.sentinel.next;
    while (currentNode !== this.sentinel && currentNode.value !== valueToFind) {
      currentNode = currentNode.next;
    }

    return currentNode === this.sentinel ? undefined : currentNode;
  }

  /**
   * Inserts a node at the beginning of the list, immediately after the
   * sentinel node.
   *
   * @param newNode - The node to insert into the list.
   * @returns The linked list instance for chaining.
   * @complexity O(1).
   */
  insert(newNode: LinkedListNode<ValueType>): this {
    newNode.next = this.sentinel.next;
    this.sentinel.next.previous = newNode;
    this.sentinel.next = newNode;
    newNode.previous = this.sentinel;
    this.count++;
    return this;
  }

  /**
   * Deletes a specified node from the list.
   *
   * @param nodeToDelete - The node to remove from the list.
   * @returns The linked list instance for chaining.
   * @complexity O(1).
   */
  delete(nodeToDelete: LinkedListNode<ValueType>): this {
    nodeToDelete.previous.next = nodeToDelete.next;
    nodeToDelete.next.previous = nodeToDelete.previous;
    this.count--;
    return this;
  }
}

import {describe, test, expect} from "bun:test";
import {LinkedList, LinkedListNode} from "./code.ts";

describe("Linked List", () => {
  test("Sentinel", () => {
    const list = new LinkedList<number>();
    expect(list.sentinel.next).toBe(list.sentinel);
    expect(list.sentinel.previous).toBe(list.sentinel);
  });

  test("Insert", () => {
    const list = new LinkedList<number>();
    const node1 = new LinkedListNode(1);
    const node2 = new LinkedListNode(2);

    list.insert(node1);
    list.insert(node2);

    expect(list.sentinel.next).toBe(node2);
    expect(node1.next).toBe(list.sentinel);
    expect(node2.previous).toBe(list.sentinel);
  });

  test("Search", () => {
    const list = new LinkedList<number>();

    for (const n of [1, 4, 16, 9, 25]) {
      list.insert(new LinkedListNode(n));
    }

    const node = list.search(9);

    if (node) {
      expect(node.value).toBe(9);
      expect(node.previous.value).toBe(25);
      expect(node.next.value).toBe(16);
    } else {
      throw new Error("Node is undefined.");
    }
  });

  test("Delete", () => {
    const list = new LinkedList<number>();

    for (const n of [1, 4, 16, 9, 25]) {
      list.insert(new LinkedListNode(n));
    }

    const node = list.search(1);
    expect(node).toBeDefined();
    if (node) {
      expect(node.value).toBe(1);
      list.delete(node);

      const foundNode = list.search(1);
      expect(foundNode).toBeUndefined();
    }
  });
});