doubly_linked_list.js

class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
    this.prev = null;
  }
}

// 简单的优化过性能......
class DoublyLinkedList {
  constructor() {
    this._length = 0;
    this._head = null;
    this._tail = null;
  }

  append(element) {
    let node = new Node(element);
    if (this._length === 0) {
      this._head = node;
      this._tail = node;
    } else {
      let current = this._tail;
      current.next = node;
      node.prev = current;
      this._tail = node;
    }
    this._length++;
  }

  insert(position, element) {
    let node = new Node(element);
    if (position > -1 && position <= this._length) {
      let current = this._head, index = 0, previous;
      if (position === 0) {
        if (this._head) {
          node.next = current;
          current.prev = node;
          this._head = node;
        } else {
          this._head = node;
          this._tail = node;
        }
      } else if (position === this._length) {
        current = this._tail;
        node.prev = current;
        current.next = node;
        this._tail = node;
      } else {
        while (index < position) {
          previous = current;
          current = current.next;
          index++;
        }
        previous.next = node;
        node.next = current;
        current.prev = node;
        node.prev = previous;
      }
      this._length++;
      return true;
    } else {
      return false;
    }
  }

  remove(element) {
    let index = this.indexOf(element);
    return this.removeAt(index);
  }

  removeAt(position) {
    let mid = Math.floor(this._length / 2);
    if (position >= mid) {
      return this._removeFromTail(position);
    } else {
      return this._removeFromHead(position);
    }
  }

  indexOf(element) {
    let current = this._head, index = 0;
    while (current) {
      if (current.element === element) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  }

  isEmpty() {
    return this._length === 0;
  }

  get size() {
    return this._length;
  }

  getHead() {
    return this._head;
  }

  getTail() {
    return this._tail;
  }

  print() {
    console.log(this.toString());
  }

  toString() {
    let current = this._head;
    let str = current ? current.element : '';
    while (current && current.next) {
      current = current.next;
      str += ', ' + current.element;
    }
    return str;
  }

  _removeFromHead(position) {
    if (position > -1 && position < this._length) {
      let current = this._head, index = 0, previous;
      if (position === 0) {
        this._head = current.next;
        if (this._length === 1) {
          this._tail = null;
        } else {
          this._head.prev = null;
        }
      } else {
        while (index < position) {
          previous = current;
          current = current.next;
          index++;
        }
        previous.next = current.next;
        current.next.prev = previous;
      }
      this._length--;
      return current.element;
    } else {
      return null;
    }
  }

  _removeFromTail(position) {
    if (position > -1 && position < this._length) {
      let current = this._tail, index = this._length - 1, previous;
       if (position === (this._length - 1)) {
         if (this._length === 1) {
           this._head = null;
           this._tail = null;
         } else {
           let current = this._tail;
           this._tail = current.prev;
           this._tail.next = null;
         }
      } else {
        while (index > position) {
          previous = current;
          current = current.prev;
          index--;
        }
        previous.prev = current.prev;
        current.prev.next = previous;
      }
      this._length--;
      return current.element;
    } else {
      return null;
    }
  }
}