列表实现：与 ArrayList 和 TreeList 相比，LinkedList 的性能真的那么差吗？
以下相对性能统计数据表明了这一点 类：
获取添加插入迭代删除 树列表 3 5 1 2 1 数组列表 1 1 40 1 40 链表 5800 1 350 2 325
接着说：
LinkedList很少是一个好的实现选择。TreeList几乎总是它的一个很好的替代品，尽管它确实使用了稍多的内存。
我的问题是：
ArrayList 有什么用
add，插入和删除次粉碎链接列表？我们是否应该期望，对于 一、现实世界中的插入和移除案例 非常喜欢ArrayList？- 可敬的
LinkedList的棺材里吗？
我很想得出这样的结论：他们已经摊销或忽略了 ArrayList 的成长烦恼，并且没有考虑已经存在的 LinkedList 中的项目的插入和删除时间。已找到。
Taken from the Apache TreeList doc:
The following relative performance statistics are indicative of this
class:get add insert iterate remove TreeList 3 5 1 2 1 ArrayList 1 1 40 1 40 LinkedList 5800 1 350 2 325
It goes on to say:
LinkedListis rarely a good choice of implementation.TreeListis almost always a good replacement for it, although it does use sligtly more memory.
My questions are:
What is with the
ArrayListadd,insert, andremovetimes crushingLinkedList? Should we expect, for
one, that real-world insertion and removal cases
greatly favorArrayList?Does this
TreeListsimply put the nail in the coffin of the venerableLinkedList?
I am tempted to conclude they have amortized or ignored ArrayList's growing pains, and have not taken into consideration the insertion and removal times for an item in a LinkedList that has already been located.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
这里的关键是三个 List 实现中插入/删除操作的复杂性。 ArrayList 对于任意索引的插入/删除时间为 O(n) 次，但如果操作位于列表末尾，则为 O(1) 次。 ArrayList 还具有 O(1) 访问任意位置的便利性。 LinkedList 类似地为 O(n)，但在 List 任一端（开始和结束）的操作为 O(1)，对任意位置的访问为 O(n)。 TreeList 对于任何位置的所有操作都有 O(logn) 复杂度。
这清楚地表明，就在任意位置插入/删除而言，对于足够大的列表，TreeList 更快。但据我所知，TreeLists 是作为二叉搜索树实现的，并且与 ArrayLists 的类似操作相比，与其 O(logn) 操作相关的常量要大得多，ArrayLists 只是数组的包装器。这使得 TreeList 对于小列表来说实际上更慢。另外，如果您所做的只是将元素附加到列表中，则 ArrayList/LinkedList 的 O(1) 性能显然更快。此外，插入/删除的次数通常比访问的次数少得多，这往往会使 ArrayList 在许多情况下总体上更快。 LinkedList 在列表两端的恒定时间插入/删除使其能够更快地实现队列、堆栈和双端队列等数据结构。
归根结底，这完全取决于您到底需要一个列表来做什么。没有一种一刀切的解决方案。您必须选择最适合您工作的实施方式。
The key thing here is the complexity of insert/delete operations in the three List implementations. ArrayList has O(n) insert/delete times for arbitrary indices, but it is O(1) if the operation is at the end of the list. ArrayList also has the convenience of O(1) access for any location. LinkedList is similarly O(n), but is O(1) for operations at either end of the List (start and end) and O(n) access for arbitrary positions. TreeList has O(logn) complexity for all operations at any position.
This clearly shows that TreeList is faster for large enough Lists as far as insert/deletes in arbitrary positions are concerned. But AFAIK, TreeLists are implemented as a binary search tree, and has a much bigger constant associated with its O(logn) operations than similar operations with ArrayLists which are simply wrappers around an array. This makes TreeList actually slower for small Lists. Also, if all you are doing is appending element into a List, the O(1) performance of ArrayList/LinkedList is clearly faster. Moreover, often the number of insert/deletes are much fewer than the numbers of accesses, which tends to make ArrayList faster overall for many cases. LinkedList's constant time insert/delete at the either end of the List makes it much faster at implementing data structures like Queues, Stacks and Deques.
At the end of the day, it all depends on what exactly you need a List for. There isn't a one-size-fits-all solution. You have to select the implementation most suitable for your job.
这是由于这些集合背后的数据结构。 TreeList 是一个 树，它允许相对快速的读取、插入、删除（全部为 O(log n))。 ArrayList 使用 数组 来存储数据，因此当您插入或删除时，其中的每个项目数组必须向上或向下移动（最坏情况为 O(n)）。数组也有固定的大小，因此如果它溢出当前数组的容量，则必须创建一个新的、更大的数组（通常是上一个数组大小的两倍，以将调整大小保持在最低限度）。 LinkedList 使用...链接列表。链接列表通常具有对列表中第一个（有时是最后一个）元素的引用。然后列表中的每个元素都引用列表中的下一个元素（对于单链表）或下一个和前一个元素（对于双链表）。因此，要访问特定元素，您必须迭代它之前的每个元素才能到达该位置（最坏情况为 O(n)）。当插入或删除特定元素时，必须找到插入或删除它们的位置，这需要时间（最坏情况为 O(n)）。然而，简单地在开头或结尾添加另一个元素的成本非常低 (O(1))。
有很多关于数据结构以及何时使用它们的书籍，我建议阅读更基础的书籍。
It's due to the data structures behind these Collections. TreeList is a tree, which allows for relatively fast reads, insertions, removals (all O(log n)). The ArrayList uses an array to store the data, so when you insert or remove, every item in the array has to be shifted up or down (O(n) worst case). Arrays also have a fixed size, so if it overflows the current array's capacity, a new, larger one (usually double the size of the last one, to keep resizes to a minimum) must be created. LinkedList used... a linked list. A linked list usually has a reference to the first (and sometimes last) elements in the list. Then each element in the list has a refrence to either the next element in the list (for a singly-linked list) or the next and previous elements (for a double linked list). Because of this, to access a specific element, you must iterate through every element before it to get there (O(n) worst case). When inserting or removing specific elements, you must find the position to insert or remove them from, which takes time (O(n) worst case). However there is very little cost to simply adding another element to the beginning or end (O(1)).
There are whole books written on data structures and when to use them, I recommend reading up on the more fundamental ones.
因为链表必须逐个节点导航才能到达列表中的任何位置（根据实现保存前面，也可能保存后面），因此数字如此之高是有道理的。
对于大型 LinkedList 中的添加/插入/删除，您将需要从一个节点到另一个节点进行大量跳跃才能到达正确的位置。
如果他们制作了适当大小的ArrayList，那么开始成长的烦恼就不算什么了。如果 ArrayList 很小，那么成长的烦恼就不重要了。
对于 LinkedList，如果操作都靠近列表的前面，那么它的影响会比它们在末尾时小得多。
你应该做的是始终使用接口，例如：在声明变量和参数时列出列表，然后你可以更改“new LinkedList();”到“新的ArrayList（）；”并对代码进行分析以查看它在您的特定代码中的执行情况。
由于不必从一个节点跳到另一个节点的速度，我总是默认使用 ArrayList 而不是 LinkedList。
我相信树列表将比两者快得多（即使不看代码）。树被设计得速度很快。
Because a linked list has to navigate node by node to get anywhere in the list (save the front and probably the back depending on implementation) it makes sense that the numbers are so high.
For add/insert/remove in a large LinkedList you would have a lot of hopping from node to node to get to the correct spot.
If they made the ArrayList of the proper size to start with the growing pains will be nothing. If the ArrayList is small the growing pains don't matter.
For the LinkedList if the operations are all near the front of the list it would impact far less then if they are at the end.
What you should do is always use the interface, eg: List when declaring variables and parameters then you can change the "new LinkedList();" to "new ArrayList();" and profile the code to see how it performs in your specific code.
Because of the speed of not having to hop from node to node I always default to ArrayList instead of LinkedList.
I would believe the tree list is going to be significantly faster than both (even without looking at the code). Trees are designed to be fast.
这里每一个回答的人都是正确的。他们的想法都是正确的，这在很大程度上取决于您的使用模式，即没有一刀切的列表。但在我撰写本文时，他们都忘记提及（要么是我是个草率的读者）LinkedList 处于最佳状态时的一个用例：迭代器定位插入。这意味着，如果您不仅使用
which 似乎是他们用来获取统计信息的方法，而且
获取的迭代器
还使用通过or
，那么您一定会获得最佳的任意值有史以来的插入性能。当然，这意味着您可以限制对 iterator() 和 listIterator() 的调用次数，以及迭代器在列表中移动的次数（例如，您只能对列表进行一次顺序传递来完成所需的所有插入操作） ）。这使得它的用例数量非常有限，但尽管如此，它们仍然是非常频繁出现的用例。 LinkedList 在其中的表现是它（并且将来会）被保留在所有语言的所有容器集合中的原因，而不仅仅是 Java。
附言。当然，上述所有操作都适用于所有其他操作，例如 get()、remove() 等。即，通过迭代器精心设计的访问将使所有操作的复杂度为 O(1)，并且实际常数非常小。当然，对于所有其他列表也可以这样说，即迭代器访问将加快它们的速度（尽管略有提升）。但ArrayList的insert()和remove()不是——它们仍然是O(n)...而不是TreeList的insert()和remove()——树平衡开销不是你可以避免的...而TreeList可能有更多的内存开销......你明白我的想法了。总而言之，LinkedList 适用于列表上的小型高性能扫描操作。无论这是否是您需要的用例，只有您自己知道。
PSS。也就是说，我也因此留下来
Each and every one person who answered here is correct. They all are right in their notion, that it depends very heavily on your usage pattern, i.e there is no one-size-fits-all List. But at the moment of my writing they all forgot to mention (either that, or I am sloppy reader) a use-case when LinkedList is at the best: iterator-positioned insert. That means, that if you're doing not just
which seem to be the method they used to obtain the statistics, but
with an
iteratorobtained through eitheror
, then you're bound to get the best arbitrary insertion performance ever. That implies of course, that you're able to limit number of calls to iterator() and listIterator(), and number of iterator's movements through the list (e.g you can do only one sequential pass over the list to do all inserts you need). This makes its use-cases quite limited in their number, but nevertheless they are the ones that occur very very often. And LinkedList's performance in them is the reason why it is (and gonna be in the future) being kept in all container collections of all languages, not just Java.
PS. All of the above of course applies to all other operations, like get(), remove(), etc. I.e carefully designed access through iterator will make all of them O(1) with a very small actual constant. The same of course can be said for all other Lists, i.e iterator access will speed them all up (however slightly). But not ArrayList's insert() and remove() - they're still going to be O(n)... And not TreeList's insert() and remove() - tree balancing overhead is not something you can avoid... And TreeList probably has more memory overhead... You get my idea. To sum it all up, LinkedList is for small hi-perf scan-like operations over lists. Whether that is the use-case you need or not - only you can tell.
PSS. That said, I'm therefore also remain
对于 ArrayList，由于很少执行，因此基本上可以忽略该成本。如果这确实是一个问题，那么一开始就将数组变大。
如果我有一个小列表，那么使用 LinkedList 是有意义的，因为此时的好处很小。如果列表很长，那么显然 TreeList 更有意义。
如果我要对列表进行大量随机访问，那么 ArrayList 更有意义。
使用哪个容器实际上取决于您将用它做什么。没有一种容器是正确的，因为每种容器都有其优点和缺点，随着经验的积累，您开始了解何时使用哪种容器。
For the ArrayList, since it is done infrequently, you can basically have that cost be negligible. If it is actually a problem, then just make the array larger to start with.
If I have a small list then a LinkedList makes sense to use as there is minimal benefit at that point. If the list is going to be long then obviously a TreeList makes more sense.
If I am going to be doing a great deal of random access to a list then the ArrayList makes more sense.
Which container to use really depends on what you will be doing with it. There is no one correct container, as each has their strengths and weaknesses, and with experience you start to get an understanding of when to use which one.
请注意，ArrayList 通常比 LinkedList 更快，即使您的代码仅调用对于两者来说都是恒定时间的方法也是如此。例如，ArrayList.add() 只需复制单个变量并在不需要调整大小时递增计数器，而 LinkedList.add() 还必须创建一个节点并设置多个指针。此外，LinkedList 节点需要更多内存，这会减慢应用程序的速度，并且垃圾收集必须处理这些节点。
如果您需要从列表的任一端添加或删除元素，但不需要随机访问，则 ArrayDeque 比 LinkedList 更快，尽管它需要 Java 6。LinkedList
对于遍历列表然后在中间添加或删除元素是有意义的，但是这是一个不寻常的情况。
Note that ArrayList is generally faster than LinkedList, even when your code calls just the methods that are constant time for both. For example, ArrayList.add() simplies copies a single variable and increments a counter when no resizing is needed, while LinkedList.add() must also create a node and set multiple pointers. In addition, the LinkedList nodes require more memory, which slows down your application, and garbage collection must deal with the nodes.
If you need to add or remove elements from either end of the list, but don't require random access, an ArrayDeque is faster than than a LinkedList, though it requires Java 6.
A LinkedList make sense for iterating across the list and then adding or removing elements in the middle, but that's an unusual situation.