list.js

class Node {
  /**
   * Creates an instance of Node.
   *
   * @param {any} value   Node's value
   * @param {Node} [next] The next Node in the list
   */
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

/**
 * Javascript list implementation
 *
 * @export
 * @class List
 */
class List {
  /**
   * Creates an instance of List.
   *
   * @param {any} initialValue  Value to initiate the list with.
   */
  constructor(initialValue) {
    if (initialValue) {
      this.head = new Node(initialValue);
    }
  }

  /**
   * Computes the length of the list
   *
   * @return {number} The length of the list.
   */
  getLength() {
    let current = this.head;
    let length = 0;

    while (current) {
      current = current.next;
      length += 1;
    }

    return length;
  }

  /**
   * Returns the head of the list (the first element)
   *
   * @return {Node} The head node (the first node in the list)
   */
  getHead() {
    return this.head;
  }

  /**
   * Returns the tail of the list (the last element)
   *
   * @return {Node} The tail node (the last node in the list)
   */
  getTail() {
    return this.reduce((_, node) => node, undefined, false);
  }

  /**
   * @callback reduceCallbackFn
   * @param {any} accumulated
   * @param {any} current
   * @return {any}
   */

  /**
   * Reduces the list to a single value
   *
   * @param {reduceCallbackFN} callbackFn   Callback which reduces the list.
   * @param {any} [startingValue]           Value to initiate the reducing with.
   * @param {boolean} [extractValues=true]  Decides on what will be passed to the callbackFn,
   * either values or whole nodes.
   * @return {any}                          Reduced value
   */
  reduce(callbackFn, startingValue, extractValues = true) {
    let currentNode;
    let accumulated;

    let extractorFn;
    if (extractValues) {
      extractorFn = node => node.value;
    } else {
      extractorFn = node => node;
    }

    if (!this.head) {
      return startingValue;
    }

    if (startingValue === undefined) {
      currentNode = this.head;
      accumulated = startingValue;
    } else {
      currentNode = this.head.next;
      accumulated = extractorFn(this.head);
    }

    while (currentNode) {
      accumulated = callbackFn(accumulated, extractorFn(currentNode));
      currentNode = currentNode.next;
    }

    return accumulated;
  }

  /**
   * @callback valueCallbackFn
   * @param {any} value
   * @param {number} index
   */

  /**
   * Traverses the list and executes the callback function for each element in the list.
   * The first argument of the callback function is the node's value, the second one is the index.
   *
   * @param {valueCallbackFn} callbackFn  Function invoked for each element in the list.
   */
  forEach(callbackFn) {
    let index = 0;

    this.reduce((_, value) => {
      callbackFn(value, index);
      index += 1;
      return null;
    });
  }

  /**
   * Executes callbackFn on each item from the list and returns the results as another list.
   *
   * @param {valueCallbackFn} callbackFn  Function invoked for each element in the list
   * @return {List}   Transformed list
   */
  map(callbackFn) {
    const outputList = new List();

    this.forEach((value, index) => {
      const transformedValue = callbackFn(value, index);
      outputList.pushBack(transformedValue);
    });

    return outputList;
  }

  /**
   * Retrieves the Node with a given index
   *
   * @param {number} targetIndex  Wanted node's index
   * @return {Node}               Found node
   */
  get(targetIndex) {
    let currentIndex = 0;
    let currentNode = this.head;

    if (targetIndex < 0 ) {
      throw new Error('Index exceeds list\'s size');
    }

    while (currentIndex < targetIndex && currentNode) {
      if (currentNode.next === null) {
        throw new Error('Index exceeds list\'s size');
      }
      currentIndex += 1;
      currentNode = currentNode.next;
    }

    return currentNode;
  }

  /**
   * Adds a value to the end of the list
   *
   * @param {any} newValue  A value to be added
   * @return {List}         This list. Allows for chainability
   */
  pushBack(newValue) {
    const newNode = new Node(newValue);
    const tail = this.getTail();

    if (tail) {
      tail.next = newNode;
    } else {
      this.head = newNode;
    }

    return this;
  }

  /**
   * Adds a value at a given index
   *
   * @param {any} value     Value to be added.
   * @param {number} index  Index at which the value should be added.
   * @throws {Error} Index must not exceed list size.
   * @return {List}    This list. Allows for chainability.
   */
  push(value, index) {
    if (index === 0) {
      // Replace head
      this.head = new Node(value, this.head);
    } else {
      const previousNode = this.get(index - 1);
      if (!previousNode) {
        throw new Error('Index exceeds list\'s size');
      }

      const nextNode = previousNode.next;
      previousNode.next = new Node(value, nextNode);
    }

    return this.head;
  }

  /**
   * Removes nodes with specific values from the list
   *
   * @param {any} valueToRemove A value to be removed
   * @return {List}             This list. Allows for chainability.
   */
  remove(valueToRemove) {
    if (this.head.next === null) {
      this.head = {};
      return this.head;
    }
    if (this.head.value === valueToRemove) {
      this.head = this.head.next;
      return this.remove(valueToRemove);
    }

    this._removeRecursive(this.head, valueToRemove);
    return this;
  }

  /**
   * Used internally by remove. Replaces the current node with a next one if the value matches.
   *
   * @private
   * @param {Node} previousNode Reference to the previous node.
   * @param {any} valueToRemove Value to be removed.
   */
  _removeRecursive(previousNode, valueToRemove) {
    if (!previousNode.next) {
      return;
    }
    const currentNode = previousNode.next;

    if (currentNode.value === valueToRemove) {
      previousNode.next = currentNode.next;
      this._removeRecursive(previousNode, valueToRemove);
    } else {
      this._removeRecursive(currentNode, valueToRemove);
    }
  }

  /**
   * Returns the first node that value matches.
   *
   * @param {any} value Value to be found
   * @return {Node}     Node with that value
   */
  find(value) {
    const findRecursive = (node, value) => {
      if (!node) {
        return null;
      } else if (node.value === value) {
        return node;
      }
      return findRecursive(node.next, value);
    };

    return findRecursive(this.head, value);
  }

  /**
   * Converts the list to an array
   *
   * @return {any[]}  Array of values from the list
   */
  getValues() {
    const valuesArray = [];
    this.forEach(value => valuesArray.push(value));
    return valuesArray;
  }

}

module.exports = List;

// Source: https://github.com/Gelio/js-list