链表

• 多个元素组成的列表
• 元素的存储是不连续的，用next指针连在一起

数组 vs链表

• 数组：增删非首尾元素时往往需要移动元素
• 链表：增删非首位元素时，不需要移动元素、只需要更改next指向就好了

JS 的实现

• javaScript没有链表，但可以用object来实现

原型链

• 下面用a -> b表示，a.proto等于b
• obj -> Object.prototype -> null
• func -> Function.prototype -> Object.prototype -> null
• arr -> Array.prototype -> Object.prototype -> nullz
• 知识点
  • 如果A沿着原型链能找到B.prototype，那么， A instance of B 为true
  • 如果在A上面找不到的方法，会沿着A的原型链，层层向上找

单向链表

图示

JS实现

// 自定义一个类，用于比较
class Comparator {
    constructor(compareFunction) {
    // 如果有传进来比较函数，就用自身的比较函数
      this.compare = compareFunction || Comparator.defaultCompareFunction;
  }
  /*
  * 对比a,b
  *  a === b 返回0
  *     a  <  b 返回-1
  *  a  >  b 返回1
  */
  static defaultCompareFunction(a, b) {
      if(a === b) return 0;
    return a < b? -1: 1;
  }
  // 如果a === b 返回true
  equal(a, b) {
      return this.compare(a, b) === 0;
  }
  // 如果a < b 返回true
  lessThan(a, b) {
      return this.compare(a, b) < 0;
  }
  // 如果a > b 返回true
  greaterThan(a, b) {
        return this.compare(a, b) > 0;
    }
  // 如果a <= b 返回true
    lessThanOrEqual(a, b) {
      return this.lessThan(a, b) || this.equal(a, b);
  }
  // 如果a >= b 返回true
    greaterThanOrEqual(a, b) {
      return this.greaterThan(a, b) || this.equal(a, b);
  }
  // 反转这个类 的 比较顺序
  reverse() {
      const compareOriginal = this.compare;
    this.compare = (a, b) => compareOriginal(b, a);
  }
}

// 定义链表节点
class LinkedListNode {
    constructor(value, next = null) {
      this.value = value;
    this.next = next;
  }
  doSomething(callback) {
    console.log(this.value);
      callback && callback(this.value);
  }
}
// 定义链表
class LinkedList {
    constructor() {
      this.head = null;
    this.tail = null;
    this.compare = new Comparator(); // 本来可以接受一个比较函数，传进去，但是这里就不做了，没必要
  }
  // 在链表头(this.head)放节点
  prepend(value) {
    // 创建一个节点
    const newNode = new LinkedListNode(value, this.head);
      if(!this.tail) {
        this.tail = newNode;
    }
    return this;
  }
  // 在链表尾(this.tail)放节点
  append(value) {
      const newNode = new LinkedListNode(value);
    if (!this.head) {
      this.tail = newNode;
        this.head = newNode;
    } else {
      this.tail.next = newNode;
         this.tail = newNode;
    }
    return this;
  }
  // 删除节点
  delete(value) {
      if (!this.head) return null;
    let deleteNodes = [];
    // 从head开始找，如果一直是这个值，head就一直往下指
    while(this.head && this.compare.equal(this.head.value === value)) {
        deleteNodes.push(this.head);
      this.head = this.head.next;
    }
    // head不是这个值了，就往下找
    let currentNode = this.head;
    // 有可能经过上面的while循环，已经变成空链表
    if (currentNode !== null) {
        while(currentNode.next) {
          if(this.compare.equal(this.currentNode.next.value, value)) {
            deleteNodes.push(this.currentNode.next);
          this.currentNode.next = this.currentNode.next.next;
        } else {
            this.currentNode = this.currentNode.next;
        }
      }
    }
    // tail也要判断，万一等于value，上面的操作，都没有把它删掉过
    if(this.compare.equal(this.tail.value, value)) {
        this.tail = currentNode;
    }
    // 最后把删除的节点都返回
    return deleteNodes;
  }
  // 链表指向反转
  reverse() {
      // 需要用三个指针
    let currNode = this.head;
    let prevNode = null;
    let nextNode = null;
      while(currNode) {
      // 把下一个节点保存起来
        nextNode = currNode.next;
      // 反转currNode指向
      currNode.next = prevNode;
      // 移动prevNode和currNode指针，以便下次反转
      prevNode = currNode;
      currNode = nextNode;
    }
    // 记得把head和tail指针，交换位置
    this.tail = this.head;
    this.head = prevNode;
    return this;
  }
}