用于频繁随机访问的数组或链表？
我经常使用列表和数组，我想知道什么是更快，数组或列表？
假设我们有整数数组和链表，两者都有相同的值。
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条记录甚至更多要保存的记录，这将是最好的解决方案，每条记录包含多个数据类型。 我最需要插入到最后，并经常访问元素。
谢谢！
你每次都要考虑这个问题是正确的; 在决定是否实现数组，链表（或其他）结构时。
ARRAY
- +快速随机访问。
- +可以使用`realloc（）`重新调整动态分配的数组。
- +使用`qsort（）`排序。
- +对于排序数组，可以使用`bsearch（）`定位特定记录
- – 必须占用连续的内存块。
- – 对于长期存在的应用程序，频繁扩大数组最终会导致碎片化的内存空间，甚至可能导致`realloc（）`的最终失败。
- – 插入和删除元素很昂贵。 插入元素（在排序数组中）需要移动插入点之外的所有数组元素。 删除元素时需要类似的元素移动。
链表
- +不需要连续的内存块。
- +比数组更有效地动态resize。 在碎片化内存使用方面表现优于数组
- +顺序访问很好，但可能仍然没有数组快（由于CPU缓存未命中等）。
- – 随机访问实际上是不可能的。
- – 节点指针的额外内存开销（priorNode，nextNode）。
还有其他结构甚至将数组与链表组合在一起，例如哈希表，二叉树，n树，随机访问列表等，每个结构都有各种要考虑的特性。
数组在访问时间不变; 即访问任何元素需要相同的时间。
对于列表而言并非如此：平均花费的时间与元素数量呈线性关系。
但是，与数组不同，列表不需要连续的内存块。 因此，附加到数组可能会导致内存重新分配，这可能会对您存储的数组元素的任何指针造成严重破坏。
在数组和列表之间进行选择时，这些要点是主要考虑因素。