React前置技能之链表
前言
本来我是想好好研究一下 React 的渲染机制的，结果发现 React 的核心数据结构是链表，而了解了链表就很容易理解 React 的各种问题为什么会发生。
什么是链表
链表是一种数据结构，由一连串相连的数据节点构成，每一个节点都包含自身的数据和指向下一个节点的指针。
链表必须按顺序访问，因为只有上一个节点才知道当前节点的位置。
代码演示
直接描述有些抽象，我们可以来看看代码。
先定义节点类。
// 定义一个类叫做ListNode，作为链表节点，包含三个变量，data用来存数据，next用来存下一个节点的指针，prev用来存上一个节点的指针
export class ListNode<T> {
data: T
next: ListNode<T> | null = null
prev: ListNode<T> | null = null
constructor(data: T) {
this.data = data
}
}
再定义链表类。
import { ListNode } from './ListNode'
// 定义一个类叫做LinkedList，作为链表，包含三个变量，head用来存头部节点，tail用来存尾部节点，size用来存链表长度
export class LinkedList<T> {
private head: ListNode<T> | null = null
private tail: ListNode<T> | null = null
private size: number = 0
/**
* 在链表头部添加新节点
*/
prepend(data: T): void {
// 创建新节点
const newNode = new ListNode(data)
// 如果链表为空，新节点既是头节点也是尾节点
if (!this.head) {
this.head = this.tail = newNode
return
}
// 否则需要将新节点插入到头部
// 将新节点的next指向原头节点
newNode.next = this.head
// 将原头节点的prev指向新节点
this.head.prev = newNode
// 更新头节点指针
this.head = newNode
// 链表长度加1
this.size++
}
/**
* 在链表尾部添加新节点
*/
append(data: T): void {
// 创建新节点
const newNode = new ListNode(data)
// 如果链表为空，新节点既是头节点也是尾节点
if (!this.tail) {
this.head = this.tail = newNode
return
}
// 否则需要将新节点插入到尾部
// 将原尾节点的next指向新节点
this.tail.next = newNode
// 将新节点的prev指向原尾节点
newNode.prev = this.tail
// 更新尾节点指针
this.tail = newNode
// 链表长度加1
this.size++
}
/**
* 删除第一个匹配指定值的节点
*/
remove(data: T): boolean {
// 从头节点开始遍历
let current = this.head
// 遍历链表寻找要删除的节点
while (current) {
// 找到匹配的节点
if (current.data === data) {
if (current.prev) {
// 如果不是头节点，将上一个节点的next指向下一个节点
current.prev.next = current.next
} else {
// 如果是头节点，直接将头节点指向下一个节点
this.head = current.next
}
// 处理下一个节点的指针
if (current.next) {
// 如果不是尾节点，将下一个节点的prev指向上一个节点
current.next.prev = current.prev
} else {
// 如果是尾节点，直接将尾节点指向上一个节点
this.tail = current.prev
}
// 链表长度减1
this.size--
// 删除成功
return true
}
// 移动到下一个节点
current = current.next
}
// 未找到要删除的节点
return false
}
/**
* 获取链表当前长度
*/
getSize(): number {
return this.size
}
}
分析
从代码逻辑中我们可以看到，链表的插入和删除的逻辑，复杂度是非常低的。
链表插入和删除数据的复杂度是 O(1)，也就是不管数据有多少，逻辑操作只需要一次。
比如你的代码现在可以读取链表的第 114514 个节点，这时你想在这个节点后面添加一个新的节点，只要把 114514 节点的 next 赋值给新的节点的 next，然后再把新的节点赋值给 114514 节点的 next，最后给链表的 size+1 就行了。
这个操作就像是把一串首尾相接的圆环，在其中某两个圆环的位置，断开这两个圆环，再把新的圆环和这两个圆环首尾相接。
删除也是同理，只要读取到对应的元素，就能获取到上一个节点和下一个节点(需要双向链表)，就可以直接把上一个节点的 next 指向下一个节点，把下一个节点的 prev 指向下一个节点就行了。
这个操作就像是把一串首尾相接的圆环，在其中某个圆环的位置，断开这个圆环的两段，再把两段的圆环收尾两个圆环首尾相接。
所以链表只要可以获取到当前要插入和删除的节点，就能拿到前后元素的指针，从而拿到前后元素。从而只要一步就能完成操作，所以复杂度是 O(1)。
作为对比，数组的插入和删除的复杂度是 O(n)，因为数组插入或删除数据后，为了保证数据的连贯性，需要移动其他元素的位置，数据越多移动的次数越多，所以是 O(n)。
但是恰好相反的是，链表随机访问的复杂度是 O(n)，也就是随着数据达到 n 个，逻辑操作需要 n 次。
因为链表是不能跳跃访问的，当你想要读取到第 114514 个节点的数据的时候，你只能从头部节点正向查找或者尾部节点反向查找。
作为对比，数组的随机访问的复杂度则是 O(1)，因为数组会存储所有数据的索引，当你想要读取第 114514 个数据的时候，数据可以根据索引直接获取到对应的数据。
链表的适用场景
链表因为插入复杂删除复杂度低，并且天然具有连贯性，所以非常适合用来做任务调度，队列逻辑，以及一些链式结构的数据。
比如我想做一个连续调用接口的逻辑，我就可以把调用接口的时间放在链表的节点里，接口调用完成，就删掉对应的节点，还可以在运行过程中去添加或者删除还未调用接口的节点。
而如果用数组就会比较麻烦，你要把所有接口调用逻辑放进数组，然后在外面跑一个循环遍历数组，用来调用数组中的逻辑，而这时你想要取消某个未调用的接口就会非常麻烦了。你需要记录逻辑调用状态，知道自己逻辑走到哪一步了，然后再跳出循环，创建一个取消某个调用的新的数组，然后再去循环数组，然后跳过已经调用过的逻辑……
结语
总而言之，链表是一种也许会让你在某些时刻简化复杂逻辑的一种数据结构，在适当的时候使用就会有奇效。