createDoublyLinkedList.js

const createDoublyLinkedList = arr => {
  class Node {
    constructor(v) {
      this.v = v;
      this.l = null;
      this.r = null;
    }
    static createNode(v) {
      return new Node(v);
    }
    setL(node) {
      this.l = node;
    }
    setR(node) {
      this.r = node;
    }
    toString() {
      return String(this.v);
    }
    valueOf() {
      return this.v;
    }
  }
  class DoublyLinkedList {
    constructor(array) {
      this.set = new Set();
      this.head = null;
      this.tail = null;
      const nodes = array.map(Node.createNode);
      for (const key in nodes) {
        const index = key | 0;
        const l = nodes[index - 1];
        const v = nodes[index];
        const r = nodes[index + 1];
        l ? v.setL(l) : (this.head = v);
        r ? v.setR(r) : (this.tail = v);
        this.set.add(v);
      }
    }
    *[Symbol.iterator]() {
      let cursor = this.head;
      while (cursor) {
        yield cursor.v;
        cursor = cursor.r;
      }
    }
    get length () {
      return this.set.size;
    }
    pop() {
      const {tail} = this;
      const {l: newTail} = tail;
      tail.setL(null);
      newTail.setR(null);
      this.set.delete(tail);
      this.tail = newTail;
      return tail;
    }
    push(v) {
      const {tail} = this;
      const newTail = new Node(v);
      tail.setR(newTail);
      newTail.setL(tail);
      this.set.add(newTail);
      this.tail = newTail;
      return this.set.size;
    }
    shift() {
      const {head} = this;
      const {r: newHead} = head;
      head.setR(null);
      newHead.setL(null);
      this.set.delete(head);
      this.head = newHead;
      return head;
    }
    unshift(v) {
      const {head} = this;
      const newHead = new Node(v);
      head.setL(newHead);
      newHead.setR(head);
      this.set.add(newHead);
      this.head = newHead;
      return this.set.size;
    }
    exchange(a, b) {
      if (a === b) return [a, b];
      [a.l, a.r, b.l, b.r] =
        a.r === b && [b, b.r, a.l, a] ||
        a.l === b && [b.l, b, a, a.r] ||
        [b.l, b.r, a.l, a.r];
      a.l && (a.l.r = a);
      a.r && (a.r.l = a);
      b.l && (b.l.r = b);
      b.r && (b.r.l = b);
      [a, b].forEach(node => (
        !node.l && (this.head = node),
        !node.r && (this.tail = node)
      ));
      return [a, b];
    }
    quickSort(since = this.head, until = this.tail) {
      const pivot = since;
      let leftBoundary = null;
      let cursor = since;
      while (cursor && cursor.l !== until) {
        if (pivot.v > cursor.v) {
          !leftBoundary && (leftBoundary = cursor);
          this.exchange(pivot.r, cursor);
          this.exchange(pivot, cursor);
        }
        cursor = cursor.r;
      }
      leftBoundary && pivot.l !== leftBoundary && this.quickSort(leftBoundary, pivot.l);
      ![pivot.l, pivot.r].includes(until) && pivot.r && this.quickSort(pivot.r, until);
      return this;
    }
  }
  return new DoublyLinkedList(arr);
};