我认为主要的区别在于你是否经常需要从列表顶部插入或删除内容。

对于一个数组，如果你从列表的顶部移除一些东西复杂度是o(n)因为数组元素的所有下标都要移位。

对于链表，它是o(1)，因为您只需要创建节点，重新分配头，并将对next的引用分配为前一个头。

当经常在列表的末尾插入或删除时，数组是更可取的，因为复杂度将是o(1)，不需要重新索引，但对于链表，它将是o(n)，因为你需要从头到最后一个节点。

我认为在链表和数组中搜索都是o(log n)因为你可能会使用二分搜索。

嗯，我猜数组列表可以用在以下情况下:

您无法确定将会出现多少个元素 但是您需要通过索引随机访问所有元素

例如，您需要导入并访问联系人列表中的所有元素(您不知道其大小)

这完全取决于你在迭代时所做的操作类型，所有数据结构都在时间和内存之间进行权衡，我们应该根据需要选择正确的DS。有些情况下，LinkedList比数组快，反之亦然。考虑数据结构上的三个基本操作。

搜索

由于array是基于索引的数据结构，搜索array.get(index)将花费O(1)时间，而linkedlist不是索引DS，因此您将需要遍历到index，其中index <=n, n是链表的大小，因此array在随机访问元素时比链表更快。

那么，这背后有什么好处呢?

As Arrays are contiguous memory blocks, large chunks of them will be loaded into the cache upon first access this makes it comparatively quick to access remaining elements of the array,as much as we access the elements in array locality of reference also increases thus less catch misses, Cache locality refers to the operations being in the cache and thus execute much faster as compared to in memory,basically In array we maximize the chances of sequential element access being in the cache. While Linked lists aren't necessarily in contiguous blocks of memory, there's no guarantee that items which appear sequentially in the list are actually arranged near each-other in memory, this means fewer cache hits e.g. more cache misses because we need to read from memory for every access of linked list element which increases the time it takes to access them and degraded performance so if we are doing more random access operation aka searching , array will be fast as explained below.

插入

这是简单和快速的LinkedList的插入是O(1)操作在LinkedList (Java)阵列相比,考虑数组充满的情况下,我们需要将内容复制到新数组如果数组完全使一个元素插入ArrayList O (n)在坏的情况下,而ArrayList还需要更新其指数年底如果你插入一些除了数组,链表的我们不必调整它,你只需要更新指针。

删除

它的工作原理类似于插入，在LinkedList中比在array中更好。

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

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

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

数组具有O(1)随机访问，但是向数组中添加或删除内容的代价非常高。

链表在任何地方添加或删除项目和迭代都非常便宜，但随机访问是O(n)。

我认为主要的区别在于你是否经常需要从列表顶部插入或删除内容。

对于一个数组，如果你从列表的顶部移除一些东西复杂度是o(n)因为数组元素的所有下标都要移位。

对于链表，它是o(1)，因为您只需要创建节点，重新分配头，并将对next的引用分配为前一个头。

当经常在列表的末尾插入或删除时，数组是更可取的，因为复杂度将是o(1)，不需要重新索引，但对于链表，它将是o(n)，因为你需要从头到最后一个节点。

我认为在链表和数组中搜索都是o(log n)因为你可能会使用二分搜索。