为什么链表比数组快吗？ [英] Why are linked lists faster than arrays?
问题描述
我对此很不解。到处都有写着链表比数组更快，但没有人做努力说为什么。使用普通的逻辑我不明白链表是如何更快。数组中的所有细胞是彼此相邻，所以只要你知道对方很容易细胞的大小，瞬间达到一个单元格。例如，如果有10个整数的列表，我想在第四个单元格的值，然后我就直接去阵+ 24字节的开始，并从那里读8个字节。
I am very puzzled about this. Everywhere there is written "linked lists are faster than arrays" but no one makes the effort to say WHY. Using plain logic I can't understand how a linked list can be faster. In an array all cells are next to each other so as long as you know the size of each cell it's easy to reach one cell instantly. For example if there is a list of 10 integers and I want to get the value in the fourth cell then I just go directly to the start of the array+24 bytes and read 8 bytes from there.
在另一方面，当你有一个链表，你想要得到的元素在第四位，那么你必须从列表的开头或结尾开始（取决于如果它是一个单人或双人列表）和去从一个节点到另一个，直到你找到你要找的东西。
In the other hand when you have a linked list and you want to get the element in the fourth place then you have to start from the beginning or end of the list(depending on if it's a single or double list) and go from one node to the other until you find what you're looking for.
那么到底如何去一步一步比直接去到一个元素更快？
So how the heck can going step by step be faster than going directly to an element?
推荐答案
此问题的标题有误导之嫌。
This question title is misleading.
它声称，链表的是的比数组快而不限制范围的好。有许多次时数组可以是<青霉>显著的速度更快，有许多的时候，一个链表可以是<青霉>显著的速度：的的特定的链接的情况下清单速度更快似乎并不被支持。
It asserts that linked lists are faster than arrays without limiting the scope well. There are a number of times when arrays can be significantly faster and there are a number of times when a linked list can be significantly faster: the particular case of linked lists "being faster" does not appear to be supported.
有需要考虑两件事情：
- 链接列表与阵列的理论界限的在特定的操作的;和
- 现实世界的实现和使用模式，包括高速缓存局部性和分配。
至于索引元素的访问：在操作 O（1）在一个阵列并为所指出的，是非常快速（只是一个偏移量）。在操作 O（K）在链表（其中 K 是索引并可能永远是＆LT;＆LT; N ，视）的但的如果链表的已经被遍历的那么这为 O（1）每步这是相同的作为一个数组。如果一个数组的遍历的（为（i = 0; I＆LT; LEN，我++ ）快（或慢）取决于具体的实施/语言/运行时间。
As far as the access of an indexed element: The operation is O(1) in an array and as pointed out, is very fast (just an offset). The operation is O(k) in a linked list (where k is the index and may always be << n, depending) but if the linked list is already being traversed then this is O(1) per step which is "the same" as an array. If an array traversal (for(i=0;i<len;i++) is faster (or slower) depends upon particular implementation/language/run-time.
不过，如果有一个的具体的情况下数组是上述任何操作（寻求或遍历），这将是有趣的，看到的不是更快的进行更解剖细节的。 （我相信这是有可能找到一个语言具有非常退化实现了列表数组咳嗽的哈斯克尔的咳嗽的）
However, if there is a specific case where the array is not faster for either of the above operations (seek or traversal), it would be interesting to see to be dissected in more detail. (I am sure it is possible to find a language with a very degenerate implementation of arrays over lists cough Haskell cough)
快乐编码。
我的简单的用法总结：数组是良好的索引访问和涉及将元素的操作。非摊销重新大小操作和额外的松弛（如需要），但是，可能是相当昂贵的。链表摊销大小调整（及贸易为松弛每单元一个指针），并可以经常操作练成像削减了或插入一堆元素。最后，他们是不同的数据结构，并应受到同样的对待。
My simple usage summary: Arrays are good for indexed access and operations which involve swapping elements. The non-amortized re-size operation and extra slack (if required), however, may be rather costly. Linked lists amortize the re-sizing (and trade slack for a "pointer" per-cell) and can often excel at operations like "chopping out or inserting a bunch of elements". In the end they are different data-structures and should be treated as such.
这篇关于为什么链表比数组快吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
