title: 链表操作

React 算法之链表操作

概念

来自 wiki 上的解释: 链表（Linked list）是一种常见的基础数据结构, 是一种线性表, 但是并不会按线性的顺序存储数据, 而是在每一个节点里存到下一个节点的指针(Pointer).由于不必须按顺序存储，链表在插入的时候可以达到 O(1)的复杂度, 但是查找一个节点或者访问特定编号的节点则需要 O(n)的时间.

单向链表: 每个节点包含两个域, 一个信息域和一个指针域. 这个指针指向列表中的下一个节点, 而最后一个节点则指向一个空值.
双向链表: 每个节点有两个连接, 一个指向前一个节点(第一个节点指向空值), 而另一个指向下一个节点(最后一个节点指向空值).
循环链表: 在单向链表的基础上, 首节点和末节点被连接在一起.

React 算法之链表操作 - 图1

基本使用

节点插入, 时间复杂度O(1)
节点查找, 时间复杂度O(n)
节点删除, 时间复杂度O(1)
反转链表, 时间复杂度O(n)

// 定义Node节点类型
function Node(name) {
  this.name = name;
  this.next = null;
}
// 链表
function LinkedList() {
  this.head = new Node('head');
  // 查找node节点的前一个节点
  this.findPrevious = function(node) {
    let currentNode = this.head;
    while (currentNode && currentNode.next !== node) {
      currentNode = currentNode.next;
    }
    return currentNode;
  };
  // 在node后插入新节点newElement
  this.insert = function(name, node) {
    const newNode = new Node(name);
    newNode.next = node.next;
    node.next = newNode;
  };
  // 删除节点
  this.remove = function(node) {
    const previousNode = this.findPrevious(node);
    if (previousNode) {
      previousNode.next = node.next;
    }
  };
  // 反转链表
  this.reverse = function() {
    let prev = null;
    let current = this.head;
    while (current) {
      const tempNode = current.next;
      // 重新设置next指针, 使其指向前一个节点
      current.next = prev;
      // 游标后移
      prev = current;
      current = tempNode;
    }
    // 重新设置head节点
    this.head = current;
  };
}

React 当中的使用场景

在 react 中, 链表的使用非常高频, 主要集中在fiber和hook对象的属性中.

fiber 对象

在react 高频对象中对fiber对象的属性做了说明, 这里列举出 4 个链表属性.

effect链表(链式队列): 存储有副作用的子节点, 构成该队列的元素是fiber对象
- fiber.nextEffect: 单向链表, 指向下一个有副作用的 fiber 节点.
- fiber.firstEffect: 指向副作用链表中的第一个 fiber 节点.
- fiber.lastEffect: 指向副作用链表中的最后一个 fiber 节点.
注意: 此处只表示出链表的结构示意图, 在fiber 树构造章节中会对上图的结构进行详细解读.
updateQueue链表(链式队列): 存储将要更新的状态, 构成该队列的元素是update对象
- fiber.updateQueue.pending: 存储state更新的队列(链式队列), class类型节点的state改动之后, 都会创建一个update对象添加到这个队列中. 由于此队列是一个环形队列, 为了方便添加新元素和快速拿到队首元素, 所以pending指针指向了队列中最后一个元素.
注意: 此处只表示出链表的结构示意图, 在状态组件(class 与 function)章节中会对上图的结构进行详细解读.

Hook 对象

在react 高频对象中对Hook对象的属性做了说明, Hook对象具备.next属性, 所以Hook对象本身就是链表中的一个节点.

此外hook.queue.pending也构成了一个链表, 将hook链表与hook.queue.pending链表同时表示在图中, 得到的结构如下:

React 算法之链表操作 - 图4

注意: 此处只表示出链表的结构示意图, 在hook 原理章节中会对上图的结构进行详细解读.

链表合并

在react中, 发起更新之后, 会通过链表合并的方式把等待(pending状态)更新的队列(updateQueue)合并到基础队列(class组件:fiber.updateQueue.firstBaseUpdate;function组件: hook.baseQueue), 最后通过遍历baseQueue筛选出优先级足够的update对象, 组合成最终的组件状态(state). 这个过程发生在reconciler阶段, 分别涉及到class组件和function组件.

