何时在数组/列表上使用链表？
我使用了大量的列表和数组，但是我还没有碰到过一个场景，其中的数组列表不能像链表一样容易使用。 我希望有人能给我一些关于链表何时更好的例子。
在以下情况下链接列表优于数组：
a）您需要从列表中进行恒定时间的插入/删除操作（例如在时间可预测性非常关键的实时计算中）
b）你不知道列表中有多less物品。 对于数组，如果数组变得太大，则可能需要重新声明和复制内存
c）你不需要随机访问任何元素
d）您希望能够在列表中间插入项目（例如优先级队列）
数组最好是：
a）你需要索引/随机访问元素
b）提前知道数组中元素的数量，以便为数组分配正确数量的内存
c）当循环遍历所有元素时，您需要速度。 您可以使用数组上的指针math来访问每个元素，而您需要根据链接列表中每个元素的指针来查找节点，这可能会导致页面错误，从而导致性能问题。
d）记忆是一个问题。 填充数组占用比链表更less的内存。 数组中的每个元素就是数据。 每个链表节点都需要数据以及一个（或多个）指向链表中其他元素的指针。
数组列表（就像.Net中的数组列表一样）为您提供了数组的优点，但为您dynamic分配资源，使您无需过多担心列表大小，并且可以毫不费力地删除任何索引处的项目，洗牌周围的元素。 性能方面，数组列表比原始数组慢。
数组有O（1）随机访问，但是添加东西或删除东西真的很昂贵。
链接列表真的很便宜添加或删除任何地方的项目和迭代，但随机访问是O（n）。
为了增加其他答案，大多数数组列表实现在列表的末尾保留额外的容量，以便在O（1）时间内将新元素添加到列表的末尾。 当一个数组列表的容量被超过时，一个新的，更大的数组被内部分配，并且所有的旧元素被复制。 通常，新arrays的大小是旧的一倍。 这意味着平均来说 ，在数组列表的末尾添加新的元素是这些实现中的O（1）操作。 因此，即使您事先不知道元素的数量，只要您在结尾添加元素，数组列表可能仍然比添加元素的链接列表快。 显然，在数组列表中的任意位置插入新元素仍然是O（n）操作。
访问数组列表中的元素也比链表快，即使访问是连续的。 这是因为数组元素存储在连续的内存中，可以很容易地caching。 链接列表节点可能分散在许多不同的页面上。
如果您知道要在任意位置插入或删除项目，我build议只使用链接列表。 数组列表的速度几乎一切。
如果您需要在中间插入项目，并且不想开始调整数组大小和移动项目，则会显示列表的优点。
你是正确的，这通常不是这种情况。 我有过几个非常具体的例子，但不是太多。
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适用于一次写入或多次写入，但在前面或中间添加/删除不好。
嗯，Arraylist可以用在如下的情况下我猜：
- 你不确定有多less元素会出现
- 但您需要通过索引随机访问所有元素
例如，您需要导入并访问联系人列表中的所有元素（其大小未知）
使用链表sorting数组和多项式操作。
这些是Collection最常用的实现。
ArrayList的：
-
通常在最后插入/删除O（1）最坏情况O（n）
-
在中间插入/删除O（n）
-
检索任何位置O（1）
链表：
-
在任何位置插入/删除O（1）（注意如果你有一个元素的引用）
-
在中间检索O（n）
-
检索第一个或最后一个元素O（1）
vector：不要使用它。 这是一个类似于ArrayList的旧实现，但是所有的方法都是同步的。 对于multithreading环境中的共享列表，这不是正确的方法。
HashMap中
用O（1）中的键插入/删除/检索
TreeSet插入/删除/包含在O（log N）
（1）中的HashSet插入/删除/包含/大小
1）如上所述，与ArrayList（O（n））相比，InsertList和Remove操作在LinkedList中提供了良好的性能（O（1））。 因此，如果在应用程序中需要频繁添加和删除，则LinkedList是最佳select。
2）在Arraylist（O（1））中search（获取方法）操作是快速的，但是在LinkedList（O（n））中没有。因此，如果有更less的添加和删除操作以及更多的search操作需求，ArrayList将是最好的select。
我认为主要的区别是你是否经常需要插入或从列表顶部删除的东西。
对于一个数组，如果从列表顶部移除一些东西，复杂度是o（n），因为数组元素的所有索引都必须移位。
有一个链表，它是o（1），因为你只需要创build节点，重新分配头并把引用指定为next作为前一个头。
当经常在列表的末尾插入或移除数组时，因为复杂性是o（1），不需要重新索引，但是对于链接列表来说，数组将是o（n），因为您需要从头开始到最后一个节点。
我认为，在链接列表和数组中search将是o（log n），因为您可能会使用二进制search。
这一切都取决于你在迭代时正在做什么types的操作，所有的数据结构在时间和内存之间进行权衡，根据我们的需要，我们应该select正确的DS。 所以有些情况下LinkedList比数组快，反之亦然。 考虑数据结构的三个基本操作。
- search
由于数组是基于索引的数据结构searcharray.get（index）将花费O（1）time而linkedlist不是索引DS，因此您需要遍历索引，其中index <= n，n是链表的大小，所以当有元素的随机访问时，数组的链接列表会更快。
Q.So这背后的美丽是什么？
由于数组是连续的内存块，因此在第一次访问时会将大块数据块加载到caching中，这使得访问数组中其余元素的速度相对较快，就像访问数组中的元素一样，错过，caching局部性指的是在caching中的操作，因此与内存相比，执行速度要快得多，基本上在arrays中，我们最大限度地提高了caching中顺序元素访问的机会。 虽然链接列表不一定在连续的内存块中，但是不能保证在列表中顺序出现的项目实际上被布置在内存中的每一个附近，这意味着更less的caching命中，例如更多的caching未命中，因为我们需要从存储器读取对链表元素的每次访问都会增加访问它们所需的时间，并且降低了性能，所以如果我们正在进行更多的随机访问操作（search），数组将会像下面解释的那样快。
- 插入
在LinkedList中，这很容易和快速，因为与Array相比，在LinkedList（Java）中插入是O（1）操作，考虑数组已满时的情况，如果数组变满，我们需要将内容复制到新数组，元素放到O（n）的ArrayList中，而ArrayList在需要的时候也需要更新它的索引，除非在数组末尾，否则在链表中我们不需要调整它的大小，只需要更新指针。
- 删除
它像插入一样工作，在LinkedList中比数组更好。
我做了一些基准testing，发现列表类实际上比LinkedList更快，用于随机插入：
using System; using System.Collections.Generic; using System.Diagnostics; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { int count = 20000; Random rand = new Random(12345); Stopwatch watch = Stopwatch.StartNew(); LinkedList<int> ll = new LinkedList<int>(); ll.AddLast(0); for (int i = 1; i < count; i++) { ll.AddBefore(ll.Find(rand.Next(i)),i); } Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds); watch = Stopwatch.StartNew(); List<int> list = new List<int>(); list.Add(0); for (int i = 1; i < count; i++) { list.Insert(list.IndexOf(rand.Next(i)), i); } Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds); Console.ReadLine(); } } }
链表需要900毫秒，列表类需要100毫秒。
它创build后续整数列表。 每个新的整数被插入到已经在列表中的随机数字之后。 也许List类使用的不仅仅是一个数组。
