何时在数组/数组列表中使用链表？

我使用了很多列表和数组,但我还没有遇到过这样一个场景,即如果不比链表更容易使用数组列表那么容易.我希望有人能给我一些关于链表明显更好的例子.

1> Lamar..：

---

在以下情况下,链接列表优于数组:

您需要从列表中进行恒定时间插入/删除(例如在时间可预测性非常关键的实时计算中)

你不知道列表中有多少项.对于数组,如果数组变得太大,您可能需要重新声明和复制内存

您不需要随机访问任何元素

您希望能够在列表中间插入项目(例如优先级队列)

在以下情况下,阵列最好:

您需要索引/随机访问元素

你知道提前数组中的元素数量,这样你就可以为数组分配正确的内存量

在按顺序迭代所有元素时需要速度.您可以在数组上使用指针数学来访问每个元素,而您需要根据链表中每个元素的指针查找节点,这可能会导致页面错误,从而导致性能下降.

记忆是一个问题.填充数组占用的内存少于链表.数组中的每个元素都只是数据.每个链表节点都需要数据以及指向链表中其他元素的一个(或多个)指针.

数组列表(如.Net中的那些)为您提供了数组的好处,但为您动态分配资源,这样您就不必过多担心列表大小,并且您可以在任何索引处删除项目而无需任何努力或重新洗牌元素.性能方面,arraylists比原始数组慢.

---

从什么时候LinkedList有O(1)插入/删除(当你说*常量时间插入/删除*时,我想你的意思是什么)？将东西插入LinkedList的中间总是O(n)

---

如果您恰好位于插入位置(通过迭代器),LinkedLists确实有O(1)插入.但并不总是如此.

---

良好的开端,但这遗漏了重要的事情:列表支持结构共享,数组更密集,具有更好的位置.

---

使用链接列表优先级队列是一个非常愚蠢的想法.动态阵列支持的堆允许O(lg n)分摊的插入和最坏情况的对数delete-min,并且是最快的实际优先级队列结构.

2> Dustin..：

---

数组具有O(1)随机访问权限,但是添加内容或从中删除内容非常昂贵.

链接列表在任何地方添加或删除项目以及迭代都非常便宜,但随机访问是O(n).

---

从数组末尾删除项目是连续的,就像从链接列表的***末端插入/删除项目一样.在中间...不是那么多.

---

拥有双重链接列表将导致您向前和向后搜索,除非您的LL已经订购了值...并且最糟糕的情况仍然是O(n)

3> 小智..：

---

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)

ArrayLists适用于一次性写入多次读取或appender,但在前面或中间添加/删除时效果不佳.

4> Jay Conrod..：

---

要添加到其他答案,大多数数组列表实现在列表的末尾保留额外的容量,以便可以在O(1)时间内将新元素添加到列表的末尾.当超出数组列表的容量时,将在内部分配一个更大的新数组,并复制所有旧元素.通常,新阵列的大小是旧阵列的两倍.这意味着平均而言,在数组列表的末尾添加新元素是这些实现中的O(1)操作.因此,即使您事先不知道元素的数量,只要您在末尾添加元素,数组列表仍然可能比添加元素的链接列表更快.显然,在数组列表中的任意位置插入新元素仍然是O(n)操作.

即使访问是连续的,访问数组列表中的元素也比链表更快.这是因为数组元素存储在连续的内存中,可以轻松缓存.链接列表节点可能分散在许多不同的页面上.

如果您知道要在任意位置插入或删除项目,我建议仅使用链接列表.几乎所有其他内容的数组列表都会更快.

5> Uri..：

---

如果您需要在中间插入项目并且不想开始调整数组大小并转移内容,则会显示列表的优点.

你是对的,通常情况并非如此.我有一些非常具体的案例,但不是太多.