list 双向链表

dummy节点(root Element)直接放到List结构中

ring

类似list,但没有dummy节点

  • 若r和s指向两个环:两个环链成一个,r => s => ... => s的最后节点s.Prev() => r.Next(),最终返回 r.Next()
  • 若r和s指向同一个环:删除r和s之间的节点,删除的节点构成子环,返回这个子环r.Next()

heap

0-indexed数组,down[i,u)返回false表示元素i没有向下筛

func Fix(h Interface, i int) {
  if !down(h, i, h.Len()) {
    up(h, i)
  }
}