前端学数据结构与算法（三）：链表为什么能和数组相提并论？实现数组

前言

说到线性的数据结构，那就不得不提链表，这一章我们从底层实现一个链表，并用它'高仿'一个数组，实现数组一系列的API，最后在性能上bettle下，从而更加深入理解这种数据结构的特性，也搞清楚为什么要理解这种数据结构。也许有一天实际的开发中，遇到某些场景，在我们习惯性的使用数组时，可以停下来思考几秒，也许这个场景用链表更合适(然后还是用数组)。

什么是链表？

简单来说链表是由一个个节点组成的，而每个节点之间的链接使用的是指针，通过指针把一个个节点串起来，形成一个链路。类似生活中的火车，火车有火车头，中间是火车的车厢，最后一节是尾车厢，再之后就是空。

image

因为是由一个个节点链接而成，所以这种数据结构在内存里存储时，就不会像数组那样需要整块连续的内存，而是一个个内存碎片链接而成，对内存的使用没有那么苛刻。还是老三样，想对一种数据结构有比较清晰的了解，还是得看它的增删查表现如何。首先实现一个节点类和链表类：

class ListNode { // 节点类
  constructor(val = null, node = null) {
    this.val = val; // 节点的值
    this.next = node; // 节点的指针
  }
}

class LinkedList { // 链表类
  constructor() {
    this.head = null; // 头指针
    this.size = 0; // 链表的长度
  }
}

查

因为链表不能像数组那样能根据下标随机访问，而需要从一个节点开始依次遍历，所以链表查找的效率并不高，例如我们来检查链表里包含有某个数，首先从头节点开始遍历，时间复杂度是O(n)。

image

class LinkedList {
  ...
  contains (val) {
    let cur = this.head; // 不能用head遍历，会改变head的指向
    while(cur !== null) { // 因为尾节点指向null
      if (cur.val === val) {
        return true;
      }
      cur = cur.next; // 指向下一个节点
    }
    return false; // 遍历结束木有
  }
}

增

与数组添加数据往尾部添加比较方便恰恰相反，链表的添加数据从头部添加会比较方便。这里又分为从头部添加，以及从头部之外的位置添加。

从头部添加时只需要做两件事，首先让新节点指向原来的头节点，然后将之前的头节点指向新节点，成为新的头节点。时间复杂度O(1)↓

image
代码如下：

class LinkedList {
  ...
  addFirst (val) {
    const node = new ListNode(val)
    node.next = this.head
    this.head = node
    
    // 可简写为 this.head = new ListNode(val, this.head)
  }
}

其余情况的添加节点，首先需要找到找到待插入节点之前的节点，然后将之前节点的指针指向新节点，新节点的指针指向待插入节点。时间复杂度是O(n)，因为需要先找到之前的节点。↓

image
代码如下：

class LinkedList {
  ...
  add (val, index) { // 指定下标位置添加节点
    if (index < 0 || index > this.size) { // 处理越界问题
      return
    }
    if (index === 0) { // 如果是首位添加，单独处理
      this.addFirst(val)
    } else {
      let prev = this.head // 这里要赋值给prev，因为如果用head遍历，会改变head的指向
      while(index > 1) { // 因为是找到之前的节点，所以少遍历一位
        prev = prev.next // 从头依次遍历下一个节点
        index--
      }
      const node = new ListNode(val)
      // 创建一个新节点
      
      node.next = prev.next
      // 遍历结束后，prev就是之前节点，而prev.next就是待插入节点
      // 让新节点指向当前节点
      
      prev.next = node
      // 之前的节点指向新节点形成链条
      
      // 同理简写 prev.next = new ListNode(val, prev.next)
      this.size++
    }
  }
}

这里比较麻烦，对于从头部添加以及其他位置添加需要分别的处理，因为链表头之前没有节点。而链表的编写有一个技巧就是在head指针之前，设置一个虚拟节点(也可以叫哨兵节点或哑节点)，让两种操作可以统一化，我们可以这样对add方法进行改造：

