ArrayList还是LinkedList更适合排序？

Question

我想使用需要经常排序的数据结构。该数据结构的大小很少超过1000个项目。

哪一个更好 - ArrayList 还是 LinkedList？

哪种排序算法更好使用？

- Sergey Gazaryan

---

我的假设是什么？当您测试您的假设时，您学到了什么？ - Mark Peters

在你考虑的规模下，两者都是一样的，我百分之百确定这不会成为你应用程序的瓶颈。始终要对自己进行性能分析，并查看您的数据，只有您才能做到这一点！ - user177800

堆不是最好的选择吗？ - Garrett Hall

注意：海报在下面的评论中指出，最大列表大小可能会在未来超过1000个项目。 - Andy Thomas

相关 - 何时使用LinkedList<>而不是ArrayList<>？ - Bernhard Barker

Answer 1

在Java 7及之前，使用Collections.sort将列表的内容转储到数组中没有任何区别。

在Java 8中，使用ArrayList会稍微更快，因为Collections.sort将调用List.sort，而ArrayList具有专门的版本，可以直接对支持数组进行排序，从而节省一次复制。

因此，ArrayList更好，因为它提供了类似或更好的性能，具体取决于Java的版本。

- assylias

Answer 2

如果你要使用java.util.Collections.sort(List)，那么这并不重要。无论如何，为了排序的目的，列表都将被转储到数组中。如果List没有实现RandomAccess，则该列表将被转储到一个List中。（感谢Ralph让我保持诚实。看起来我混淆了sort和shuffle的实现。它们非常相似，对吧？）

- corsiKa

---

这并不是Java文档或实现所说的（或者至少不是我理解的）：Java文档中写道，“此实现将指定的列表转储到数组中，对数组进行排序，并迭代列表以重置每个元素”-- 它是将列表转储到数组中（而不是List），而且无论它是否实现了RandomAccess接口都会这样做。 - Ralph

Answer 3

如果您可以使用Apache库，那么请查看TreeList。它能正确解决您的问题。

- Saurabh

---

或者只使用标准的TreeSet，不需要额外的依赖。 - Andy Thomas

TreeSet不支持使用索引访问元素。 - Saurabh

Answer 4

只有1000个项目？你为什么在意呢？

除非我有特殊需求，否则我通常都使用ArrayList。

看一下源代码。如果我没记错的话，排序是基于数组的。

- Puce

---

我关注这个因为它不是最终的尺寸。它可能会随着时间增加。 - Sergey Gazaryan

Answer 5

如果你只是进行排序而不是动态更新已排序的列表，那么两者都可以，而数组将更加节省内存。如果你想要维护一个有序列表，那么链表确实更好。在链表中快速插入对象到中间位置，但在数组中则较慢。

如果你想在中间位置找到一个对象，那么数组更好。使用数组，你可以进行二进制排序，并在O(logN)时间内查找成员是否在列表中。而在链表中，你需要遍历整个列表，这非常慢。

我猜取决于排序后你想要对列表做什么，哪种方法更好。

- Ron

---

在链表的中间插入一个对象速度很快，但是在数组中则很慢。然而，在链表中查找插入位置需要 O(n) 时间，而在 ArrayList 中则需要 O(log n) 的时间。复杂度相当。实际上，Java 中对链表进行排序（即 Collections.sort()）之所以能够接受的快，仅仅是因为它将整个链表转储到数组列表中进行排序，然后再将其转储回链表中。 - Mark Peters

复杂度相当，而对于大数据集，内存中的本地访问速度显着更快（我看到和测试的实验约为40％）。 - corsiKa