我对此非常不解。到处都写着“链表比数组快”，但没有人努力说出原因。使用简单的逻辑我无法理解链表如何更快。在数组中，所有单元格都彼此相邻，因此只要您知道每个单元格的大小，就可以轻松立即到达一个单元格。例如，如果有一个包含 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?
发布评论
评论（6）
这个问题的标题具有误导性。
它断言链表比更快，并且没有很好地限制范围。在很多时候，数组可以显着更快，而链表也有很多时候显着更快：链接的特殊情况列表“更快”似乎不受支持。
有两件事需要考虑：
就索引元素的访问而言：在数组中的操作是
O(1)，正如所指出的，非常快（只是一个偏移量）。 链表中的操作为O(k)（其中k是索引，并且可能始终为<< n，视情况而定）但是如果链表已经被遍历，那么每步的时间为O(1)，即“与数组相同”。数组遍历（for(i=0;i)）是否更快（或更慢）取决于特定的实现/语言/运行时。 但是，如果存在特定情况，其中数组对于上述任一操作（查找或遍历）都没有更快，那么更详细地剖析将会很有趣（我确信可以找到一种在列表上实现数组的非常简陋的语言 咳嗽 Haskell 咳嗽）
。
我的简单使用总结：数组很好 然而，对于涉及交换元素的索引访问和操作，非摊销调整大小操作和额外的松弛（如果需要）可能会相当昂贵，链接列表会摊销调整大小（并用松弛换取每个“指针”）。 -cell）并且通常擅长“删除或插入一堆元素”之类的操作，最终它们是不同的数据结构，应该这样对待。
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.
There are two things to consider:
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 isO(k)in a linked list (wherekis the index and may always be<< n, depending) but if the linked list is already being traversed then this isO(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)
Happy coding.
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.
与编程中的大多数问题一样，上下文就是一切。您需要考虑数据的预期访问模式，然后适当地设计存储系统。如果您插入某项内容一次，然后访问它 1,000,000 次，那么谁在乎插入成本是多少？另一方面，如果您插入/删除的次数与读取的次数一样多，那么这些成本就会决定您的决策。
Like most problems in programming, context is everything. You need to think about the expected access patterns of your data, and then design your storage system appropriately. If you insert something once, and then access it 1,000,000 times, then who cares what the insert cost is? On the other hand, if you insert/delete as often as you read, then those costs drive the decision.
取决于您所指的操作。在链表中添加或删除元素比在数组中快得多。
在链表和数组中逐个顺序迭代列表的速度或多或少相同。
在数组中获取中间的一个特定元素要快得多。
并且数组可能会浪费空间，因为在扩展数组时，通常会分配比当时需要的更多的元素（想想 Java 中的 ArrayList）。
因此，您需要根据您想要执行的操作来选择数据结构：
多次插入和顺序迭代 -->使用 LinkedList
随机访问和理想情况下预定义的大小 -->使用数组
Depends on which operation you are referring to. Adding or removing elements is a lot faster in a linked list than in an array.
Iterating sequentially over the list one by one is more or less the same speed in a linked list and an array.
Getting one specific element in the middle is a lot faster in an array.
And the array might waste space, because very often when expanding the array, more elements are allocated than needed at that point in time (think ArrayList in Java).
So you need to choose your data structure depending on what you want to do:
many insertions and iterating sequentially --> use a LinkedList
random access and ideally a predefined size --> use an array
在以下情况下，链接列表优于数组：
a) 您需要从列表中进行恒定时间插入/删除（例如在实时计算中，时间可预测性绝对至关重要）
b) 您不知道列表中有多少项目。对于数组，如果数组变得太大，您可能需要重新声明和复制内存
c) 您不需要随机访问任何元素
d) 您希望能够在列表中间插入项目（例如优先级队列）
在以下情况下更适合使用数组：
a) 您需要对元素进行索引/随机访问
b) 您提前知道数组中的元素数量，以便可以分配正确的内存量对于数组
c)，按顺序迭代所有元素时需要速度。您可以在数组上使用指针数学来访问每个元素，而您需要根据链表中每个元素的指针查找节点，这可能会导致页面错误，从而导致性能下降。
d) 记忆力是一个问题。填充数组比链表占用更少的内存。数组中的每个元素只是数据。每个链表节点都需要数据以及一个（或多个）指向链表中其他元素的指针。
数组列表（如 .Net 中的数组列表）为您提供了数组的优点，但为您动态分配资源，这样您就不必过多担心列表大小，并且可以删除任何索引处的项目，无需任何努力或重新创建。洗牌元素。从性能角度来看，数组列表比原始数组慢。
参考：
拉马尔的回答
https://stackoverflow.com/a/393578/6249148
Linked lists are preferable over arrays when:
a) you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)
b) you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big
c) you don't need random access to any elements
d) you want to be able to insert items in the middle of the list (such as a priority queue)
Arrays are preferable when:
a) you need indexed/random access to elements
b) you know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array
c) you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.
d) memory is a concern. Filled arrays take up less memory than linked lists. Each element in the array is just the data. Each linked list node requires the data as well as one (or more) pointers to the other elements in the linked list.
Array Lists (like those in .Net) give you the benefits of arrays, but dynamically allocate resources for you so that you don't need to worry too much about list size and you can delete items at any index without any effort or re-shuffling elements around. Performance-wise, arraylists are slower than raw arrays.
Reference:
Lamar answer
https://stackoverflow.com/a/393578/6249148
因为在数组中间插入时不会移动内存。
对于您提出的情况，它是正确的 - 数组更快，您只需要算术即可从一个元素转到另一个元素。链表需要间接寻址和片段内存。
关键是要知道使用什么结构以及何时使用。
Because no memory is moved when insertion is made in the middle of the array.
For the case you presented, its true - arrays are faster, you need arithmetic only to go from one element to another. Linked list require indirection and fragments memory.
The key is to know what structure to use and when.
LinkedList 是基于节点的，意味着数据随机放置在内存中，并通过节点（指向另一个对象，而不是彼此相邻的对象）链接在一起
数组是一组类似的对象存储在连续内存位置的数据对象
链表的优点是数据在内存中不必是连续的。当您添加/删除元素时，您只是将节点的指针更改为指向不同的节点，而不是实际移动元素。如果您不必在列表末尾添加元素，那么由于迭代的元素较少，访问数据会更快。然而，LinkedList 有多种变体，例如指向上一个和下一个节点的 DoublyLinkedList。
数组的优点是，如果你知道索引，你可以在 O(1) 时间内访问任何元素，但如果你不知道索引，那么你将不得不迭代数据。
数组的缺点是它的数据按顺序存储在内存中。如果要在索引 1 处插入元素，则必须将每个元素向右移动。此外，随着数组的增长，数组必须不断调整自身大小，基本上是复制自身，以便创建一个容量更大的新数组。如果你想删除乞求中的一个元素，那么你必须将所有元素移动到左侧。
当您知道索引时，数组是很好的，但随着它们的增长，数组的成本会很高。
人们之所以高度评价链表，是因为最有用、最高效的数据结构是基于节点的。
LinkedList is Node-based meaning that data is randomly placed in memory and is linked together by nodes (objects that point to another, rather than being next to one another)
Array is a set of similar data objects stored in sequential memory locations
The advantage of a linked list is that data doesn’t have to be sequential in memory. When you add/remove an element, you are simply changing the pointer of a node to point to a different node, not actually moving elements around. If you don’t have to add elements towards the end of the list, then accessing data is faster, due to iterating over less elements. However there are variations to the LinkedList such as a DoublyLinkedList which point to previous and next nodes.
The advantage of an array is that yes you can access any element O(1) time if you know the index, but if you don’t know the index, then you will have to iterate over the data.
The down side of an array is the fact that its data is stored sequentially in memory. If you want to insert an element at index 1, then you have to move every single element to the right. Also, the array has to keep resizing itself as it grows, basically copying itself in order to make a new array with a larger capacity. If you want to remove an element in the begging, then you will have to move all the elements to left.
Arrays are good when you know the index, but are costly as they grow.
The reason why people talk highly about linked lists is because the most useful and efficient data structures are node based.