什么时候会使用java.util.LinkedList？

Question

这是一个了解何时使用LinkedList的真实尝试；据我所知，由于java.util.LinkedList不支持随机访问，获取第n个元素的唯一方法是从1跳到(n-1)，或者使用get(n)，这本身就非常低效。那么为什么要使用LinkedList呢？除非您想要使用ListIterator从两侧迭代集合，否则ArrayList大部分情况下都可以胜任。

- sachinrahulsourav

---

获取第n个元素听起来确实像是随机访问。 - Steve Kuo

@Steve Kuo，LinkedList 不允许随机访问。你可以使用 get(n) 方法，但该方法的实现本身是从 1 跳过到 (n-1)。因此它不是随机访问。 - sachinrahulsourav

Answer 1

请思考以下这个方法：

List list = // choose your list here
list.add(0, new Object());

对于大型列表，LinkedList 的性能将远优于 ArrayList。同样的情况也适用于。

list.remove(0);

...还有许多其他方法。如需更多信息，建议阅读关于java.util.Deque接口的内容，该接口也由LinkedList实现。

- Lukas Eder

---

list.remove() 是从迭代器接口中继承而来的，这个操作在 ArrayList 中也具有相同的效率。至于 list.add()，我同意对于使用 LinkedList 的大型列表，在列表的某个位置添加元素是高效的。 - sachinrahulsourav

@sachinrahulsourav：查看remove(int)的源代码。 ArrayList执行对System.arraycopy的调用，而LinkedList仅更新一些引用...在接口中声明并不影响实现事实...除此之外，请注意remove(int)未在Iterator中声明，而是在List中声明... - Lukas Eder

没错。我刚意识到，remove()函数将需要进行复制并更新引用。 - sachinrahulsourav

如果您需要频繁地在列表的前面进行插入或删除操作，也许您需要使用ArrayDeque（或反转该列表）。 - Tom Hawtin - tackline

Answer 2

考虑这些数据结构上的三种常见操作：随机元素访问、添加元素和删除元素。

在LinkedList中，随机元素访问较慢（O(N)），但添加和删除较快（O(1)）。对于ArrayList，情况相反：随机元素访问很快（O(N)），但添加和删除元素较慢。

您需要考虑系统将执行哪些操作，并使用适当的数据结构。

- Oleksi

---

从哪里插入或删除元素？这可能是O(n)。 - Tom Hawtin - tackline

@TomHawtin-tackline 只有在包括查找该元素的列表节点时才需要。在某些情况下，您已经拥有它，或者可以在常数时间内获取它。在许多情况下，即使您有一个数组，您仍然必须进行搜索。 - user395760

Answer 3

LinkedList相对于ArrayList更适合在任意索引处进行插入/删除操作。当在ArrayList中插入或删除元素时，内部数组必须进行移位操作。而对于LinkedList来说，只需要简单地重新指向节点的指针即可。

- Steve Kuo

---

任意索引？对于两者都是O(n)。只有ArrayList通常会快一些。 - Tom Hawtin - tackline