Java中LinkedList那点事
1.简介
LinkedList是 List和 Deque接口的双向链表实现。它实现所有可选的列表操作并允许所有元素（包括 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中项的插入，添加和删除操作更快，因为当元素被添加到集合内的某个任意位置时，不需要调整数组大小或更新索引，只有更改周围元素中的引用即可。
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 删除元素
与元素添加类似，此列表实现提供removeFirst() 和removeLast() 。
此外，还有方便的方法removeFirstOccurence() 和 removeLastOccurence() 返回boolean（如果collection包含指定的元素，则为true）。
4.4 队列操作
Deque接口提供类似队列的行为（实际上Deque扩展了Queue接口）：
linkedList.poll();
linkedList.pop();
这些方法检索第一个元素并将其从列表中删除。
方法poll() 和pop() 之间的区别是pop() 将抛出NoSuchElementException异常在空集合中，而poll()则返回null。API pollFirst() 和pollLast() 也可用。
以下是推送 API的工作原理：
linkedList.push(Object o);
其中将元素作为集合的头部插入。
LinkedList有许多其他方法，其中大多数方法对于已经使用过列表的用户应该很熟悉。Deque提供的其他方法可能是“标准”方法的便捷替代方案。
5.结论
ArrayList通常是默认的List实现。
但是，在某些使用情况下，使用LinkedList会更好地适应，例如在频繁插入/删除/更新操作时。
image
image
