链表！比数组更适合做增删操作的数据结构

2019-08-14 10:05:57来源：博客园阅读 ()

什么是链表？

链表和数组的对比：在大多数语言中，数组的大小是固定的，从数组的起点或中间添加或删除元素的成本很高，因为需要移动元素。
链表中的每一个元素在内存中不是连续放置的，和它左右两侧元素是没有关系的。
每个元素有一个存储元素本身的节点和指向下一个元素的引用组成。
相对于数组，链表的好处在于添加或删除元素的时候不需要移动其它元素。
在数组中我们可以直接访问任何位置的任何元素，而要想访问链表中的某一个元素，则需要从起点（链表头）开始迭代链表直到找到所需的元素。

举个栗子：一列火车是由一系列车厢组成的。每节车厢或车皮都相互连接，你很容易分离一节车箱，改变它的位置、添加或移除它。每节车厢相当于链表的元素，车厢间的对接扣就是元素的引用。

创建一个链表类

const defaultCompare = function (a, b) { // 一个比较函数
  if (a === b) return 0;
  return a < b ? -1 : 1;
}

class Node { // 一个助手类，用来表示我们想要添加到链表中的元素
  constructor(element, next) {
    this.element = element; // 元素的值
    this.next = next; // 指向链表中下一个元素的指针
  }
}

class LinkedList { // 链表类
    constructor(equalsFn = defaultEquals) {
    this.equalsFn = equalsFn; // 比较链表中的元素是否相等，默认a===b
    this.count = 0; // 链表中的元素数量
    this.head = undefined; // 表头
  }
}

创建几个链表的方法

向链表的尾部添加元素

push(element) {
    const node = new Node(element); // 创建node项
    let current; // 声明一个指向链表中的临时项
    if (this.head == undefined) { // 如果链表头为空，即链表为空
      this.head = node; // 直接让表头等于当前元素就好了，下一项（next）未传，因此为undefined
    } else {
      current = this.head; // 先让current等于第一个元素
      while (current.next != null) { // 只要当前元素的下一项元素不是假的，便继续循环
        current = current.next;
      }
      current.next = node; // 找到最后一个元素后，让它的下一个元素等于传进来的元素
    }
    this.count++;// 最后把总长度自增就好了
  }

首先初始化node类，把element作为值传入。
尾部添加元素分为两种情况，一种是链表为空，一种是链表有值，在后者时，因为链表只有链表头的引用，因此在向链表尾部添加元素时，我们需要循环列表，直到找到最后一个元素，为此我们需要一个指向链表中current项的变量。
如果链表头没值表示在向链表添加第一个元素，直接让表头等于当前元素就好了，下一项的引用（next）未传，因此为undefined
然后就是第二种情况，首先让current等于链表头，然后循环访问列表，直到找到最后一个元素，然后就是让最后一个元素的下一项的引用指向想要添加到链表的节点。
最后把总长度自增就好了

从特定位置移除一个元素

