尽管对于两种数据结构都需要 O(n)，但链表如何比插入和删除操作的数组更快？

Question

数组中插入和删除操作的最坏情况运行时间是 O(n)，因为我们可能需要进行 n 次移位。

链表的情况也是如此，如果我们想插入或删除第 i 个元素，我们可能需要遍历整个列表才能到达预期执行插入/删除的位置。所以链表也需要 O(n) 时间。

那么为什么在完成插入/删除密集操作的情况下首选链表。

Answer 1

在这两种情况下搜索元素是相同的 ( O(n))。区别在于在指定位置插入和删除。在这种情况下，插入和删除是O(1)在链表中（因为您应该重置两个指针），但需要O(n)在数组中（因为您需要O(n)移位）。

另一个区别是从一个位置遍历到另一个位置。在列表中，这种遍历是需要的O(n)，但在数组中则是O(1)。

Answer 2

如果要插入/删除数组中的第 i 个元素，由于索引的原因，搜索只需要 O(1)。例如，您可以通过访问数组的第 i 个元素array[i]。然而，在最坏的情况下，插入/删除该元素将花费 O(n) 时间。例如，如果在位置 0 插入一个元素，则必须将所有元素向右移动一位，这需要遍历整个数组。

如果你想在链表中插入/删除第 i 个元素，在最坏的情况下搜索将花费 O(n)，因为你必须在一次遍历链表一个元素时保留计数和指针。一旦到达第 i 个节点，插入/删除只需要 O(1) 时间，因为它只是指针的重新排列，没有移位。

至于为什么在有很多插入/删除时首选链表，我想说的一个原因是，使用链表你不需要提前知道它有多大。而对于数组，可能需要经常调整其大小以适应更多/更少的元素。