arrays - 何时在数组/数组列表上使用链表？

Question

我使用了很多列表和数组，但我还没有遇到过这样的场景:数组列表不能像链表那样容易使用，甚至比链表更容易使用。我希望有人能给我一些链接列表何时明显更好的例子。

Answer 1

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

1. 您需要从列表中进行恒定时间的插入/删除(例如在实时计算中，时间可预测性绝对至关重要)

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

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

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

在以下情况下最好使用数组:

1. 您需要对元素进行索引/随机访问

2. 您提前知道数组中元素的数量，以便为数组分配正确的内存量

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

   <

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

数组列表(如 .Net 中的数组列表)为您提供了数组的好处，但为您动态分配资源，这样您就无需过多担心列表大小，并且可以毫不费力地删除任何索引处的项目或重新调整元素。从性能角度来看，数组列表比原始数组慢。