c - 从数组和列表中删除项目的时间复杂度

Question

我在 iOS 上下载了算法应用程序，并且正在检查为数组编写的内容，因为我对编程和计算机科学还比较陌生。那里说

与列表相比，数组的另一个特点是在特定位置添加或删除数据的成本很高。

这是为什么？

Answer 1

嗯，这是真的！在数组中，如果您在最坏的情况下删除中间或第一个元素，则必须通过向下移动所有较高的元素（间隙右侧的元素）来缩小间隙，这在最坏的情况下可能导致 O(n ) 操作。在列表（双链接或单链接）中，我们只需弹出并重新连接节点！并且此操作需要 O(1) （仅重新连接，如果我们需要按值搜索元素，则在这两种情况下都会增加搜索时间）

Answer 2

这正是为什么数组对于可能被删除的项目集合来说是一个糟糕选择的原因：在计算机的内存中，它如下所示：

int a[1000];

for (int i=0;i<1000;i++){
  a[i] = i;
}

这是做什么的：

int a[1000];

您可能认为这只是告诉计算机您将使用一个大小为 1000 的数组，仅此而已，但还有更多：此时您的计算机保留了 1000 个可以存储所有这些条目的位置。这也是你需要注意不要在这里走得太远的一个原因：想象你把十亿甚至一万亿作为一个大小，你可能会炸毁你的计算机内存，只是使用那一条线。

保留所有这些位置后，您可以使用所需的值来占用它们，但是关于删除，有一个问题：正如@Hadeel 所提到的，您需要移动数组中的下一个条目以免出现漏洞在你的阵列中。最重要的是，仍然会有 1000 个（或更多）内存地址，为您的一个数组保留。
您可以通过重新分配数组来减少内存中的这种情况，但这很危险，而且您为什么要这样做？

但是，列表要容易得多：您只需声明它们，它们不会保留一大堆内存，您可以根据需要添加和删除，而无需整个移动过程。但是，访问n列表中的第 th 个条目需要您从第一个条目运行到n第 th 个条目才能找到它。

那么让我们来看看两者的速度：

                   array   linked list
access an entry     O(1)          O(n)
add an entry        O(1)          O(1)
delete an entry     O(n)          O(1)

祝你好运