Java LinkedList指南

4次阅读

共计 1457 个字符，预计需要花费 4 分钟才能阅读完成。

1. 介绍
LinkedList 是一个双向链表, 实现了 List 和 Deque 接口。它实现所有可选的 list 操作，并且存储对象可以为 null。
2. 特点
LinkedList 具有以下特点：

查到列表中的元素，需要从头至尾的遍历列表
没有同步
它的 Iterator 和 ListIterator 迭代器是快速失败的（这意味着在迭代器创建之后，如果修改了列表，将抛出一个 ConcurrentModificationException)
每个元素都是一个节点，它保留对下一个和前一个节点的引用
维护了插入顺序

虽然 LinkedList 没有同步，但是我们可以通过调用 Collections.synchronizedList 方法创建它的同步版本，如：
List list = Collections.synchronizedList(new LinkedList(…));
3. 与 ArrayList 比较
虽然它们都实现了 List 接口，但它们具有不用的语义，这将影响我们使用哪一个。
3.1 结构体
ArrayList 是基于索引的数据结构，它提供了对其元素的随机访问，其性能为 O(1)。
LinkedList 将数据存储为元素列表，并且每个元素都链接到上一个和下一个元素。在这样情况下，其元素搜索的复发度为 O(n)。
3.2 操作
对 LinkedList 中的元素进行插入，删除操作更快，因为当元素添加到集合内的某个位置时，不需要调整数组的大小或更新索引，只需更改前后元素的 pre 和 next 指针即可。
3.3 内存的使用情况
LinkedList 的内存占用比 ArrayList 更多，因为在每一个接口都需要存储两个引用，一个用于记录前一个元素，一个用于记录后一个元素。而 ArrayList 中仅需要保持数据和它的索引。
4. 用法
以下是一些代码示例，展示了如何使用 LinkedList：
4.1 创建
LinkedList<Object> linkedList = new LinkedList<>();
4.2 添加元素
LinkedList 实现了 List 和 Deque 接口，除了标准的 add() 和 addAll()，还提供了 addFirst() 和 addLast()，它们分别在开头或结尾添加一个元素。
4.3 删除元素
与元素添加类似，LinkedList 还提供了 removeFirst() 和 removeLast()。
此外，还有方便的方法 removeFirstOccurence() 和 removeLastOccurence() 返回 boolean。如果 collection 中包含了指定的元素，则返回 true。
4.4 队列操作
Deque 接口提供类似队列的行为（实际上 Deque 扩展了 Queue 接口）：
linkedList.poll();
linkedList.pop();
这些方法检索第一个元素并将其从列表中删除。poll() 和 pop() 的区别是当列表为空时，pop 就会抛出 NoSuchElementException() 异常，而 poll 则会返回 null。
linkedList.push(Object o);
push 将在列表头添加一个元素。
LinkedList 还有许多其他操作，使用方式与 List 和 Deque 一样。
5. 结论
ArrayList 通常是默认的 List 实现。
但是，在某些使用情况下，使用 LinkedList 会是更好的选择。例如需要频繁的插入，删除，更新列表元素时。