Description and implementation of a doubly linked list data structure.

doubly-linked-lists.js

/**
 * Title: Doubly Linked List
 * Author: Dylan Landry
 * Date: Wed 26 Jun 2019 16:00:15 EDT
 * Permalink: https://gist.github.com/dyllandry/12d0a2f7f1b1cfc22169b1990bd89c2d
 *
 * Description:
 * A kind of data structure similar to a train.
 * Each node, a container for a value, knows of the node ahead of it and behind
 * it. The list keeps references to the head node, the tail node, and the total
 * number of nodes.
 *
 * Strengths:
 * - O(1) performance when adding to either the beginning or end.
 *   - Contrast with an regular array's O(n) performance when adding to the end.
 *   - Contrast with a singly linked list's O(n) performance when adding to the end.
 *
 * Weaknesses:
 * - Requires more memory than a singly linked list due to the additional
 *   references backwards between nodes.
 *
 * Applications:
 * Any collection of items with a distinct linear relationship. For example:
 * web pages composing a browser history; pages in a daily journal; or cars
 * which passed through a single toll booth.
 *
 * Performance:
 * - Insertion: O(1)
 * - Removal: O(1)
 * - Searching: O(n)
 * - Access: O(n)
 *
 * Note: Comments before functions use the JSDoc 3 specification.
 * It's just a way to document functions so people can understand them.
 * JSDoc Website: https://jsdoc.app/about-getting-started.html
 */

/**
 * Creates a node. Is called a factory function.
 * @returns {Node}
 */
function Node (value) {
  const prototype = {
    value,
    next: null,
    previous: null
  }
  // Create object based on prototype object (only transfers property names)
  const node = Object.create(prototype)
  // Assign prototype property values to object.
  Object.assign(node, prototype)
  return node
}

/**
 * Creates a DoublyLinkedList.
 * @returns {DoublyLinkedList}
 */
function DoublyLinkedList () {
  const prototype = {
    // The first node
    head: null,

    // The last node
    tail: null,

    // The total number of nodes
    length: 0,

    /**
     * Adds a node to the end of the linked list.
     * @param value The new node's contained value.
     * @returns {Node} The added node.
     */
    push (value) {
      const newNode = Node(value)
      if (this.length === 0) {
        this.head = newNode
      } else {
        this.tail.next = newNode
        newNode.previous = this.tail
      }
      this.tail = newNode
      this.length++
      return newNode
    },

    /**
     * Remove a node from the end of the list.
     * @returns {?Node} The removed node, or null if there lacks a node to
     * remove.
     */
    pop () {
      if (this.tail === null) return null
      const tailToRemove = this.tail
      const newTail = tailToRemove.previous
      tailToRemove.previous = null
      if (newTail !== null) newTail.next = null
      this.tail = newTail
      this.length--
      if (this.length === 0) this.head = null
      return tailToRemove
    },

    /**
     * Removes a node from the beginning of the list.
     * @returns {?Node} The removed node, or null if there lacks a node to
     * remove.
     */
    shift () {
      if (this.head === null) return null
      const headToRemove = this.head
      if (headToRemove.next !== null) headToRemove.next.previous = null
      this.head = headToRemove.next
      headToRemove.next = null
      headToRemove.previous = null
      this.length--
      if (this.length === 0) this.tail = null
      return headToRemove
    },

    /**
     * Adds a node to the beginning of the list.
     * @param value The added node's contained value.
     * @returns {Node} The added node.
     */
    unshift (value) {
      const newHeadNode = Node(value)
      if (this.head !== null) {
        const oldHead = this.head
        oldHead.previous = newHeadNode
        newHeadNode.next = oldHead
      }
      this.head = newHeadNode
      this.length++
      if (this.length === 1) this.tail = newHeadNode
      return newHeadNode
    },

    /**
     * Gets a node at a specific index.
     * @param lookupIndex
     * @returns {?Node} The retrieved node, or null if there lacks a node to
     * retrieve.
     */
    get (lookupIndex) {
      if (lookupIndex < 0 || lookupIndex > this.length - 1) return null
      // With references between nodes going forward and backward, we may
      // choose whether to begin at the start or end of the list. Even
      // though both approaches yield O(n), pick whichever is faster.
      const startAtHead = lookupIndex + 1 <= Math.floor(this.length/ 2)
      let node = startAtHead ? this.head : this.tail
      let i = startAtHead ? 0 : this.length - 1
      while (node !== null && i !== lookupIndex) {
        node = startAtHead ? node.next : node.previous
        i += startAtHead ? 1 : -1
      }
      return node
    },

    /**
     * Set a node's contained value at a specific index.
     * @param index
     * @param value
     * @returns {?Node} The retrieved node, or null if there lacks a node to
     * retrieve.
     */
    set (index, value) {
      const node = this.get(index)
      if (node !== null) node.value = value
      return node
    },

    /**
     * Inserts a node at a specific index either at the list's start, end, or
     * somewhere in the middle.
     * @param index
     * @param value
     * @returns {?Node} The inserted node, or null if the index did not fit
     * within the bounds of the list.
     */
    insert (index, value) {
      if (index > this.length || index < 0) return null
      if (index === 0) return this.shift(value)
      if (index === this.length) return this.push(value)
      const newNode = Node(value)
      const existingNode = this.get(index)
      newNode.next = existingNode
      newNode.previous = existingNode.previous
      existingNode.previous.next = newNode
      existingNode.previous = newNode
      this.length++
      return newNode
    },

    /**
     * Removes a node from the list at a specific index.
     * @param index
     * @returns {?Node} The removed node, or null if there lacks a node to
     * remove.
     */
    remove(index) {
      if (index < 0 || index > this.length - 1) return null
      if (index === this.length - 1) return this.pop()
      if (index === 0) return this.shift()
      const nodeToRemove = this.get(index)
      const nodeBefore = nodeToRemove.previous
      const nodeAfter = nodeToRemove.next
      nodeBefore.next = nodeAfter
      nodeAfter.previous = nodeBefore
      nodeToRemove.previous = null
      nodeToRemove.next = null
      this.length--
      return nodeToRemove
    },

    /**
     * Reverse the list in place.
     * @returns {DoublyLinkedList} The reversed list.
     */
    reverse () {
      let node = this.head
      while (node !== null) {
        // Es6 array destructuring
        [node.next, node.previous] = [node.previous, node.next]
        // Remember, we just reversed the next and previous properties, so to
        // move to the next node we use node.previous
        node = node.previous
      }
      [this.head, this.tail] = [this.tail, this.head]
      return this
    }
  }
  // Create object based on prototype object (only transfers property names)
  const doublyLinkedList = Object.create(prototype)
  // Assign prototype property values to object.
  Object.assign(doublyLinkedList, prototype)
  return doublyLinkedList
}