链表

 toString(callback) {
    return callback ? callback(this.value) : `${this.value}`;
  }

 const nodeValue = { value: 1, key: 'test' };
    const node = new LinkedListNode(nodeValue);
    const toStringCallback = value => `value: ${value.value}, key: ${value.key}`;

    expect(node.toString(toStringCallback)).toBe('value: 1, key: test');

expect(node.toString()).toBe('value: 1, key: test');

 toString(callback) {
    return callback ? callback(this.value) : `${this.value}`;
  }

import LinkedListNode from './LinkedListNode';
import Comparator from '../../utils/comparator/Comparator';

export default class LinkedList {//链表类
  /**
   * @param {Function} [comparatorFunction]
   */
  constructor(comparatorFunction) {//构造函数
    /** @var LinkedListNode */
    this.head = null;//头节点指针

    /** @var LinkedListNode */
    this.tail = null;//尾节点指针

    this.compare = new Comparator(comparatorFunction);//新实例化一个比较器对象存成compare属性
  }

  /**
   * @param {*} value
   * @return {LinkedList}
   */
  prepend(value) {//在链表最前面添加一个新的节点作为头节点,头插法
    // Make new node to be a head.
    const newNode = new LinkedListNode(value, this.head);//添加新节点在头节点之前
    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 {LinkedList}
   */
  append(value) {//在链表最后面添加一个新节点作为尾节点，尾插法
    const newNode = new LinkedListNode(value);//根据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;//将旧的尾节点和新尾节点连接起来
    this.tail = newNode;//尾指针指向新节点

    return this;
  }

  /**
   * @param {*} value
   * @return {LinkedListNode}
   */
  delete(value) {//删除值对应的节点
    if (!this.head) {//如果链表没有节点，返回null
      return null;
    }

    let deletedNode = null;//要删除的节点

    // If the head must be deleted then make next node that is differ
    // from the head to be a new head.
    //如果头节点必须被删除，就要确保下一个节点和头节点是不一样的新节点
    while (this.head && this.compare.equal(this.head.value, value)) {
      //循环条件：头指针存在且头节点的值和要删除的值相等
      deletedNode = this.head;//要被删除的头节点赋值给deletedNode
      this.head = this.head.next;//头指针指向头节点的下一个节点
    }

    let currentNode = this.head;//当前头节点

    if (currentNode !== null) {
      // If next node must be deleted then make next node to be a next next one.
      //如果下一个节点必须被删除，就让下一个节点变成下下个节点
      while (currentNode.next) {
        if (this.compare.equal(currentNode.next.value, value)) {
          deletedNode = currentNode.next;//要被删除的几点赋值给deletedNode
          currentNode.next = currentNode.next.next;//下下个节点赋值给下个节点
        } else {//如果下个节点不删除，就继续往下遍历
          currentNode = currentNode.next;
        }
      }
    }

    // Check if tail must be deleted.
    //如果尾节点要被删除就重新赋值尾指针
    if (this.compare.equal(this.tail.value, value)) {
      this.tail = currentNode;
    }

    return deletedNode;//返回最后一个被删除的节点
  }

  /**
   * @param {Object} findParams
   * @param {*} findParams.value
   * @param {function} [findParams.callback]
   * @return {LinkedListNode}
   */
  //查找指定值对应节点
  find({ value = undefined, callback = undefined }) {
    if (!this.head) {//如果链表没有节点，返回null
      return null;
    }

    let currentNode = this.head;//currentNode存头节点

    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..
      //如果指定了value就比较value是否相等来查找节点
      if (value !== undefined && this.compare.equal(currentNode.value, value)) {
        return currentNode;
      }

      currentNode = currentNode.next;//继续循环比较下一个节点
    }

    return null;//找不到返回null
  }

