关于javascript:javascript-数据结构系列-二-双向链表

明天持续讲数据结构双向链表 DoublyLinkedList具体实现
波及两个类DoublyLinkedListNode DoublyLinkedList
首先,看一下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);  }}

append 办法

  /**   * @param {*} value   * @return {DoublyLinkedList}   */  append(value) {    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;  }

delete 办法

  /**   * @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;  }

find 办法

  /**   * @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;  }

reverse 办法

  /**   * 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;  }