linkedList.js

/**
 * Class representing a tree node
 */
class Node {
  /**
   * Create a linked list node
   * @param {any} value - The value of the node
   * @param {Node} next - The reference to the next nodes
   */
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

/**
 * Class representing a linked list
 */
class LinkedList {
  constructor() {
    this.head = null;
  }

  /**
   * Get the size of the linked list.
   * @returns {number} The number of nodes in the linked list.
   */
  size() {
    let count = 0;
    let node = this.head;
    while (node) {
      count++;
      node = node.next;
    }
    return count;
  }

  /**
   * Get the first node in the linked list.
   * @returns {Node} The first node in the linked list.
   */
  getFirst() {
    return this.head;
  }

  /**
   * Get the last node in the linked list.
   * @returns {Node} The last node in the linked list or null if the list is empty.
   */
  getLast() {
    if (!this.head) {
      return null;
    }

    let node = this.head;
    while (node.next) {
      node = node.next;
    }

    return node;
  }

  /**
   * Get the node at a specific index.
   * @param {number} index The index of the node to get.
   * @returns {Node} The node at the specified index or null if list is empty or index is out of boundary.
   */
  getAt(index) {
    let counter = 0;
    let node = this.head;
    while (node) {
      if (counter === index) {
        return node;
      }
      node = node.next;
      counter++;
    }
    return null;
  }

  /**
   * Search for a node with a specific value.
   * @param {any} value
   * @returns {boolean} True if the value is found, false otherwise.
   */
  search(value) {
    let node = this.head;
    while (node) {
      if (node.value === value) {
        return true;
      }
      node = node.next;
    }
    return false;
  }

  /**
   * Empty the linked list. i.e. Set the head as null.
   */
  clear() {
    this.head = null;
  }

  /**
   * Insert a node at a specific index.
   * @param {any} value
   * @param {number} index
   */
  insertAt(value, index) {
    if (!this.head) {
      // When the list is empty.
      this.head = new Node(value);
      return;
    }

    if (index === 0) {
      // When inserting at the head.
      this.head = new Node(value, this.head);
      return;
    }

    const previous = this.getAt(index - 1) || this.getLast();
    const node = new Node(value, previous.next);
    previous.next = node;
  }

  /**
   * Add a node to the head of the linked list
   * @param {any} value - The value of the node to insert
   */
  insertFirst(value) {
    this.head = new Node(value, this.head);
  }

  /**
   * Append a node to the end of the linked list
   * @param {any} value The value of the node to insert
   */
  insertLast(value) {
    const last = this.getLast();

    if (last) {
      last.next = new Node(value);
    } else {
      this.head = new Node(value);
    }
  }

  /**
   * Remove the first node in the linked list.
   */
  removeFirst() {
    if (!this.head) {
      return;
    }
    this.head = this.head.next;
  }

  /**
   * Remove the last node in the linked list. (Set the last second node's next as null)
   */
  removeLast() {
    if (!this.head) {
      //When linked list is empty
      return;
    }

    let node = this.head;
    if (!node.next) {
      // When linked list has only one node
      this.head = null;
      return;
    }

    while (node.next.next) {
      node = node.next;
    }
    node.next = null;
  }

  /**
   * Remove a node at a specific index.
   * @param {number} index
   */
  removeAt(index) {
    if (!this.head) {
      //When linked list is empty
      return;
    }

    if (index === 0) {
      // Delete the first node.
      this.head = this.head.next;
      return;
    }

    const previous = this.getAt(index - 1);
    if (!previous || !previous.next) {
      return;
    }
    previous.next = previous.next.next;
  }
}

module.exports = { Node, LinkedList };