data-structures - 链表相对于二叉树的优势？

Question

标题大多是不言自明的:链表相对于二叉树的优势是什么？我能想到的唯一一种链表更有效的情况是迭代每个元素，在这种情况下它仍然非常接近。看起来二叉树在访问数据和插入新元素方面都更快。那么为什么要使用链表呢？

Answer 1

如果存储了链表的尾部，那么插入链表肯定比插入二叉树快。如果不平衡，在最坏的情况下(最多为 O(log N))，插入二叉树是 O(N)。如果它是平衡的，那么插入是 O(log N)，但是为了保持平衡，需要进行内部维护。如果保留尾部，则插入链表是 O(1)。

此外，作为 BillyONeal mentioned ，二叉树通常是关联结构，而链表不是。