(Doubley) Linked List

LinkedList.js

/**
 * Double Linked list
 */
export default class LinkedList {

  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  /**
   * Iterator for Linked list so it can be used with common iteration operators
   *
   * @returns {ListNode} - next list node
   */
  *[Symbol.iterator]() {
    let current = this.head;

    while (current.next !== null) {
      yield current;
      current = current.next;
    }

    yield current;
  }

  /**
   * Push a list node to this list
   *
   * @param {string|number} data - value of the list node
   * @returns {boolean} - true if operation was successful
   */
  push(data) {

    const node = new ListNode(data);

    if (!this.size) {
      // if this is the first node make it head and tail
      this.head = node;
      this.tail = node;
    } else {
      // append the node to the old tail and set new tail
      this.tail.append(node);
      this.tail = node;
    }

    this.size++;

    return true;
  }

  /**
   * Call function with each node
   *
   * @param {function} cb - callback to call on each node
   * @param {ListNode} [node = this.head] - node to invoke cb on
   * @returns {cb~inner} - the returned callback
   */
  forEach(cb, node = this.head) {

    if (node.next) {
      this.forEach(cb, node.next);
    }
    /**
     * callback
     *
     * @param {ListNode} node - current node
     * @returns {cb~inner} - the result of the returned callback
     */
    return cb(node);

  }

  /**
   * Find an item in this list
   *
   * @param {number|string} data - data to search for
   * @returns {null|ListNode} - list node if found
   */
  find(data) {

    let result = null;

    this.forEach(node => {
      if (node.data === data) {
        result = node;
      }
    });

    return result;
  }
}


/**
 * List Node for Linked lists
 */
export class ListNode {

  constructor(data) {
    this.next = null;
    this.prev = null;
    this.data = data;
  }

  /**
   * Appends a node after this one
   *
   * @constructor
   * @param {ListNode} node - node to append
   */
  append = (node) => {
    this.next = node;
    node.prev = this;
  }
}

LinkedList.spec.js

import test from 'ava';
import LinkedList from 'utils/LinkedList';

const SIZE = 100;
function setup(config = {size: SIZE}) {

  const data = Array.from(Array(config.size).keys());

  const linkedList = new LinkedList();

  return {
    data,
    linkedList,
  }
}

test('LinkedList constructor', t => {

  const {linkedList, data} = setup();

  linkedList.push(1);

  t.is(linkedList.head.data, 1);

  linkedList.push(2);

  t.is(linkedList.head.next.data, 2);

});


test('LinkedList method [Symbol.iterator]', t => {

  const {linkedList, data} = setup();

  for (const value of data) {
    linkedList.push(value);
  }

  t.is(linkedList.size, SIZE);
  let i = 0;

  for (const link of linkedList) {
    t.is(link.data, i);
    i++;
  }
});

test('LinkedList method forEach', t => {

  const {linkedList, data} = setup();

  for (const value of data) {
    linkedList.push(value);
  }

  let total = 0;

  linkedList.forEach((node) => (total += node.data));

  t.is(total, data.reduce((t, c) => t + c, 0))

});

test('LinkedList method find', t => {

  const {linkedList, data} = setup();

  for (const value of data) {
    linkedList.push(value);
  }

  t.is(linkedList.find(10).next.data, 11);

});