  /**
   * @return {LinkedListNode}
   */
  deleteTail() {//删除尾节点
    const deletedTail = this.tail;//存下尾节点

    if (this.head === this.tail) {//如果链表只有一个节点，头尾指针都置空然后返回被删除的尾节点
      // There is only one node in linked list.
      this.head = null;
      this.tail = null;

      return deletedTail;
    }

    // If there are many nodes in linked list...

    // Rewind to the last node and delete "next" link for the node before the last one.
    //如果链表有许多节点，就从头开始遍历，找到尾节点的前一个节点，将它的next指针置空即可
    let currentNode = this.head;
    while (currentNode.next) {
      if (!currentNode.next.next) {
        currentNode.next = null;
      } else {
        currentNode = currentNode.next;
      }
    }

    this.tail = currentNode;//设置尾指针

    return deletedTail;//返回被删除的尾节点
  }

  /**
   * @return {LinkedListNode}
   */
  //删除头节点
  deleteHead() {
    if (!this.head) {//如果链表没有节点，返回null
      return null;
    }

    const deletedHead = this.head;

    if (this.head.next) {//如果链表节点超过一个，就将头指针移动到下一个
      this.head = this.head.next;
    } else {//如果链表只有一个节点，就把头尾指针都置空
      this.head = null;
      this.tail = null;
    }

    return deletedHead;//返回被删除的头节点
  }

  /**
   * @param {*[]} values - Array of values that need to be converted to linked list.
   * @return {LinkedList}
   */
  //将一个数组内的每个元素作为新节点插入链表结尾
  fromArray(values) {
    values.forEach(value => this.append(value));

    return this;//返回链表对象
  }

  /**
   * @return {LinkedListNode[]}
   */
  toArray() {//将链表所有节点的值转换成一个数组
    const nodes = [];

    let currentNode = this.head;
    while (currentNode) {//遍历链表，将节点的值push到结果数组
      nodes.push(currentNode);
      currentNode = currentNode.next;
    }

    return nodes;
  }

  /**
   * @param {function} [callback]
   * @return {string}
   */
  toString(callback) {//返回将链表所有节点的值调用节点自身的toString方法经由callback处理后的值变成字符串组成的数组
    return this.toArray().map(node => node.toString(callback)).toString();
  }

  /**
   * Reverse a linked list.
   * @returns {LinkedList}
   */
  //将链表顺序反转
  reverse() {
    let currNode = this.head;
    let prevNode = null;
    let nextNode = null;

    while (currNode) {
      // Store next node.
      nextNode = currNode.next;//存下下一个节点

      // Change next node of the current node so it would link to previous node.
      currNode.next = prevNode;//当前节点的下一个节点赋值为上一个节点

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

export default class Comparator {//比较器类，用于实例化一个对象，上面有各种用于比较的工具方法
  /**
   * @param {function(a: *, b: *)} [compareFunction]
   */
  constructor(compareFunction) {//构造函数可以传入自定义的比较方法
    this.compare = compareFunction || Comparator.defaultCompareFunction;
    //对象上的compare属性是自定义比较方法或者默认的比较方法
  }

  /**
   * @param {(string|number)} a
   * @param {(string|number)} b
   * @returns {number}
   */
  static defaultCompareFunction(a, b) {//默认比较方法，相等返回0，小于返回-1，大于返回1
    if (a === b) {
      return 0;
    }

    return a < b ? -1 : 1;
  }

  equal(a, b) {//判断两个值是否相等
    return this.compare(a, b) === 0;
  }

  lessThan(a, b) {//判断是否a<b
    return this.compare(a, b) < 0;
  }

  greaterThan(a, b) {//判断是否a>b
    return this.compare(a, b) > 0;
  }

  lessThanOrEqual(a, b) {//判断a<=b
    return this.lessThan(a, b) || this.equal(a, b);
  }

  greaterThanOrEqual(a, b) {//判断a>=b
    return this.greaterThan(a, b) || this.equal(a, b);
  }

  reverse() {//a和b调换位置比较
    const compareOriginal = this.compare;
    this.compare = (a, b) => compareOriginal(b, a);
  }
}