我想知道与c中的连续数组相比，链表的优点和缺点是什么。因此，我阅读了一篇关于链表的维基百科文章。
https://en.wikipedia.org/wiki/Linked_list缺点根据这篇文章，缺点如下:
- 它们比数组占用更多的内存，因为它们的指针占用了更多的存储空间。
- 链表中的节点必须从一开始就按顺序读取，因为链表本身就是顺序访问。
当涉及到反向遍历时，链表中会出现困难。例如，单链表在向后导航时很麻烦，而双链表在某种程度上更容易读取，但在分配时浪费了内存。
节点是不连续存储的，这大大增加了访问列表中单个元素所需的时间，特别是在CPU缓存的情况下。
我明白前三点，但最后一点我很难理解:
节点是不连续存储的，这大大增加了访问列表中单个元素所需的时间，特别是在CPU缓存的情况下。
关于CPU Cache的文章没有提到任何关于非连续内存数组的内容。据我所知，CPU缓存只是缓存经常使用的地址，总缓存miss为10^-6。
因此，我不明白为什么CPU缓存在处理非连续内存数组时效率会降低。
CPU缓存实际上做两件事。
你提到的缓存最近使用的内存。
另一个是预测哪些内存将在不久的将来被使用。该算法通常非常简单——它假设程序处理大数组的数据，并且每当它访问一些内存时，它将在后面预取几个字节。
这对链表不起作用，因为节点是随机放置在内存中的。
此外，CPU加载更大的内存块(64,128字节)。同样，对于单读的int64数组，它有处理8或16个元素的数据。对于链表，它读取一个块，其余的可能被浪费，因为下一个节点可能在完全不同的内存块中。
最后但并非最不重要的是，与上一节相关-链表需要更多的内存来管理，最简单的版本将至少需要额外的sizeof(指针)字节用于指向下一个节点的指针。但这已经不再是CPU缓存的问题了。
这篇文章只是触及了表面，并且有些地方是错误的(或者至少是有问题的)，但总体结果通常是相同的:链表要慢得多。
需要注意的一点是，"节点是不连续存储的[原文如此]"是一个过于强烈的主张。的确，一般来说，例如malloc返回的节点可能分散在内存中，特别是在节点在不同时间或从不同线程分配时。然而，在实践中，许多节点经常同时分配在同一个线程上，并且这些节点通常在内存中是相当连续的，因为好的malloc实现是非常好的!此外，当关注性能时，您可能经常使用基于每个对象的特殊分配器，它从一个或多个连续的内存块中分配固定大小的注释，这将提供很好的空间局部性。
所以你可以假设，至少在某些情况下，链表会给你合理的良好的空间局部性。这在很大程度上取决于您是一次添加大多数列表元素(链表可以)，还是在较长一段时间内不断添加元素(链表的空间局部性很差)。
现在，在列表速度较慢的方面，链表被忽略的一个主要问题是，与数组变量相关的一些操作存在较大的常数因子。每个人都知道访问一个给定索引的元素在链表中是O(n)，在数组中是O(1)，所以如果你要通过索引进行大量访问，就不要使用链表。同样，每个人都知道，在链表中添加一个元素需要O(1)时间，在数组中添加一个元素需要O(n)时间，所以在这种情况下，前者获胜。
他们没有解决的是，即使是具有相同算法复杂度的操作，在实践中在一个实现中也可能慢得多…
让我们以遍历列表中的所有元素为例(可能是查找特定的值)。这是一个O(n)操作，无论您使用链接或数组表示。所以这是平局，对吗?
别那么快!实际的性能变化很大!下面是典型的find()实现在x86 gcc中以-O2优化级别编译时的样子，感谢godbolt使这变得容易。
C代码
int find_array(int val, int *array, unsigned int size) {
for (unsigned int i=0; i < size; i++) {
if (array[i] == val)
return i;
}
return -1;
}
汇编(仅限循环)1
.L6:
add rsi, 4
cmp DWORD PTR [rsi-4], edi
je .done
add eax, 1
cmp edx, eax
jne .notfound
C代码
struct Node {
struct Node *next;
int item;
};
Node * find_list(int val, Node *listptr) {
while (listptr) {
if (listptr->item == val)
return listptr;
listptr = listptr->next;
}
return 0;
}
汇编(仅限循环)
.L20:
cmp DWORD PTR [rax+8], edi
je .done
mov rax, QWORD PTR [rax]
test rax, rax
jne .notfound
看一下C代码，这两种方法看起来很有竞争力。数组方法将具有i的增量、一对比较和一次从数组中读取值的内存访问。链表版本将有一对(相邻的)内存访问来读取Node.val和Node.next成员，以及一对比较。
汇编似乎证实了这一点:链表版本有5条指令，而数组版本2有6条指令。所有的指令都是简单的指令，在现代硬件上每个周期的吞吐量为1或更多。
如果您测试它-，两个列表都完全驻留在L1中，您会发现数组版本每次迭代执行大约1.5个周期，而链表版本大约需要4个周期!这是因为链表版本受到它对listptr的循环依赖的限制。一行listptr = listptr->next可以归结为一条指令，但是这条指令每4个周期执行一次以上，因为每次执行都依赖于前一个的完成(在计算listptr->next->next之前，您需要完成listptr->next的读取)。尽管现代cpu每个周期可以执行2个加载周期，但这些加载需要4个周期才能完成，因此这里会出现串行瓶颈。
数组版本也有加载，但是地址不依赖于先前的加载:
add rsi, 4
cmp DWORD PTR [rsi-4], edi
它只依赖于rsi，它只是通过每次迭代添加4来计算。add在现代硬件上的延迟为一个周期，所以这不会造成瓶颈(除非低于1个周期/迭代)。因此，数组循环能够使用CPU的全部能力，并行执行许多指令。链接表版本不是。
这并不是"find"所特有的——任何需要迭代许多元素的链接操作都会有指针跟踪行为，这在现代硬件上固有地很慢。
1我省略了每个汇编函数的尾声和序言，因为它确实没有做任何有趣的事情。这两个版本都没有尾声，前言也都非常相似，从第一次迭代中剥离出来，进入循环的中间部分。完整的代码可在任何情况下查看。
2值得注意的是，gcc并没有像它在这里做的那样好，因为它将rsi作为指向数组的指针，并将eax作为索引i。这意味着两个单独的cmp指令和两个增量。更好的做法是在循环中只维护指针rsi，并将(array + 4*size)作为"未找到"条件进行比较。这样就减少了一个增量。此外，您可以通过让rsi从-4*size运行到零来消除一个cmp，并使用[rdi + rsi]索引数组，其中rdi为array + 4*size。这表明即使在今天，优化编译器也不能把所有事情都做好!
CPU缓存通常占用一定大小的页面，例如(常用的)4096字节4 kb或并从那里获取所需的信息。获取一个页面需要花费相当多的时间，比如1000个周期。如果我们有一个4096字节的连续数组，我们将从缓存中取出一个4096字节的页面，可能大部分数据都在那里。如果不是，我们可能需要获取另一个页面来获取其余的数据。
例子:我们从0-8191有2页，数组在2048和6244之间，然后我们将从0-4095获取页面#1以获取所需的元素，然后从4096-8191获取页面#2以获取我们想要的所有数组元素。这将导致从内存中取出2页到缓存中以获取数据。
列表中发生了什么?在列表中，数据是非连续的，这意味着元素在内存中不是连续的位置，所以它们可能分散在不同的页面中。这意味着CPU必须从内存中获取大量的页面到缓存中才能获得所需的数据。
例子:节点#1 mem_address = 1000，节点#2 mem_address = 5000，节点#3 mem_address = 18000如果CPU能够看到4k的页面大小，那么它必须从内存中获取3个不同的页面来找到它想要的数据。
同时，内存使用预取所以如果链表很小，比如A -> B -> C，那么第一个周期将会很慢，因为预取器无法预测下一个要取的块。但是，在下一个循环中，我们说预取器预热了，它可以开始预测链表的路径，并按时获取正确的块。
汇总数组很容易被硬件预测，并且在一个地方，所以它们很容易获取，而链表是不可预测的，并且分散在整个内存中，这使得预测器和CPU的寿命更加困难。
BeeOnRope的回答很好，并强调了遍历链表与遍历数组的循环计数开销，但正如他明确表示的那样，这是假设"两个列表都完全驻留在L1中"。然而，数组更有可能比链表更适合L1，并且当您开始使用缓存时，性能差异就会变得巨大。RAM可能比L1慢100倍以上，L2和L3(如果您的CPU有的话)慢3到14倍。
在64位架构中，每个指针占用8个字节，而双链表需要两个指针或16个字节的开销。如果每个条目只需要一个4字节的uint32，这意味着dlist需要的存储空间是数组的5倍。数组保证局部性，虽然malloc在局部性上可以做得很好，如果你按正确的顺序分配东西，你通常不能。让我们通过说它占用2倍的空间来近似糟糕的局部性，所以列表使用的"局部性空间"是数组的10倍。这足以使您从适合L1到溢出到L3，或者更糟的是从L2到RAM。