c - 用于频繁随机访问的数组或链表？

Question

我经常使用列表和数组，我想知道哪个更快，数组还是列表？

假设我们有整数数组和链表，两者都具有相同的值。

int array_data[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

typedef struct node_data{
    int data;
    struct node_data * next;
} list_data;

                  ____    ____    ____    ____    ____    ____    ____    ____    ____    ____
list_data *d = -> | 1| -> | 2| -> | 3| -> | 4| -> | 5| -> | 6| -> | 7| -> | 8| -> | 9| -> |10| -> NULL

如果我想获取索引 6 上的 array_data 的值，我将使用 array_data[6] 并获取 7 的值。但是如果我想要列表中的相同数据怎么办？我是否应该从头开始计算跳数，直到到达请求索引 get_data(d,6)？或者有更好的方法吗？

int get_data(list_data *l, int index){
    int i = 0;
    while(l != NULL){
        if(index == i){
            return l -> data;
        }
        i++;
        l = l -> next;
    }
    return 0;
}

如何使用指针数组来列出元素？如果我有超过 100,000 条记录甚至更多要保存，并且每条记录包含不止一种数据类型，这将是最好的解决方案。我将主要需要插入到最后，并且非常频繁地访问元素。

谢谢!

Answer 1

你每次都考虑这个问题是正确的；在决定是否实现数组、链表(或其他)结构时。

数组

• + 快速随机访问。
• + 动态分配的数组可以使用 `realloc()` 调整大小。
• + 使用 `qsort()` 排序。
• + 对于排序数组，可以使用 `bsearch()` 定位特定记录


• - 必须占用连续的内存块。
• - 对于长期存在的应用程序，数组的频繁扩大最终会导致内存空间碎片化，甚至可能最终导致 `realloc()` 失败。
• - 插入和删除元素是昂贵的。插入一个元素(在排序数组中)需要移动插入点之外的所有数组元素。删除元素时需要类似的元素移动。

链表

• + 不需要连续的内存块。
• + 动态调整大小比数组更有效。 在碎片化内存使用方面优于数组
• + 顺序访问很好，但可能仍然不如数组快(由于 CPU 缓存未命中等)。


• - 随机访问是不可能的。
• - 节点指针(priorNode、nextNode)的额外内存开销。

还有其他结构甚至将数组与链表结合在一起，例如哈希表、二叉树、n-树、随机访问列表等，每种结构都有不同的特性需要考虑。