LinkedList

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

export default class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  /**
   * Adds an item to the head of the linked list.
   * @param {*} value The item to be added to the head of the list.
   */
  insertHead(value) {
    const newNode = new Node(value);

    // Empty list: new node is both head and tail.
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }

    this.size++;
  }

  /**
   * Adds an item to the tail of the linked list.
   * @param {*} value The item to be added to the tail of the list.
   */
  insertTail(value) {
    const newNode = new Node(value);

    // Empty list: new node is both head and tail.
    if (this.tail === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.size++;
  }

  /**
   * Remove the item in the given index and return its value or `undefined` if index is out of bound.
   * @param {int} i The index of the item to be removed.
   * @return {*} The value of the item in index i if it exists, `undefined` otherwise.
   */
  remove(i) {
    if (i < 0 || i >= this.size) {
      return undefined;
    }

    // Remove head.
    if (i === 0) {
      const removedValue = this.head.value;

      this.head = this.head.next;
      this.size--;

      // If list becomes empty, also clear tail.
      if (this.size === 0) {
        this.tail = null;
      }

      return removedValue;
    }

    // Find node before the one we want to remove.
    let prev = this.head;

    for (let index = 0; index < i - 1; index++) {
      prev = prev.next;
    }

    const nodeToRemove = prev.next;
    const removedValue = nodeToRemove.value;

    prev.next = nodeToRemove.next;

    // If removing tail, update tail.
    if (nodeToRemove === this.tail) {
      this.tail = prev;
    }

    this.size--;

    return removedValue;
  }

  /**
   * Return the value of the item in the given index or `undefined` if index is out of bound.
   * @param {int} i The index of the value of the item to be returned.
   * @return {*} The value of the item in index i if it exists, `undefined` otherwise.
   */
  get(i) {
    if (i < 0 || i >= this.size) {
      return undefined;
    }

    let current = this.head;

    for (let index = 0; index < i; index++) {
      current = current.next;
    }

    return current.value;
  }

  /**
   * Return an array containing all the values of the items in the linked list from head to tail.
   * @return {*} The array of all the values in the linked list from head to tail.
   */
  toArray() {
    const result = [];
    let current = this.head;

    while (current !== null) {
      result.push(current.value);
      current = current.next;
    }

    return result;
  }

  /**
   * Return the length / number of elements in the linked list.
   * @return {*} Length of the linked list.
   */
  length() {
    return this.size;
  }
}