复杂度

时间复杂度

获取：O(n)

查询：O(n)

插入：O(1)

删除：O(1)

空间复杂度

O(n)

DoublyLinkedListNode：

export default class DoublyLinkedListNode {  constructor(value, next = null, previous = null) {    this.value = value;    this.next = next;    this.previous = previous;  }  toString(callback) {    return callback ? callback(this.value) : `${
   this.value}`;  }}

DoublyLinkedList：

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) {
    //头插法1.头节点存在2.正常3.尾指针不存在    // Make new node to be a head.    const newNode = new DoublyLinkedListNode(value, this.head);    // If there is head, then it won't be head anymore.    // Therefore, make its previous reference to be new node (new head).    // Then mark the new node as head.    if (this.head) {      this.head.previous = newNode;    }    this.head = newNode;    // If there is no tail yet let's make new node a tail.    if (!this.tail) {      this.tail = newNode;    }    return this;  }  /**   * @param {*} value   * @return {DoublyLinkedList}   */  append(value) {
    //尾插法，1.头节点不存在2.其他情况    const newNode = new DoublyLinkedListNode(value);    // If there is no head yet let's make new node a head.    if (!this.head) {      this.head = newNode;      this.tail = newNode;      return this;    }    // Attach new node to the end of linked list.    this.tail.next = newNode;    // Attach current tail to the new node's previous reference.    newNode.previous = this.tail;    // Set new node to be the tail of linked list.    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) {          // If HEAD is going to be deleted...          // Set head to second node, which will become new head.          this.head = deletedNode.next;          // Set new head's previous to null.          if (this.head) {            this.head.previous = null;          }          // If all the nodes in list has same value that is passed as argument          // then all nodes will get deleted, therefore tail needs to be updated.          if (deletedNode === this.tail) {            this.tail = null;          }        } else if (deletedNode === this.tail) {          // If TAIL is going to be deleted...          // Set tail to second last node, which will become new tail.          this.tail = deletedNode.previous;          this.tail.next = null;        } else {          // If MIDDLE node is going to be deleted...          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 is specified then try to find node by callback.      if (callback && callback(currentNode.value)) {        return currentNode;      }      // If value is specified then try to compare by value..      if (value !== undefined && this.compare.equal(currentNode.value, value)) {        return currentNode;      }      currentNode = currentNode.next;    }    return null;  }  /**   * @return {DoublyLinkedListNode}   */  deleteTail() {    if (!this.tail) {      // No tail to delete.      return null;    }    if (this.head === this.tail) {      // There is only one node in linked list.      const deletedTail = this.tail;      this.head = null;      this.tail = null;      return deletedTail;    }    // If there are many nodes in linked list...    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 - Array of values that need to be converted to linked list.   * @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();  }  /**   * Reverse a linked list.   * @returns {DoublyLinkedList}   */  reverse() {    let currNode = this.head;    let prevNode = null;    let nextNode = null;    while (currNode) {      // Store next node.      nextNode = currNode.next;      prevNode = currNode.previous;      // Change next node of the current node so it would link to previous node.      //逆置。      currNode.next = prevNode;      currNode.previous = nextNode;      // Move prevNode and currNode nodes one step forward.      prevNode = currNode;      currNode = nextNode;    }    // Reset head and tail.    this.tail = this.head;    this.head = prevNode;    return this;  }}

note:

1.

it('should prepend node to linked list', () => {    const linkedList = new DoublyLinkedList();    linkedList.prepend(2);    expect(linkedList.head.toString()).toBe('2');    expect(linkedList.tail.toString()).toBe('2');    linkedList.append(1);    linkedList.prepend(3);//3<- ->2<- ->1    expect(linkedList.head.next.next.previous).toBe(linkedList.head.next);    expect(linkedList.tail.previous.next).toBe(linkedList.tail);    expect(linkedList.tail.previous.value).toBe(2);    expect(linkedList.toString()).toBe('3,2,1');  });

2.通过回调查找函数

it('should find node by callback', () => {    const linkedList = new DoublyLinkedList();    linkedList      .append({ value: 1, key: 'test1' })      .append({ value: 2, key: 'test2' })      .append({ value: 3, key: 'test3' });    const node = linkedList.find({ callback: value => value.key === 'test2' });    expect(node).toBeDefined();    expect(node.value.value).toBe(2);    expect(node.value.key).toBe('test2');    expect(linkedList.find({ callback: value => value.key === 'test5' })).toBeNull();  });

3.双向链表逆置算法：

reverse() {    let currNode = this.head;    let prevNode = null;    let nextNode = null;    while (currNode) {      // Store next node.找到前后结点。      nextNode = currNode.next;      prevNode = currNode.previous;      // Change next node of the current node so it would link to previous node.      //逆置。      currNode.next = prevNode;      currNode.previous = nextNode;      // Move prevNode and currNode nodes one step forward.反复进行。      prevNode = currNode;      currNode = nextNode;    }    // Reset head and tail.    this.tail = this.head;    this.head = prevNode;    return this;  }