Description and implementation of a singly linked list data structure.

singly-linked-list.js

/**
 * Title: Singly Linked List
 * Author: Dylan Landry
 * Date: Wed 26 Jun 2019 13:38:38 EDT
 * Permalink: https://gist.github.com/dyllandry/371505391a608abb9d979a1ea258cff9
 *
 * Description:
 * A kind of data structure similar to a train.
 * Each node, a container for a value, knows only of the node ahead of 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.
 *  - Contrast with an regular array's O(n) performance when adding to the end.
 *
 * 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) (doesn't include searching which is O(n))
 * - Removal:
 *   - Beginning: O(1)
 *   - End: O(n)
 * - 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. A factory function.
 * @returns {Node}
 */
function Node (value) {
  const prototype = {
    value,
    next: null
  }
  // Create object based on prototype object (only copies property names).
  const node = Object.create(prototype)
  // Assign property values from prototype to object.
  Object.assign(node, prototype)
  return node
}

/**
 * Creates a singly linked list. A factory function.
 * @returns {SinglyLinkedList}
 */
function SinglyLinkedList () {
  const prototype = {
    // A maintained reference to the first node in the list.
    head: null,

    // A maintained reference to the last node in the list.
    tail: null,

    // the total number of nodes in the list.
    length: 0,

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

    /*
     * Removes the last node from the list.
     * @returns {?Node} The removed node, or null if there lacks a node
     * to remove.
     */
    pop () {
      if (this.tail === null) return null
      const oldTail = this.tail
      const newTail = this.get(this.length - 2)
      this.tail = newTail
      if (newTail !== null) newTail.next = null
      this.length--
      if (this.length === 0) this.head = null
      return oldTail
    },

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

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

    /**
     * Gets a node at a specific index.
     * @param index
     * @returns {?Node} The retrieved node, or null if there lacks a node
     * to retrieve at the given index.
     */
    get (index) {
      if (
        this.length === 0 ||
        index < 0 ||
        index > this.length
      ) return null
      while (index >= 0) {
        // First time node is set to this.head because node is undefined
        // Subsequent times node is set to node.next
        var nodeToReturn = nodeToReturn ? nodeToReturn.next : this.head
        index--
      }
      // Variable is declared because var declarations are function scoped
      return nodeToReturn
    },

    /**
     * Set an existing node's contained value.
     * @param index
     * @param value
     * @returns {?Node} The set node, or null if no node was found.
     */
    set (index, value) {
      const foundNode = this.get(index)
      if (foundNode !== null) foundNode.value = value
      // Example: Object -> false -> true
      // Example: null -> true -> false
      return foundNode
    },

    /**
     * Insert a node within the list, either at the beginning, end, or
     * somewhere in the middle.
     * @param index
     * @param value
     * @returns {?Node} The inserted node, or null if the insertion index was
     * outside the bounds of the list.
     */
    insert (index, value) {
      if (index > this.length || index < 0) return null
      if (index === this.length) return this.push(value)
      if (index === 0) return this.unshift(value)
      const newNode = Node(value)
      const nodeBefore = this.get(index - 1)
      newNode.next = nodeBefore.next
      nodeBefore.next = newNode
      return newNode
    },

    /**
     * Remove a node from the list at an index.
     * @param index
     * @returns {?Node} The removed node, or null if a node was not found.
     */
    remove (index) {
      if (index > this.length - 1 || index < 0) return null
      if (index === 0) return this.shift()
      if (index === this.length - 1) return this.pop()
      const nodeBefore = this.get(index - 1)
      const nodeToRemove = nodeBefore.next
      nodeBefore.next = nodeToRemove.next
      nodeToRemove.next = null
      this.length--
      return nodeToRemove
    },

    /**
     * Reverses the list in place.
     * @returns {SinglyLinkedList}
     */
    reverse () {
      // Start at head and go to tail.
      // Swap node.next value with node previously iterated on (null at first)
      // Maintain a reference to the next node so we can keep iterating through
      for (let i = 0; i < this.length; i++) {
        const node = nextNodeToReverse || this.head
        var nextNodeToReverse = node.next
        node.next = previousNode || null
        var previousNode = node
      }
      const oldTail = this.tail
      this.tail = this.head
      this.head = oldTail
      return this
    }
  }
  // Create object based on prototype object (only uses poperty names).
  const list = Object.create(prototype)
  // Assign property values from prototype to object.
  Object.assign(list, prototype)
  return list
}