更改內存地址的速度

Question

我想解釋這個問題的最好方法是迭代一個鏈表與數組。

給定一個大小爲n的數組和鏈表，它基於時間完全基於時間移動到不同的存儲器地址，通過數組迭代的速度比遍歷鏈表更快。由於數組是連續的內存塊，並且鏈接列表包含指向內存中其他點的指針，數組是否會更快？如果內存足夠大，速度會有明顯差異嗎？

感謝您的任何意見！

Answer 1

數組會更快。想想這樣吧，對於一個鏈表，你需要找到的元素我你需要看看每個節點並找到指針移動到下一個元素。而對於一個數組，我們只需要在內存中移動（基於數據類型），而且大多數情況下，大多數CPU的移位操作是快速操作，比查看指針並移動到其位置更快。

而且更重要的是，對於一個數組的下一個元素可以並行地發現，我們並不需要知道什麼I-1是發現元素我。但是對於鏈表，你需要知道最後一個元素來找到下一個元素。當你迭代一個數組時（如果你有一個好的緩存），它可以將下一個元素移到緩存中以加快訪問速度。大多數情況下，迭代緩存可能會被存儲和使用。對於鏈接列表，您無法預測下一個要放入緩存的項目，因爲它可能是隨機的。