Java LinkedList指南 - 记得看网

1.绪论

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

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

对列表进行索引的操作将从列表的开头或结尾开始，以离指定索引较近的为准。
它不是同步化的。
它的Iterator和ListIterator迭代器是fail-fast（这意味着在迭代器创建后，如果列表被修改，将抛出ConcurrentModificationException）。
每个元素都是一个节点，它保持着对下一个和上一个元素的引用。
它保持了插入的顺序

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

linkedList.push(Object o);

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

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

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

ArrayList 通常是默认的List的实现。

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

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