class LinkedList {
  ...
  add(val, index = 0) {
    const dummy = new ListNode(); // 设置一个虚拟节点
    dummy.next = this.head; // 让这个虚拟节点指向原来的头节点
    let prev = dummy; // 遍历就从虚拟节点开始
    while (index > 0) {
      prev = prev.next;
      index--;
    }
    prev.next = new ListNode(val, prev.next);
    this.size++;
    this.head = dummy.next // 虚拟头节点之后才是真实的节点，让head重新指向
  }
}

通过这样的改造，之前的addFirst方法也可以不需要，默认就是从头部添加节点。

删

如果需要删除某个节点，同理也需要找到删除节点之前的节点，让之前节点的指针指向下一个即可。这里还是引入虚拟节点，因为删除第一个节点时，之前没有节点的缘故。移除头节点时间复杂度还是O(1)，如果是移除中间节点复杂度为O(n)。

image

class LinkedList {
  ...
  remove(val) {
    const dummy = new ListNode()
    dummy.next = this.head
    let prev = dummy
    while(prev.next !== null) {
      if(prev.next.val === val) { // 找到了待移除的节点
        const delNode = prev.next // 先保存待移除的节点
        prev.next = delNode.next // 让之前的节点指向待移除之后的节点
        delNode.next = null // 让待移除节点的指针指向空，方便GC
        this.size--
        break;
      }
      prev = prev.next // 查找下一个
    }
  }
}

踩坑小技巧

以上都是比较简单的链表操作，如果对链表不太熟悉，但是又有比较复杂的链表操作时，指针指来指去，很容易把人搞晕，以下分享几个编写链表代码的小技巧：

1. 把head指针缓存起来

因为head指针始终指向的是链表的头部，而head指针又是JavaScript里的引用类型，所以当改变cur的引用时，head的内部也会同步改变，但head始终还是头指针。

let cur = this.head

cur = cur.next // head不会有任何变化
this.head = this.head.next // 改变了头指针的位置

cur.next = null // 同样head.next也会变为null
this.head.next === null // true

2. 使用虚拟节点指向头节点

这个也是上面代码使用过的技巧，这么做的原因是为了方便统一处理，然后也是不改变头指针的指向。一般这么使用：

const dummy = new ListNode()
dummy.next = this.head
let prev = dummy

... 处理逻辑

return dummy.next

3. 把赋值理解为指向

例如const a = b，我们一般的理解是将b赋值给a。但如果遇到链表代码，我们需要这么解读const a = b，让a指向b，也就是从右到左的看代码变为从左到右，这也是我个人方便理解时的习惯，对看懂链表很有帮助。

node.next = node.next.next 
// 将node指向它的下个节点的下个节点，
// 而不要解读成将node.next.next赋值给node.next

4.注意改变指针的先后顺序

例如之前插入节点的操作，首先需要让新节点指向待插入的节点，然后让之前的节点指向新节点。如果我们颠倒顺序：

image

颠倒顺序：
const node = new ListNode(val)
prev.next = node // 先让之前的节点指向新节点
node.next = prev.next // 然后让新节点指向待插入节点

因为这个时候prev.next已经指向了node，已经断开了和之后节点的链接，所以下一行的node.next指向的还是自己。这也说明写链表代码对逻辑性的要求，个人感觉看似简单的链表比二叉树还难理解些。

5.注意边界条件判断

当链表为空、只有一个节点、只有两个节点时，边界条件的判空要特别注意，经常遇到的问题就是指针为空的报错。

高仿一个数组

经过上面一系列的说明，大家应该对链表已经有了初步的理解，接下来我们用这个链表类来'高仿'一个数组，最后与数组进行比较，方便更加深刻的理解链表这种数据结构。

实现的API有：

• unshift：往链表的头部添加节点。
• pop：移除链表的尾节点。
• push：往节点的尾部添加节点。
• get: 返回指定下标的值，模仿arr[i]。
• set: 设置指定下标的值，传入下标与值，模仿arr[i] = x。
• forEach：遍历链表每一项。
• map：遍历链表每一项，返回新结果组成的链表。
• concat：拼接多个链表为一个链表。
• reverse：链表翻转。
• sort：排序链表。

