带你读《图解算法小抄》二、双向链表（3）

export default class DoublyLinkedList {
  /**
   * @param {Function} [comparatorFunction]
   */
  constructor(comparatorFunction) {
    /** @var DoublyLinkedListNode */
    // 双向链表的头节点
    this.head = null;
    /** @var DoublyLinkedListNode */
    // 双向链表的尾节点
    this.tail = null;
    // 用于比较的函数
    this.compare = new Comparator(comparatorFunction);
  }
  /**
   * @param {*} value
   * @return {DoublyLinkedList}
   */
  // 将新的节点插入到头部
  prepend(value) {
    // 创建新的节点作为头部节点
    const newNode = new DoublyLinkedListNode(value, this.head);
    // 如果存在头部节点，那么它不再是头部节点了。
    // 因此，将其前驱节点设置为新节点（新的头部节点）。
    // 然后标记新的节点为头部节点。
    if (this.head) {
      this.head.previous = newNode;
    }
    this.head = newNode;
    // 如果还没有尾部节点，那么就让新的节点成为尾部节点。
    if (!this.tail) {
      this.tail = newNode;
    }
    return this;
  }
  /**
   * @param {*} value
   * @return {DoublyLinkedList}
   */
  // 将新的节点追加到尾部
  append(value) {
    const newNode = new DoublyLinkedListNode(value);
    // 如果还没有头部节点，让新的节点成为头部节点。
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return this;
    }
    // 将新的节点添加到链表的末尾。
    this.tail.next = newNode;
    // 将当前尾部节点添加到新节点的前驱引用。
    newNode.previous = this.tail;
    // 设置新节点为链表的尾部节点。
    this.tail = newNode;
    return this;
  }
  /**
   * @param {*} value
   * @return {DoublyLinkedListNode}
   */
  // 删除具有特定值的节点
  delete(value) {
    if (!this.head) {
      return null;
    }
    let deletedNode = null;
    let currentNode = this.head;
    while (currentNode) {
      if (this.compare.equal(currentNode.value, value)) {
        deletedNode = currentNode;
        if (deletedNode === this.head) {
          // 如果要删除的是头部节点...
          // 将头部节点设置为第二个节点，它将成为新的头部节点。
          this.head = deletedNode.next;
          // 将新头部节点的前驱设置为 null。
          if (this.head) {
            this.head.previous = null;
          }
          // 如果链表中的所有节点的值都和传入的参数相同
          // 那么所有节点都会被删除，因此需要更新尾部节点。
          if (deletedNode === this.tail) {
            this.tail = null;
          }
        } else if (deletedNode === this.tail) {
          // 如果要删除的是尾部节点...
          // 将尾部节点设置为倒数第二个节点，它将成为新的尾部节点。
          this.tail = deletedNode.previous;
          this.tail.next = null;
        } else {
          // 如果要删除的是中间节点...
          const previousNode = deletedNode.previous;
          const nextNode = deletedNode.next;
          previousNode.next = nextNode;
          nextNode.previous = previousNode;
        }
      }
      currentNode = currentNode.next;
    }
    return deletedNode;
  }
  /**
   * @param {Object} findParams
   * @param {*} findParams.value
   * @param {function} [findParams.callback]
   * @return {DoublyLinkedListNode}
   */
  // 查找具有特定值或满足回调函数的节点
  find({ value = undefined, callback = undefined }) {
    if (!this.head) {
      return null;
    }
    let currentNode = this.head;
    while (currentNode) {
      // 如果指定了回调函数，那么尝试通过回调函数找到节点。
      if (callback && callback(currentNode.value)) {
        return currentNode;
      }
      // 如果指定了值，那么尝试通过值找到节点。
      if (value !== undefined && this.compare.equal(currentNode.value, value)) {
        return currentNode;
      }
      currentNode = currentNode.next;
    }
    return null;
  }
  /**
   * @return {DoublyLinkedListNode}
   */
  // 删除尾部节点
  deleteTail() {
    if (!this.tail) {
      // 没有尾部节点可以删除
      return null;
    }
    if (this.head === this.tail) {
      // 链表中只有一个节点
      const deletedTail = this.tail;
      this.head = null;
      this.tail = null;
      return deletedTail;
    }
    // 如果链表中有很多节点...
    const deletedTail = this.tail;
    this.tail = this.tail.previous;
    this.tail.next = null;
    return deletedTail;
  }
  /**
   * @return {DoublyLinkedListNode}
   */
  // 删除头部节点
  deleteHead() {
    if (!this.head) {
      return null;
    }
    const deletedHead = this.head;
    if (this.head.next) {
      this.head = this.head.next;
      this.head.previous = null;
    } else {
      this.head = null;
      this.tail = null;
    }
    return deletedHead;
  }
  /**
   * @return {DoublyLinkedListNode[]}
   */
  // 将链表转换为数组
  toArray() {
    const nodes = [];
    let currentNode = this.head;
    while (currentNode) {
      nodes.push(currentNode);
      currentNode = currentNode.next;
    }
    return nodes;
  }
  /**
   * @param {*[]} values - 需要转换为链表的值的数组。
   * @return {DoublyLinkedList}
   */
  // 从数组创建链表
  fromArray(values) {
    values.forEach((value) => this.append(value));
    return this;
  }
  /**
   * @param {function} [callback]
   * @return {string}
   */
  // 将链表转换为字符串
  toString(callback) {
    return this.toArray().map((node) => node.toString(callback)).toString();
  }
  /**
   * 反转链表。
   * @returns {DoublyLinkedList}
   */
  reverse() {
    let currNode = this.head;
    let prevNode = null;
    let nextNode = null;
    while (currNode) {
      // 存储下一个节点。
      nextNode = currNode.next;
      prevNode = currNode.previous;
      // 改变当前节点的下一个节点，使其链接到前一个节点。
      currNode.next = prevNode;
      currNode.previous = nextNode;
      // 将 prevNode 和 currNode 节点向前移动一步。
      prevNode = currNode;
      currNode = nextNode;
    }
    // 重置头部和尾部节点。
    this.tail = this.head;
    this.head = prevNode;
    return this;
  }
}