[js-data-structure] JS数据结构 #JavaScript

node-list.js

/**
 * Node definition
 */
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

/**
 * Lined-list definition
 * 链表常用方法
 */
class NodeList {
  constructor() {
    this.size = 0;
    this.head = this.tail = null;
  }

  /**
   * Add element at the beginning.
   * @param {object} item
   */
  addFirst(item) {
    const node = new Node(item);

    if (!this.head) this.head = this.tail = node;
    else {
      node.next = this.head;
      this.head = node;
    }

    this.size++;
  }

  /**
   * Add element at the end.
   * @param {object} item
   */
  addLast(item) {
    const node = new Node(item);

    if (!this.head) this.head = this.tail = node;
    else {
      this.tail.next = node;
      this.tail = node;
    }

    this.size++;
  }

  /**
   * Index of element in node list.
   * @param {object} item
   */
  indexOf(item) {
    let [current, index] = [this.head, 0];

    while (current && current.data !== item) {
      current = current.next ? current.next : null;
      index++;
    }

    return current ? index : -1;
  }

  /**
   * Is contained in node list.
   * @param {object} item
   */
  contains(item) {
    return this.indexOf(item) !== -1;
  }

  /**
   * Remove element at the beginning.
   */
  removeFirst() {
    if (!this.head) throw new Error("NoSuchElement");

    if (this.head === this.tail) this.head = this.tail = null;
    else this.head = this.head.next;

    this.size--;
  }

  /**
   * Remove element at the end.
   */
  removeLast() {
    if (!this.head) throw new Error("NoSuchElement");

    if (this.head === this.tail) this.head = this.tail = null;
    else {
      const previous = this.getPreviousNode(this.tail);
      this.tail = previous;
      this.tail.next = null;
    }

    this.size--;
  }

  /**
   * Convert node list to array.
   */
  toArray() {
    let [array, current] = [[], this.head];

    while (current) {
      array.push(current.data);
      current = current.next;
    }

    return array;
  }

  /**
   * Get previous node for the given node.
   * @param {NodeList} node
   */
  getPreviousNode(node) {
    let current = this.head;

    while (current) {
      if (current.next === node) return current;
      current = current.next;
    }

    return null;
  }
}

queue.js

/**
 * JavaScript 队列queue
 * FIFO enqueue/dequeue/peek/isEmpty
 * @author CodecWang
 */
class Queue {
  constructor() {
    this.item = [];
  }

  enqueue(element) {
    this.item.unshift(element);
  }

  dequeue() {
    this.item.pop();
  }

  peek() {
    return this.item[this.item.length - 1];
  }

  isEmpty() {
    return this.item.length === 0;
  }
}

stack.js

/**
 * JavaScript 栈stack
 * LIFO push/pop/peek/isEmpty
 * @author CodecWang
 */
class Stack {
  constructor() {
    this.item = [];
  }

  push(element) {
    this.item.push(element);
  }

  pop() {
    return this.item.pop();
  }

  peek() {
    return this.item[this.item.length - 1];
  }

  isEmpty() {
    return this.item.length === 0;
  }
}