我在很大程度上了解链接列表的复杂性。在最坏的情况下访问一个项目是 O(n)，因为它可能在最后或不存在。将 O(1) 添加到未排序的链接列表中，因为您可以将其添加为头部。
但是对于数组，我很困惑。我已经阅读了很多关于访问效率如何（O（1））的内容，但添加不一定，删除也不一定。为什么是这样？
是因为加法并不总是在最后吗？那里会是O（1），对吧？但如果是在另一个点，你就必须移动项目，这将是 O(n)？这是在“幕后”发生的，可以用高级语言说，对吧？它正在移动内存位置，这就是复杂性开始的地方？
删除会导致我收集到间隙？它必须填写吗？
基本上，如果我有一个包含 10 个项目的数组，并且我要在第 5 个索引点添加一个项目，它是否必须将所有项目从索引 5 和更高的索引点复制到一个更高的索引点，从而导致操作是 O(n)？
任何澄清将不胜感激。
插入（例如，插入数组的中间）是O(n)因为，正如您所说，您需要将所有后续元素向右移动。因此，如果您在第一个位置插入，则必须将所有n现有元素移至上方以腾出空间，最坏情况下的成本为n. 平均而言，假设您在随机位置插入，您正在移动(n/2)元素。
附加（到数组的末尾）也是O(n)因为它需要重新分配。如果您的数组存在于一块已分配大于数组当前大小的内存中，这不是问题；您只需对内存中的下一个位置进行（恒定时间）写入。但最终你会用完房间。然后，您需要分配一块更大的新内存并将所有现有元素复制到其中。所以你最坏情况下的净成本是n+1（n副本，加上1附加），它给你你的O(n). （还有分配内存所产生的任何幕后成本。）为了避免这种成本，许多语言和库为您提供了在数组中预分配空间的选项，以覆盖您希望在其中看到的最大元素数量你的申请; 这确保不会有任何重新分配，除非您最终添加的元素数量超过预期数量。
删除是O(n)因为（如您所说）您需要将已删除元素之后的所有内容移回左侧一个空格。如果从第一个位置删除，则必须将所有n-1剩余的元素移过来，以O(n)应对最坏的情况。（如果你从最后一个位置删除，那只需要恒定的时间。）
通常，数组是具有固定长度的数据结构。这个特性有优点也有缺点。
与链表相比，数组的一个优点是，如果您知道它在数组中的位置，您可以在 Θ(1) 中访问数组中的任何项。根据数组中项目的内部顺序，搜索特定值可能非常有效，例如，当项目按排序顺序时，您只需要 Ο(log n ) 在与Ο( n ) 用于需要线性访问的链表。
数组的主要缺点是如果需要调整数组大小，则需要复制所有项目。因此，如果您不希望数组中有间隙，则任何插入和删除操作都需要 Θ( n )。