doublyLinkedList.js

/**
 * Doubly Linked list function constructor.
 * 
 * @example const DoublyLinkedList = require('dstructures').DoublyLinkedList;
 * const myDoublyLinkedList = new DoublyLinkedList();
 * @description In computer science, a doubly linked list is a linked data 
 * structure that consists of a set of sequentially linked records called 
 * nodes. Each node contains two fields, called links, that are references 
 * to the previous and to the next node in the sequence of nodes. The beginning 
 * and ending nodes' previous and next links, respectively, point to some kind 
 * of terminator, typically a sentinel node or null, to facilitate traversal 
 * of the list. Full wikipedia article at:
 * {@link https://en.wikipedia.org/wiki/Doubly_linked_list}
 * @public
 * @constructor
 */
class DoublyLinkedList {
  
  constructor(){
    const head = new Node('head');
    const tail = new Node('tail');

    this.getTail = () => tail;
    this.getHead = () => head;
    
    this.getHead().next     = this.getTail();
    this.getTail().previous = this.getHead();
  }
  

  /**
   * Returns the element property of the given node.
   * 
   * @param {any} element Element property of the node.
   * @returns Returns the element property of the node.
   */
  GetElement (element) {
    return this._find(element).element;
  }
  
  /**
   * Inserts a node in a doubly linked list.
   * 
   * @param {any} newElement Given element.
   * @param {any} [oldElement = head] 'oldElement' argument defaults to 'head' if 
   * is not present, and inserts at the head of doubly linked list.  
   * @returns {Boolean|Void} Returns false if the 'newElement' argument is not present.
   * @example DoublyLinkedList.insert(1); // [1]
   * DoublyLinkedList.insert(2, 1); // [1] -> [2]
   * DoublyLinkedList.insert(3, 1); // [1] -> [3] -> [2]
   * DoublyLinkedList.insert(4); // [4] -> [1] -> [3] -> [2]
   */
  insert (newElement, oldElement) {
    oldElement   = oldElement || 'head';
    if (!newElement) {return false;}

    let newNode  = new Node(newElement);
    let current  = this._find(oldElement);

    if (current === false) {
      return false;
    }

    if (this.getHead().next.element === 'tail') {
      return this.append(newElement);
    }

    newNode.next     = current.next;
    newNode.previous = current;
    current.next     = newNode;
  }

  /**
   * Appends element to a doubly linked list.
   * 
   * @param {any} element Given element.
   * @returns {Boolean|Void} Returns false if 'element' argument is not present.
   * @example DoublyLinkedList.append(1); // [1]
   * DoublyLinkedList.append(2); // [1] -> [2]
   * DoublyLinkedList.append(3); // [1] -> [2] -> [3]
   * @memberOf DoublyLinkedList
   */
  append (element) {
    if (!element) {
      return false;
    }

    const newNode  = new Node(element);
    const current  = this.getTail(); 

    newNode.previous      = current.previous;
    current.previous.next = newNode;
    newNode.next          = current;
    current.previous      = newNode;
  }
  
  /**
   * Removes element from a doubly linked list.
   * 
   * @param {any} element Element that will be removed.
   * @returns {Boolean} Returns false if the element is not present.
   * @example DoublyLinkedList; // [1] -> [2] -> [3]
   * DoublyLinkedList.remove(2); // [1] -> [3]
   */
  remove (element) {
    let currentNode = this._find(element);
    if (currentNode.next !== null && currentNode !== false) {
      currentNode.previous.next = currentNode.next;
      currentNode.next.previous = currentNode.previous;
      currentNode.next = null;
      currentNode.previous = null;
    }
    return false;
  }
  
  /**
   * Returns array representation of a doubly linked list.
   * 
   * @returns {Array} Returns array representation of the Doubly linked list. 
   * @example DoublyLinkedList; // ['cat'] -> ['pig'] -> ['dog']
   * DoublyLinkedList.toArray(); // ['cat', 'pig', 'dog']
   */
  toArray () {
    let resultArray  = [];
    let currentNode  = this.getHead();
    while (currentNode.next.next !== null) {
      resultArray.push(currentNode.next.element);
      currentNode = currentNode.next;
    }
    return resultArray;
  }

  _find (element) {
    let currentNode = this.getHead();
    while (currentNode.element !== element  && currentNode.next !== null) {
      currentNode = currentNode.next;
    }
    if (currentNode.element === element) {
      return currentNode;
    }
    return false;
  }
  
}

// Node function constructor.
//  @private
function Node(element) {
  this.element = element;
  this.next    = null;
  this.previous = null;
}

module.exports = DoublyLinkedList