removeAt(index) {
    if (index >= 0 && index < this.count) { // 检查越界值
      let current = this.head;
      if (index === 0) { // 如果是表头
        this.head = current.next; // 就让表头等于下一个引用
      } else {
        let previous；
        for (let i = 0; i < index； i++) { // 嗯，开始迭代把~~~
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
        // 上一个的下一个等于现在的下一个，，，（现在内心os:我是谁，我在哪？？？）当前节点就会被丢弃在计算机内存中，等着被垃圾回收器移除
      }
      this.count--;// 长度自减
      return current.element; // 返回移除的元素
    }

    return undefined;
  }

由于该方法需要得到移除元素的index（位置），我们需要验证该index是从0到链表的长度之间的。如果不是就返回undefined。
如果移除的是链表中的第一个元素，就要让head指向列表的第二个元素。我们将current变量创建一个对链表中第一个元素的引用。这样current变量就是对链表中第一个元素的引用。这时候如果如果把head赋为current.next，就会移除第一个元素。我们也可以直接把head赋为head.next，不使用current。
如果我们要移除的是链表的最后一个元素或者中间的某个元素。就需要对链表进行迭代，直到到达目标位置。
在到达目标位置后，current变量就会变成我们想要从链表中移除的节点。因此，要从链表中移除当前元素，要做的就是将previous.next和current.next链接起来。这样，当前节点就会被丢弃在计算机内存中，等着被垃圾回收器清除。

循环迭代链表直到目标位置

getElementAt(index) {
    if (index >= 0 && index <= this.count) return undefined; // 检查越界值
    let node = this.head; // 默认等于表头
    for (let i = 0; i < index && node != null; i++) { // 嗯，开始迭代把~~~
      node = node.next;
    }
    return node;
  }

在remove方法中，我们需要迭代整个链表直到到达我们的目标索引index(位置)。循环到目标index的代码片段在链表方法中会经常用到。因此，我们可以将这部分逻辑独立为单独的办法，这样就可以在不同的地方复用它。
然后我们可以使用刚刚创建的getElementAt方法来重构remove方法

if(index===0){
    // 第一个位置的逻辑
} else {
    const previous = this.getElementAt(index - 1);
    current = previous.next;
    previous.next = current.next;
}
this.count--;

在任何位置插入元素

insert(element, index) {
    if (index >= 0 && index <= this.count) { // 边界处理
      const node = new Node(element); // 实例化当前元素
      if (index === 0) { // 如果插在表头
        const current = this.head;// 声明一个变量，等于原来的表头
        node.next = current;// 传入元素的下一个引用等于current
        this.head = node; // 当前表头等于传入的元素
      } else {
        const previous = this.getElementAt(index - 1);// 找到传入索引的上一个值
        previous.next = node;// 上一个的引用等于传入的值
        node.next = previous.next;// 传入值的下一个引用等于上一个的下一个引用
        
      }
      this.count++;// 总长度自增
      return true; // 最后返回true
    }
  return false; // 如果位置未找到返回false
}

先惯例的做一下边界处理。
首先如果是插在链表头，我们先声明一个变量等于原来的链表头，再让插入元素的先一个引用等于原来的current变量，最后让当前表头等于传入的元素。
如果是在链表中间或者末尾我们需要用getElementAt方法先找到目标位置的上一个元素，然后让上一个的引用等于传入的值。再把传入值的下一个引用等于上一个的下一个引用。最后一定记得把总长度加一，返回true

返回一个元素的位置

indexOf(element) {
    let current = this.head; // 等于表头
    for (let i = 0; i < this.size() && current != null; i++) { // 循环迭代所有元素
      if (this.equalsFn(element, current.element)) { // 找到和当前元素相等的第一个元素
        return i;// 返回索引
      }
      current = current.next;// 如果不相等，就继续迭代下一个
    }
    return -1; // 如果都没找到，就返回-1
  }

indexOf方法接收一个元素的值，如果在链表中找到了它，就返回元素的位置，否则返回-1。
一如既往，需要一个变量来帮助我们循环访问列表。该变量是current，它的初始值是head
然后迭代元素，从链表头开始，直到链表长度为止。为了确保不会发生运行时错误，我们可以验证一下current变量是否为null或undefined。
循环迭代所有元素直到找到和当前元素相等的第一个元素，返回它的所在位置
如果没找到，就返回-1

移除传入的元素

remove(element) { 
    const index = this.indexOf(element); // 先找到这个元素的第一个索引
    return this.removeAt(index); // 利用删除指定位置元素的方法，搞掉它
  }

我们已经有了一个用来移除给定位置元素的方法，也有了indexOf方法。利用indexOf方法找到它的位置，利用删除指定位置元素的方法，搞掉它。

检查是否为空，长度，获取链表头

isEmpty() {
    return this.size() === 0;
  }
  size() {
    return this.count;
  }
  getHead() {
    return this.head;
  }

还是比较简单的。

把所有元素转换成字符串

toString() {
    if (this.head == null) { // 如果列表为空，就返回空字符串
      return '';
    }
    let objString = `${this.head.element}`; // 创建一个变量，先让他等于表头的元素
    let current = this.head.next; // 等于表头的下一个引用
    for (let i = 1; i < this.size() && current != null; i++) { // 循环迭代所有元素
      objString = `${objString},${current.element}`; // 让这个字符串等于原来的字符串加上当前元素
      current = current.next; // 当前元素等于当前的下一个引用
    }
    return objString; // 最后把这个字符串返回
  }