链表在二叉树上的优势？

Question

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

Answer 1

如果存储了链表的尾部,那么插入到链表中肯定比插入二叉树更快.如果不平衡,在最坏情况下插入二叉树是O(N)(最好是O(log N)).如果它是平衡的,那么插入是O(log N),但是有保持平衡的家务.如果保留尾部,则插入到链表中是O(1).

另外,正如BillyONeal所提到的,二叉树通常是一个关联结构,而链表则不是.