c - 数组和链表之间的内存使用

Question

在C语言中，链表和数组哪个在内存管理方面更有效率？

对于我的程序，我可以使用其中一个或两个。我想在开始之前考虑到这一点。

Answer 1

链表和数组都有好的一面和不好的一面。

数组

1. 访问特定位置需要 O(1) 时间，因为初始化的内存对于数组是连续的。因此，如果第一个位置的地址是 A，则如果 A+4，则第 5 个元素的地址。

2. 如果您想在某个位置插入一个数字，则需要 O(n) 的时间。因为您必须在该特定位置之后移动每个数字并增加数组的大小。

3. 关于搜索元素。考虑到数组已排序。您可以进行二进制搜索并访问每个位置是 O(1)。所以你按照二进制搜索的顺序进行搜索。如果数组未排序，则必须遍历整个数组，因此 O(n) 时间。

4. 删除与插入正好相反。您必须从删除它的地方开始左移所有数字。您可能还需要重新创建数组以提高内存效率。所以 O(n)

5. 内存必须是连续的，这在旧的 x86 机器上可能是个问题有 64k 段。

6. 释放是一个单一的操作。

链表

1. 访问特定位置需要 O(n) 时间，因为您必须遍历整个列表才能到达特定位置。

2. 如果您想在某个位置插入一个数字，并且您已经有一个指向该位置的指针，那么插入新值将花费 O(1) 的时间。

3. 关于搜索元素。无论数字如何排列，您都必须一个一个地从前到后遍历数字才能找到您的特定数字。所以它总是 O(n)

4. 删除与插入正好相反。如果您已经通过某个指针知道位置，假设列表是这样的。 p->q->r 你想删除 q 所有你需要的是将 p 的下一个设置为 r。没有别的。所以 O(1) [假定您知道指向 p 的指针]

5. 内存分散。如果采用简单的实现方式，缓存一致性可能会很差，而且总体占用率可能很高，因为内存分配系统对每个节点都有开销。然而仔细的编程可以绕过这个问题。

6. 删除需要对每个节点单独调用，但是再次仔细编程可以解决这个问题。

因此，根据您要解决的问题类型，您必须从两者中选择其一。