链表优于二叉树?

如果存储了链表的尾部,那么插入链表的速度肯定比插入二叉树的速度快。如果不平衡,在最坏情况下插入二叉树是O(N)(最好是O(logN))。如果它是平衡的,那么插入是O(log n),但是有一个内部维护参与保持平衡。如果保留尾部,则插入到链接列表中为O(1)。

还有,像比利约内尔 mentioned 二叉树通常是关联结构,而链表则不是。

与二叉树相比,从链接列表中删除项目更容易/更快,因为二叉树可能需要很少的操作来修复树。

链表通常不被用作关联容器(阅读:不被用作字典)--只被用作项目的文本列表,如数组。当需要如此简单的数据结构时,二叉树的性能较差。

在链接列表中,对象是由容器本身排序的,因此您不需要为对象使用比较函数。

一个公平的问题。我喜欢用最“紧”的容器来满足我的需要。例如,当您所需要的只是一个没有实际结果的队列时,您可以使用一个列表…但是…队列针对这个特定的任务进行了高度优化,即从前面弹出,在后面插入,不需要额外的指针或任何东西。通过使用最合适的类,您可以确保不会得到任何额外的绒毛,即使它有相同的大O。 做 物质。

这主要取决于场景。如果保持了链表的尾部,则在链表中插入速度很快。在链表中删除速度很快,但在搜索的情况下,最好是在树中删除(对于高度平衡树为O(对数(n)),而在链表中删除(n))。

我假设您在讨论实际的二进制搜索树,其中使用算法添加节点以最大限度地提高检索性能。与每个节点最多有2个子节点的简单树不同。

链表通常是未排序的,因此添加新节点只是一个O(1)操作,通常通过附加到列表的尾部。

另一方面,二叉树必须将节点存储在特定的排序机制中(并且可能强制平衡),以提供更有效的搜索/检索操作。

如果您的算法不需要非常有效地检索项目,同时也提供项目的有效排序,那么链接列表可能就是您所需要的。

队列和堆栈是可以使用链接列表愉快地实现的数据结构的示例。

注意:插入到链接列表的操作与基本的添加/附加操作不同(速度较慢)。插入通常需要沿着列表遍历,直到找到正确的位置,o(n)其中n是列表长度。附加只是添加到列表的尾部(因此o(1))。