Linked List

A data structure where each element contains a value and a reference to the next node, supporting efficient insertion and deletion operations.

/**
 * @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.
 */
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.
 */
class CircularLinkedList<ValueType> {
  /**
   * 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> {
    let currentNode = this.sentinel.next;
    while (currentNode !== this.sentinel && currentNode.value !== valueToFind) {
      currentNode = currentNode.next;
    }

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

(() => {
  // Default sentinel
  const list = new CircularLinkedList<number>();
  if (
    list.sentinel.next !== list.sentinel ||
    list.sentinel.previous !== list.sentinel
  ) {
    throw new Error(`Sentinel does not point to itself by default.`);
  }

console.log('Sentinel functionality is correct.');

// Test inserting nodes
  const node1 = new LinkedListNode(1);
  const node2 = new LinkedListNode(2);
  list.insert(node1);
  list.insert(node2);
  if (
    list.sentinel.next !== node2 ||
    node2.next !== node1 ||
    node1.previous !== node2
  ) {
    throw new Error('Insert functionality failed.');
  }

console.log('Insert functionality is correct.');

// Test searching for a node
  const nodeFound = list.search(1);
  if (nodeFound !== node1) {
    throw new Error(
      `Search failed. Expected: ${node1.value}, Got: ${nodeFound.value}`,
    );
  }

console.log('Search functionality is correct.');

// Test deleting a node
  list.delete(node1);
  if (list.search(1) !== list.sentinel) {
    throw new Error(
      'Delete functionality failed. Node was not properly removed.',
    );
  }

console.log('Delete functionality is correct.');
})();