我使用了很多列表和数组,但我还没有遇到一个场景,数组列表不能像链表一样容易使用,如果不是更容易的话。我希望有人能给我一些例子,说明什么时候链表明显更好。


当前回答

如果您需要在中间插入项,并且不想开始调整数组大小和移动内容,则列表的优势就会显现出来。

你是对的,通常情况下并非如此。我遇到过一些非常具体的案例,但不是很多。

其他回答

在现实中,内存局部性对实际处理的性能有很大的影响。

与随机访问相比,磁盘流在“大数据”处理中的使用越来越多,这表明围绕它构建应用程序可以在更大范围内显著提高性能。

如果存在按顺序访问数组的方法,则这是迄今为止性能最好的方法。如果性能很重要,那么至少应该考虑将此作为设计目标。

如果您需要在中间插入项,并且不想开始调整数组大小和移动内容,则列表的优势就会显现出来。

你是对的,通常情况下并非如此。我遇到过一些非常具体的案例,但不是很多。

这些是最常用的Collection实现。

数组列表:

插入/删除在结尾一般O(1)最坏情况O(n) 中间插入/删除O(n) 检索任意位置O(1)

LinkedList:

在任何位置O(1)插入/删除(注意你是否引用了元素) 中间检索O(n) 检索第一个或最后一个元素O(1)

向量:不要用。它是一个类似于ArrayList的旧实现,但所有方法都是同步的。对于多线程环境中的共享列表,这不是正确的方法。

HashMap

在O(1)中按键插入/删除/检索

TreeSet 插入/删除/包含O(log N)

HashSet 在O(1)中插入/删除/包含/大小

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

数组列表适用于写一次读多次或追加程序,但不适用于从前面或中间进行添加/删除。

到目前为止,数组是使用最广泛的数据结构。然而,链表以其独特的方式被证明是有用的,而数组是笨拙的——或者至少可以说是昂贵的。

链表在大小可变的情况下,对于实现堆栈和队列非常有用。链表中的每个节点都可以被推送或弹出,而不会影响大多数节点。在中间插入/删除节点也是如此。然而,在数组中,所有元素都必须移动,这在执行时间方面是一项昂贵的工作。

二叉树、二叉搜索树、哈希表和try是其中的一些数据结构——至少在C语言中——你需要链表作为构建它们的基本成分。

但是,在期望链表能够通过其索引调用任何任意元素的情况下,应该避免使用链表。