我们知道从链表头添加/移除元素很简单，但是从尾部添加/移除就很麻烦了，需要从头开始遍历到尾部才行。所以这个链表会有些不同，我们增加指向链表尾的指针，这样的话用O(1)的时间复杂度就能访问到尾部。

链表行走江湖多年，靠的就是灵活。例如再将尾指针指向头，就行成了一个环，也就是循环链表；如果每个节点再加一个指向上一个节点的指针，那就成了双向链表。

class LinkedListArray { // 链表数组
  constructor() {
    this.dummy = new ListNode() // 虚拟头节点
    this.tail = null // 尾节点
    this.size = 0
  }
  
  ...
}

这里我们还可以继续分析，如果是从头节点添加，从尾节点移除，而删除节点又需要知道它之前的节点。所以我们这里换个思路，从尾节点添加元素，从头节点移除元素，这样的话它们的操作就全部是O(1)。

class LinkedListArray {
  ...
  
  get(index) { // 根据下标获取对应值
    if (index < 0 || index > this.size) {
      return;
    }
    let cur = this.dummy.next;
    while (index > 0) {
      cur = cur.next;
      index--;
    }
    return cur.val;
  }
  
  set(index, val) { // 设置制定下标节点的值
    if (index < 0 || index > this.size) {
      return;
    }
    let cur = this.dummy.next;
    while (index > 0) {
      cur = cur.next;
      index--;
    }
    cur.val = val;
  }
  
  unshift (val) { // 从头添加
    const node = new ListNode(val);
    if (this.tail === null) {
      this.dummy.next = this.tail = node; // 如果尾指针为空，那么头指针也是空的
    } else {
      this.tail.next = node; // 尾指针指向新节点
      this.tail = this.tail.next; // 新节点成为新的尾指针
    }
    this.size++;
  }
  
  pop () { // 删除尾部，从头指针处删除
    if (this.size === 0) {
      return;
    }
    const delNode = this.dummy.next; // 缓存需要删除的节点
    this.dummy.next = delNode.next; // 头节点的下个节点成为新的头节点
    delNode.next = null; // GC
    if (this.dummy.next === null) {
      // 如果头节点为空了，需要把链表至空
      this.tail = null; // 所以把尾指针指向空
    }
    this.size--;
    return delNode.val; // 删除移除节点的值
  }
  
  push(val) { // 从链表尾添加节点，从头节点开始添加
    this.dummy.next = new ListNode(val, this.dummy.next); // 更换新头节点即可
    if (this.tail === null) { // 如果是首次添加
      this.tail = this.dummy.next; // 将尾指针设置添加的第一个元素
    }
    this.size++;
  }
  
  forEach(fn) { // 遍历每一项，没有返回值
    if (this.size === 0 || typeof fn !== "function") {
      return;
    }
    let cur = this.dummy.next;
    let i = 0;
    while (cur != null) {
      fn(cur.val, i);
      i++;
      cur = cur.next;
    }
  }
  
  map(fn) { // 对每一项处理，返回新的链表
    if (this.size === 0 || typeof fn !== "function") {
      return;
    }
    let cur = this.dummy.next;
    const dummy = new ListNode(); // 新建一个链表
    let node = dummy;
    let i = 0;
    while (cur !== null) {
      const resNode = new ListNode(fn(cur.val, i)); // 将处理结果实例化为一个节点
      node = node.next = resNode; // 将新链表串起来
      cur = cur.next; // 遍历每一项
      i++;
    }
    this.dummy.next = dummy.next; // 改变头指针
    return this; // 为了新链表链式调用
  }

