A Guide to the Java LinkedList – Java关联列表指南

最后修改: 2016年 10月 19日

中文/混合/英文(键盘快捷键：t)

1. Introduction

1.绪论

LinkedList is a doubly-linked list implementation of the List and Deque interfaces. It implements all optional list operations and permits all elements (including null).

LinkedList 是 List 和 Deque 接口的双重链接列表实现。它实现了所有可选的列表操作，并允许所有元素（包括null）。

2. Features

2.特点

Below you can find the most important properties of the LinkedList:

下面你可以找到LinkedList的最重要的属性。

  • Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index
  • It is not synchronized
  • Its Iterator and ListIterator iterators are fail-fast (which means that after the iterator’s creation, if the list is modified, a ConcurrentModificationException will be thrown)
  • Every element is a node, which keeps a reference to the next and previous ones
  • It maintains insertion order

Although LinkedList is not synchronized, we can retrieve a synchronized version of it by calling the Collections.synchronizedList method, like:

虽然LinkedList不是同步的，但我们可以通过调用Collections.synchronizedList方法来检索它的同步版本，如。

List list = Collections.synchronizedList(new LinkedList(...));

3. Comparison to ArrayList

3.与ArrayList比较

Although both of them implement the List interface, they have different semantics – which will definitely affect the decision of which one to use.

尽管它们都实现了List接口，但它们有不同的语义–这肯定会影响到决定使用哪一个。

3.1. Structure

3.1.结构

An ArrayList is an index based data structure backed by an Array. It provides random access to its elements with a performance equal to O(1).

ArrayList是一个基于索引的数据结构，由Array支持。它提供对其元素的随机访问，性能相当于O(1)。

On the other hand, a LinkedList stores its data as a list of elements and every element is linked to its previous and next element. In this case, the search operation for an item has execution time equal to O(n).

另一方面，LinkedList将其数据存储为一个元素的列表，每个元素都与它的上一个和下一个元素相联系。在这种情况下，一个项目的搜索操作的执行时间等于O(n)。

3.2. Operations

3.2.操作

The insertion, addition and removal operations of an item are faster in a LinkedList because there is no need to resize an array or update the index when an element is added to some arbitrary position inside the collection, only references in surrounding elements will change.

在LinkedList中，项目的插入、添加和删除操作更快，因为当一个元素被添加到集合内部的某个任意位置时，不需要调整数组的大小或更新索引，只有周围元素的引用会发生变化。

3.3. Memory Usage

3.3.内存使用情况

A LinkedList consumes more memory than an ArrayList because of every node in a LinkedList stores two references, one for its previous element and one for its next element, whereas ArrayList holds only data and its index.

LinkedList比ArrayList消耗更多的内存，因为LinkedList中的每个节点都存储了两个引用，一个是前一个元素，一个是后一个元素，而ArrayList只保存数据及其索引。

4. Usage

4.使用情况

Here are some code samples that show how you can use LinkedList:

这里有一些代码样本，展示了你如何使用LinkedList。

4.1. Creation

4.1.创造 

LinkedList<Object> linkedList = new LinkedList<>();

4.2. Adding Element

4.2.添加元素

LinkedList implements List and Deque interface, besides standard add() and addAll() methods you can find addFirst() and addLast(), which adds an element in the beginning or the end, respectively.

LinkedList实现了List和Deque接口，除了标准的add()和addAll()方法，你可以找到addFirst()和addLast()，分别在开头或结尾添加一个元素。

4.3. Removing Element

4.3.移除元素

Similarly to element addition this list implementation offers removeFirst() and removeLast().

与元素添加类似，这个列表实现提供了removeFirst()和removeLast()。

Also, there is convenient method removeFirstOccurence() and removeLastOccurence() which returns boolean (true if collection contained specified element).

此外，还有一个方便的方法removeFirstOccurence()和removeLastOccurence()，它返回布尔值（如果集合包含指定的元素则为真）。

4.4. Queue Operations

4.4.队列操作

Deque interface provides queue-like behaviors (actually Deque extends Queue interface):

Deque接口提供类似队列的行为（实际上Deque扩展了Queue接口）。

linkedList.poll();
linkedList.pop();

Those methods retrieve the first element and remove it from the list.

这些方法检索出第一个元素，并将其从列表中删除。

The difference between poll() and pop() is that pop will throw NoSuchElementException() on empty list, whereas poll returns null. The APIs pollFirst() and pollLast() are also available.

poll()和pop()之间的区别是，pop将在空列表中抛出NoSuchElementException()，而poll返回null。还有API pollFirst() 和pollLast()。

Here’s for example how the push API works:

例如，下面是push API的工作方式。

linkedList.push(Object o);

Which inserts the element as the head of the collection.

将该元素作为集合的头部插入。

LinkedList has many other methods, most of which should be familiar to a user who already used Lists. Others that are provided by Deque might be a convenient alternative to “standard” methods.

LinkedList有许多其他方法，其中大部分对于已经使用过Lists的用户来说应该是熟悉的。其他由Deque提供的方法可能是 “标准 “方法的便利替代。

The full documentation can be found here.

完整的文档可以在这里找到。

5. Conclusion

5.总结

ArrayList is usually the default List implementation.

ArrayList通常是默认的List实现。

However, there are certain use cases where using LinkedList will be a better fit, such as preferences for constant insertion/deletion time (e.g., frequent insertions/deletions/updates), over constant access time and effective memory usage.

然而，在某些用例中，使用LinkedList将更适合，例如偏好恒定的插入/删除时间（例如，频繁的插入/删除/更新），而不是恒定的访问时间和有效的内存使用。

Code samples can be found over on GitHub.

代码样本可以在GitHub上找到over。