具体场景:

class组件中

在class组件中调用setState, 会创建update对象并添加到fiber.updateQueue.shared.pending链式队列(源码地址).

export function enqueueUpdate<State>(fiber: Fiber, update: Update<State>) {
  const updateQueue = fiber.updateQueue;
  // ...
  const sharedQueue: SharedQueue<State> = (updateQueue: any).shared;
  // 将新的update对象添加到fiber.updateQueue.shared.pending链表上
  const pending = sharedQueue.pending;
  if (pending === null) {
    update.next = update;
  } else {
    update.next = pending.next;
    pending.next = update;
  }
  sharedQueue.pending = update;
}

由于fiber.updateQueue.shared.pending是一个环形链表, 所以fiber.updateQueue.shared.pending永远指向末尾元素(保证快速添加新元素)

React 算法之链表操作 - 图5

在fiber树构建阶段(或reconciler阶段), 会把fiber.updateQueue.shared.pending合并到fiber.updateQueue.firstBaseUpdate队列上(源码地址).

export function processUpdateQueue<State>(
  workInProgress: Fiber,
  props: any,
  instance: any,
  renderLanes: Lanes,
): void {
  // This is always non-null on a ClassComponent or HostRoot
  const queue: UpdateQueue<State> = (workInProgress.updateQueue: any);
  let firstBaseUpdate = queue.firstBaseUpdate;
  let lastBaseUpdate = queue.lastBaseUpdate;
  // Check if there are pending updates. If so, transfer them to the base queue.
  let pendingQueue = queue.shared.pending;
  if (pendingQueue !== null) {
    queue.shared.pending = null;
    // The pending queue is circular. Disconnect the pointer between first
    // and last so that it's non-circular.
    const lastPendingUpdate = pendingQueue;
    const firstPendingUpdate = lastPendingUpdate.next;
    lastPendingUpdate.next = null;
    // Append pending updates to base queue
    if (lastBaseUpdate === null) {
      firstBaseUpdate = firstPendingUpdate;
    } else {
      lastBaseUpdate.next = firstPendingUpdate;
    }
    lastBaseUpdate = lastPendingUpdate;
  }
}

React 算法之链表操作 - 图6

React 算法之链表操作 - 图7

function组件中
- 在function组件中使用Hook对象(useState), 并改变Hook对象的值(内部会调用dispatchAction), 此时也会创建update(hook)对象并添加到hook.queue.pending链式队列(源码地址).
- hook.queue.pending也是一个环形链表(与fiber.updateQueue.shared.pending的结构很相似)
```
function dispatchAction<S, A>(
  fiber: Fiber,
  queue: UpdateQueue<S, A>,
  action: A,
) {
  // ... 省略部分代码
  const pending = queue.pending;
  if (pending === null) {
    // This is the first update. Create a circular list.
    update.next = update;
  } else {
    update.next = pending.next;
    pending.next = update;
  }
  queue.pending = update;
}
```
- 在fiber树构建阶段(或reconciler阶段), 会将hook.queue.pending合并到hook.baseQueue队列上(源码地址).

    ```js
      function updateReducer<S, I, A>(
        reducer: (S, A) => S,
        initialArg: I,
        init?: I => S,
      ): [S, Dispatch<A>] {
        // ... 省略部分代码
        if (pendingQueue !== null) {
          if (baseQueue !== null) {
            // 在这里进行队列的合并
            const baseFirst = baseQueue.next;
            const pendingFirst = pendingQueue.next;
            baseQueue.next = pendingFirst;
            pendingQueue.next = baseFirst;
          }
          current.baseQueue = baseQueue = pendingQueue;
          queue.pending = null;
        }
      }
    ```
    ![](/uploads/projects/react-illustration-series/snapshots/linkedlist/hook.baseQueue-merge-before.png)
    ![](/uploads/projects/react-illustration-series/snapshots/linkedlist/hook.baseQueue-merge-after.png)

总结

本节主要介绍了链表的概念和它在react源码中的使用情况. react中主要的数据结构都和链表有关, 使用非常高频. 源码中链表合并, 环形链表拆解, 链表遍历的代码篇幅很多, 所以深入理解链表的使用, 对理解react原理大有益处.

参考资料

链表