链表

Add(value)
  Pre: value is the value to add to the list
  Post: value has been placed at the tail of the list
  n ← node(value)
  if head = ø
    head ← n
    tail ← n
  else
    tail.next ← n
    tail ← n
  end if
end Add

Add(value)
  Pre: value is the value to add to the list
  Post: value has been placed at the tail of the list
  //value是将被插入链表的元素
  //操作结束后value被插入到链表的结尾
  n ← node(value)//将value在值变成一个节点然后赋值给n
  if head = ø//如果头部节点是空节点，那么头节点和尾节点都赋值为n
    head ← n
    tail ← n
  else//如果头节点不为空节点，那么尾节点的下一个节点是n，然后将尾节点指针移动到n上
    tail.next ← n
    tail ← n
  end if
end Add

Contains(head, value)
  Pre: head is the head node in the list
       value is the value to search for
  Post: the item is either in the linked list, true; otherwise false
  n ← head
  while n != ø and n.value != value
    n ← n.next
  end while
  if n = ø
    return false
  end if
  return true
end Contains

Contains(head, value)
  Pre: head is the head node in the list
       value is the value to search for
  Post: the item is either in the linked list, true; otherwise false
  //head是头节点指针，value是查询的值
  //如果链表中存在value值，返回true，否则返回false
  n ← head//头节点赋值给n
  while n != ø and n.value != value//如果头节点不是空节点并且节点值和value不相等，就移动到下一个节点继续判断
    n ← n.next
  end while
  if n = ø//循环结束后如果n是空节点，则说明没找到，返回false
    return false
  end if
  return true//否则找到，返回true
end Contains

Remove(head, value)
  Pre: head is the head node in the list
       value is the value to remove from the list
  Post: value is removed from the list, true, otherwise false
  if head = ø
    return false
  end if
  n ← head
  if n.value = value
    if head = tail
      head ← ø
      tail ← ø
    else
      head ← head.next
    end if
    return true
  end if
  while n.next != ø and n.next.value != value
    n ← n.next
  end while
  if n.next != ø
    if n.next = tail
      tail ← n
    end if
    n.next ← n.next.next
    return true
  end if
  return false
end Remove

Remove(head, value)
  Pre: head is the head node in the list
       value is the value to remove from the list
  Post: value is removed from the list, true, otherwise false
  //head是头节点
  //value被删除成功返回true，否则返回false
  if head = ø//如果头节点为空节点，返回false
    return false
  end if
  n ← head//头节点赋值给n
  if n.value = value//如果头节点的值等于value
    if head = tail//如果头节点就是尾节点，也就是说链表只有一个元素，就给头尾节点都赋值为空节点
      head ← ø
      tail ← ø
    else//否则给头节点赋值下一个节点，将原来的头节点删除
      head ← head.next
    end if
    return true
  end if
  while n.next != ø and n.next.value != value//循环，如果下一个节点不是空节点并且值和value不相等，就给n赋值下一个节点
    n ← n.next
  end while
  if n.next != ø//如果n的下一个节点不是空节点
    if n.next = tail//如果下一个节点是尾节点，则尾指针移动到n上，将n.next删除了
      tail ← n
    end if
    n.next ← n.next.next//n.next.next移动到n.next
    return true//删除成功，返回true
  end if
  return false//没有删除任何节点，返回false
end Remove

Traverse(head)
  Pre: head is the head node in the list
  Post: the items in the list have been traversed
  n ← head
  while n != ø
    yield n.value
    n ← n.next
  end while
end Traverse

Traverse(head)
  Pre: head is the head node in the list
  Post: the items in the list have been traversed
  //head是头节点
  //运行之后链表被遍历一遍
  n ← head//头节点赋值给n
  while n != ø//如果n不是空节点
    yield n.value//生成当前节点的值
    n ← n.next//指针移动到下一个节点
  end while
end Traverse

ReverseTraversal(head, tail)
  Pre: head and tail belong to the same list
  Post: the items in the list have been traversed in reverse order
  if tail != ø
    curr ← tail
    while curr != head
      prev ← head
      while prev.next != curr
        prev ← prev.next
      end while
      yield curr.value
      curr ← prev
    end while
   yeild curr.value
  end if
end ReverseTraversal

ReverseTraversal(head, tail)
  Pre: head and tail belong to the same list
  Post: the items in the list have been traversed in reverse order
  //head和tail是头尾节点
  //链表被反向遍历一遍
  if tail != ø//如果尾节点不为空节点
    curr ← tail//尾节点赋值给curr
    while curr != head//如果curr不等于头节点
      prev ← head//头节点赋值给prev
      while prev.next != curr//如果prev.next不等于尾节点，prev移动到下一个节点
        prev ← prev.next
      end while
      yield curr.value//生成当前节点的值
      curr ← prev//prev赋值给curr
    end while
   yeild curr.value//生成最后一个头节点的值
  end if
end ReverseTraversal

export default class LinkedListNode {//链表节点类，实例化后就是一个链表节点
  constructor(value, next = null) {//构造函数，value参数是节点的值，next是指向下一个节点的指针，next默认值是null
    //链表节点对象有两个属性，一个是节点的值value，一个是下一个节点的指针next
    this.value = value;
    this.next = next;
  }

  toString(callback) {//toString方法，返回当前节点的值，支持自定义回调函数处理当前节点值
    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);
  }
}