ArenaList 必须唯一

• 如果每个链表对应自己的 ArenaList，那么链表的 "拆分"、"合并" 等原本 O(1) 的操作，会有大量 nodes 在不同 Vec 上批量移动。复杂度变为 O(n)
• 所以多个链表共用同一个 ArenaList。Tree/Graph 等允许合并/拆分的数据结构也是如此。

维护 holes 的优缺点

• 优点：可以最大化利用内存，及时记录和使用孔洞。无需 compact
• 缺点：制造孔洞（del）、变更孔洞（make_node），都需要改变其上游节点对孔洞的指向。例如删除需要把上游的 next 设置为 None。这要求操作时知道父节点。
  • 这对于链表/二叉树是可能的，但是对于多叉树/图是不可能的

因此，对于 Graph 需要增加一个 compact 方法来清理孔洞。

• 算法流程如下
  1. 对 holes 降序排序
  2. 将 nodes.pop() 放入 nodes[holes.pop()]。也就是说，将最后一个有效节点放入第一个孔洞中。
  3. 调整 nexts，将原本指向孔洞的值改为 None。将原本指向被移动的节点的值改为移动后的位置。
  4. 回到步骤 2，直到 holes 为空。
• 整个 compact 的复杂度为 O(mn)。其中 m 为空洞数量，n 为 nodes 长度。相比之下，使用 holes 实时维护空洞的复杂度为 O(1)。
• 其他地方需要相应调整。
  • 删除操作只需要设置为 None，判断为空的语句也相应调整。
  • 在插入新节点时，不再寻找孔洞，而是将其插入到末尾。

使用 holes 维护空洞的优缺点

• 优点：添加节点和边的效率很高。删除节点的效率也不低（需要维护 holes）。
• 缺点：
  • 在执行 compact() 时，如果尾部是节点，需要删除 hole 的第一个元素，但 holes: Vec<usize> 对这样的操作复杂度为 O(n)
  • 每处理一个空洞，都需要遍历所有节点，因此复杂度为 O(mn)，其中 m 是空洞个数，n 是节点个数。
• 改进：引入一个 prev: Vec<usize> 来记录节点的上游。
  • 缺点：额外维护关于边的数据量翻倍。新增边的性能损耗也高一点（因为要更新 prev）。
  • 优点：compact() 处理单个空洞的效率是 O(1)，总效率为 O(m)。如果不维护 holes，总效率为 O(n)。

进一步的改进

• 如果在任意阶段都小心维护 next 和 prev，并且及时处理节点为 None 的情况，那么就不会出现空洞。
• 这样就不需要维护 holes，也不需要 compact 方法了。node: Vec<Option<Node<T>>> 可以改为 node: Vec<Node<T>>
• 移除过程中，使用 swap_remove() 达到 O(1) 性能，而不是 remove() 的 O(n) 性能。