ArrayList 还是 LinkedList 更适合排序？
我想使用需要时不时进行排序的数据结构。数据结构的大小不会超过 1000 项。
ArrayList 和 LinkedList 哪个更好？
使用哪种排序算法更好？
I want to use data structure that needs to be sorted every now and again. The size of the data structure will hardly exceed 1000 items.
Which one is better - ArrayList or LinkedList?
Which sorting algorithm is better to use?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
在 Java 7 之前，这没有什么区别，因为
Collections.sort会将列表的内容转储到数组中。在 Java 8 中，使用
ArrayList应该会稍微快一些，因为Collections.sort将调用List.sort和ArrayList有一个专门的版本，可以直接对后备数组进行排序，并保存副本。所以底线是 ArrayList 更好，因为它根据 Java 版本提供类似或更好的性能。
Up to Java 7, it made no difference because
Collections.sortwould dump the content of the list into an array.With Java 8, using an
ArrayListshould be slightly faster becauseCollections.sortwill callList.sortandArrayListhas a specialised version that sorts the backing array directly, saving a copy.So bottom line is
ArrayListis better as it gives a similar or better performance depending on the version of Java.如果您要使用 java.util.Collections.sort(List) 那么这并不重要。
如果列表将被转储到无论如何，出于排序目的的数组。List没有实现RandomAccess，那么它将被转储到List（感谢拉尔夫让我保持诚实。看来我混淆了排序和洗牌的实现。它们足够接近同一件事，对吧？）
If you're going to be using
java.util.Collections.sort(List)then it really doesn't matter.If theThe list will get dumped into an array for purposes of sorting anyway.Listdoes not implementRandomAccess, then it will be dumped to aList(Thanks for keeping me honest Ralph. Looks like I confused the implementations of sort and shuffle. They're close enough to the same thing right?)
只有1000件？你为什么关心？
除非我有特殊需要，否则我通常总是使用 ArrayList。
看一下源代码。如果我没记错的话，我认为排序无论如何都是基于数组的。
Only 1000 items? Why do you care?
I usually always use ArrayList unless I have specific need to do otherwise.
Have a look at the source code. I think sorting is based on arrays anyway, if I remember correctly.
如果您可以使用 Apache 库，请查看 树列表。它正确地解决了您的问题。
If you can use the Apache library, then have a look at TreeList. It addresses your problem correctly.
如果您只是排序而不是动态更新排序列表，那么两者都可以，并且数组将更加节省内存。如果你想维护一个排序列表，链接列表确实更好。在链表中间插入对象速度快，但在数组中插入对象速度慢。
如果你想在中间找到一个对象，数组会更好。使用数组，您可以进行二进制排序并在 O(logN) 时间内查找某个成员是否在列表中。使用链表，您需要遍历整个列表，这是非常慢的。
我想哪个更适合您的应用程序取决于您在排序后想要对列表执行什么操作。
If you are just sorting and not dynamically updating your sorted list, then either is fine and an array will be more memory efficient. Linked lists are really better if you want to maintain a sorted list. Inserting an object is fast into the middle of a linked list, but slow into an array.
Arrays are better if you want to find an object in the middle. With an array, you can do a binary sort and find if a member is in the list in O(logN) time. With a linked list, you need to walk the entire list which is very slow.
I guess which is better for your application depends on what you want to do with the list after it is sorted.