  concat(...lists) { // 将多个链表或节点从尾部链接起来
    if (lists.length === 0) {
      return this;
    }
    let last = this.dummy.next; // 从链表的尾部添加，也就是链表头
    for (const list of lists) {
      if (typeof list === "object") {
        if (list === null) { // 如果是null则跳过
          break;
        }
        let cur = list["dummy"] ? list.dummy.next : list; // 如果是使用的当前链表实例
        const stack = []; // 使用栈，因为是尾添加，新的链表顺序要颠倒后去添加节点
        while (cur !== null) {
          stack.push(cur);
          cur = cur.next;
          this.size++;
        }
        while (stack.length > 0) {
          const node = stack.pop(); // 从栈里弹出的就是逆序的链表节点
          node.next = last; // 往后添加
          last = node; // last向后移动
        }
      } else {
        const node = new ListNode(list); // 如果不是链表，只是一个值，创建节点实例
        node.next = last;
        last = node; // 更改需要添加节点last位置即可
        this.size++;
      }
    }
    this.dummy.next = last; // 重新链接头指针
    return this; // 链式调用
  }
  
  reverse() { // 翻转链表
    let head = this.dummy.next;
    let cur = null;
    let prev = head;
    this.tail = head; // 翻转后头就是尾，所以需要指向
    while (prev !== null) {
      const temp = prev.next; // 将前一个节点缓存起来
      prev.next = cur; // 往回指
      cur = prev; // cur前移
      prev = temp; // prev也前移
    }
    this.dummy.next = cur; // 链接新的链表
    return this;
  }
  
  sort(fn) { // 排序链表
    // 之后归并排序章节补全
  }
}

有了前面链表的基础，实现的一个数组并不会太难，这里难理解的一个API可能是链表的翻转，这里画图解释下。

image

链表数组 VS 数组

读取与设置

链表的模仿只能从头开始去遍历，也就是需要O(n)的时间复杂度，而数组只需要O(1)即可；设置同样如此，时间复杂度都是O(n)和O(1)的差距，数组爆锤链表。而这个特性也表明了二分查找只能适用于数组。

添加与移除

如果只是从头尾添加或移除，链表的时间复杂度都可以下降到O(1)(有尾指针的缘故，双向链表会更方便)；而数组如果从头部添加或移除元素，都会用O(n)复杂度去搬家。这也就造成了用链表或数组去实现栈复杂度性能一致，但如果是实现队列，那么链表的进出都会以O(1)的复杂度吊打数组。

链表队列与数组队列对比
const arrayQueue = [];
const linkedListQueue = new LinkedListArray();

console.time("arrayQueue");
for (let i = 0; i < 100000; i++) {
  arrayQueue.push(i); // 尾进
}
for (let i = 0; i < 100000; i++) {
  arrayQueue.shift(); // 头出
}
console.timeEnd("arrayQueue");

console.time("linkedListQueue");
for (let i = 0; i < 100000; i++) {
  linkedListQueue.unshift(i); // 头进
}
for (let i = 0; i < 100000; i++) {
  linkedListQueue.pop(); // 尾出
}
console.timeEnd("linkedListQueue");

image

遍历与排序

这个性能都是O(n)的，这没的说，如果逆序翻转，数组只需要首尾交换元素即可，而链表需要从头到尾整个翻转过来，数组的速度会是链表的两倍，当然它们依然都是O(n)。排序的话，它们都是O(nlogn)，这个之后章节介绍。

内存对比与消耗

数组需要使用整块的内存，而整块的内存又可以被CPU预读取，让访问速度更快，只是内存的使用会更加苛刻，而现代计算机针对这一苛刻条件也没多大影响；存储同样多的数据，链表整体的内存占用会更高，因为不仅仅有数据的占用，还有每个节点指针的消耗，只不过说内存不需要整块使用。

便利性

链表JavaScript还没有官方的数据结构提供，很多操作需要自己实现，无疑是麻烦很多；而数组官方的API一大箩筐，使用方便，如果数据量不大，完全使用数组也是没任何影响。

最后

线性数据结构两大巨头各有优缺点，知道并理解链表至少能扩宽我们处理程序的眼界。最后，对于链表翻转，你能写出递归的解法么？
完整源码，附带翻转递归写法 => 链表实现数组