更改内存地址的速度

Question

我想解释这个问题的最好方法是迭代一个链表与数组。

给定一个大小为n的数组和链表，它基于时间完全基于时间移动到不同的存储器地址，通过数组迭代的速度比遍历链表更快。由于数组是连续的内存块，并且链接列表包含指向内存中其他点的指针，数组是否会更快？如果内存足够大，速度会有明显差异吗？

感谢您的任何意见！

Answer 1

数组会更快。想想这样吧，对于一个链表，你需要找到的元素我你需要看看每个节点并找到指针移动到下一个元素。而对于一个数组，我们只需要在内存中移动（基于数据类型），而且大多数情况下，大多数CPU的移位操作是快速操作，比查看指针并移动到其位置更快。

而且更重要的是，对于一个数组的下一个元素可以并行地发现，我们并不需要知道什么I-1是发现元素我。但是对于链表，你需要知道最后一个元素来找到下一个元素。当你迭代一个数组时（如果你有一个好的缓存），它可以将下一个元素移到缓存中以加快访问速度。大多数情况下，迭代缓存可能会被存储和使用。对于链接列表，您无法预测下一个要放入缓存的项目，因为它可能是随机的。