使用链表描述复杂结构

halo 米娜过年好，俺是 132，首先大家过年好哇！大家知道我写过一个叫 fre 的框架，在 fre 中最主要的特点就是使用链表去描述 vdom 树，这是很少见的

今天给大家带来一篇文章，详细讲讲那些传统框架很少见到的，链表这个数据结构

链表替代数组

大家熟知的 3kb react like 框架 preact 最近在进行大重构，使用两阶段的 diff/patch 的新架构

它使用了一个叫做 commitQueue 的数组队列去装载 diff 的结果

另外，preact 还是一个经典的同步递归框架，当然像 vue 等框架也是一样

这就比较尴尬了，因为无论是递归还是数组，都会爆栈

解决爆栈的思路非常简单，就是使用链表和循环

let commitment = null

// 构建单向环状链表
for (let i = 0; i < children.length; i++){
  commitment.next = children[i]
  commitment = children[i]
}
commitment.next = children[0]

// 循环遍历链表
let current = commitment.next
while (current) {
  // do something
  current = current.next
}

短短几行代码，就可以将一个数组（栈，队列）转化为一个单向链表

一不需要递归，二不需要数组这种连续内存占用，解决了爆栈的问题，适合大量数据的遍历替代使用

其中在 fre 中就使用了同样的方式，解决了大量节点的内存问题

链表替代树

我们平时看到的前端框架，vue，preact，angular 都是使用 vdom 树或者 idom 树

树是一个非常常用的结构，构建容易，遍历也方便（递归）

同样的道理，当数据量大了以后，无论是内存还是时间，递归的弊端就会很明显，此时我们就需要使用链表了

// 构建链表树
// https://github.com/yisar/fre/blob/master/src/reconciler.ts#L176
for (var i = 0, prev = null; i  0) {
      prev.sibling = child
    } else {
      if (WIP.tag & OP.SVG) child.tag |= OP.SVG
      WIP.child = child
    }
    prev = child
  }

这段代码是 fre 中，将树的数组转化为链表的代码，非常简单

它将第一个孩子变成 child，之后的用 sibling 串联

这个结构相信读过 react 文章的很熟悉，实际上这还是一棵树，只是使用链表去描述了而已

这样的好处是，可以用经典的循环遍历了，除了上面的内存方面的好处，循环还是异步友好的，可以很方便得打断，继续……

// 遍历链表树
// https://github.com/facebook/react/issues/7942
let root = fiber
let node = fiber
while (true) {
  // Do something with node
  if (node.child) {
    node = node.child
    continue
  }
  if (node === root) return
  while (!node.sibling) {
    if (!node.return || node.return === root) return
    node = node.return
  }
  node = node.sibling
}

到这里，都是 fre 中对链表的使用，当然主要思路还是来自 react，但在这个满大街的同步框架的世界里，使用链表确实有它的好处，内存优势，异步友好等等

但这还没完呢？

使用双链表去描述 dom 树

大家有想过吗？如果 fiber 不是由框架 runtime 实现，而是浏览器内置，到底需要怎样的硬性条件呢？

很简单，那就是浏览器中复杂的树，比如 dom 树，同样使用链表去描述

写过 html parser 的人都知道，其实我们无论如何拿到的都是一串字符串，我们的遍历从左到右线性的

 132 
 
 [        #      #  [   ]   ]
Element > Node > Node > Element > End > End

所以它真是是一棵树吗？不从来都不是，它无论如何都是一串字符串而已

我们使用双向链表同样可以很方便地表述这串字符串的线性关系

const {ELEMENT, ATTRIBUTE, TEXT} = Node

const div = new Node(ELEMENT)

const id = new Node(ATTRIBUTE)
tag.next = id
id.prev = div

const text = new Node(TEXT)
id.next = text
text.prev = id

const br = new Node(ELEMENT)
text.next = br
br.prev = text

br.end = new Node(br.End)
div.end = new Node(div.End)

同样的，我们可以遍历这个链表，来做我们想做的事情

const childNodes = element => {
  const nodeList = []
  let { next, end } = element
  while (next !== end) {
    if (next.type !== Node.ATTRIBUTE) {
      nodeList.push(next)
      if (next.type === Node.ELEMENT)
        next = next.end
    }
    next = next.next
  }
  return nodeList
}

到这里，我们基本上是可以利用链表去描述 dom 树了，有了链表，我们在任何循环的地方都可以进行打断了……

其实无论如何，我们需要同步的地方只有两处，一是 js 行为，二是画图行为

不管是浏览器，还是我们自己实现渲染引擎，除了这两个行为之外的所有环节，比如排版，合成，统统都可以异步打断

过去 fre 实在框架 runtime 创造异步条件，那是因为我们没办法控制浏览器

我自己实现渲染引擎，我希望将这部分内容移交给引擎，相反 js runtime 越轻量越好

未来是物联网时代，没人乐意和浏览器玩♂耍了……

总结

其实说实话，我们使用链表而不是使用树，并不是看上了性能，至少我是对性能完全无感的，都什么年代了，还追求那点点时间

但是写树真的写腻了……尤其是渲染引擎这种复杂，大型的东西，数据结构一旦确定下来，就很难撼动了……

我希望从一开始就站在至高点，不要说什么先整个简单的，后续再重构……这是不现实的，越重要的东西越是从一开始就得确定好

最后大家过年好！年后一起搞事情鸭！