Java LinkedList 教程_编程设计

本文介绍Java LinkedList数据结构。它常用于实现stack、queue，graph，另外稀疏矩阵的存储，HashMap为了防止hash code冲突也用到。

LinkedList 同时实现了List 和 Deque接口并实现了所有可用的方法，并支持元素为null 。

LinkedList特性

这里列举最常用的一些特性：

访问元素必须从头或尾开始遍历
不是同步的
Iterator 和 ListIterator 迭代器是快速失败模式（即迭代器创建之后，如果list被修改了，则会抛出ConcurrentModificationException异常）
每个元素是一个节点，包括前面和后面节点的引用
维护插入顺序

虽然LinkedList 不是同步的，我们可以利用 Collections.synchronizedList 实现同步版本:

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

虽然两者都实现了List接口，但语义不同，不同是应用场景不同。

内部结构

ArrayList底层基于数组按照索引访问的数据结构。提供元素随机访问方式，性能为O(1).

LinkedList按照链表方式存储数据，每个元素于前后元素进行链接，这时搜索操作时间复杂度为 O(n).
操作性能

LinkedList的插入、添加、删除操作比较快，因为不需要扩大数组或更新索引（当增加元素至特定位置），仅引用周边元素会改变.
内存使用

LinkedList消费内存较ArrayList更多，因为其每个节点需要额外存储两个引用（前后节点的引用），ArrayList不需要存储该引用。

下面通过一些示例代码展示如何使用LinkedList。

创建

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

增加元素

LinkedList 实现了List 和 Deque接口，除了标准的add 、addAll 方法，还有addFirst 、addLast分别在开头和结尾增加元素。
删除元素

与添加类似，list也提供了removeFirst() 和 removeLast() 。另外还提供好的 removeFirstOccurence() 和 removeLastOccurence() 方法，用于删除首次出现或最后出现元素，如果包括该元素则返回true。
队列操作

Deque接口提供队列方式行为,如出队和入队：

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

这些方法返回第一个元素并从列表中删除。两者的差异是，如果list为空pop方法会抛出NoSuchElementException异常，而poll返回null。 pollFirst() 和 pollLast() 也可用。这里示例push方法：

linkedList.push(Object o);

在list的开头插入元素。LinkedList 还有其他方法，大多数与list或与Deque的方法类似。

ArrayList是List的缺省实现，但有时LinkedList 更合适，如在频繁的插入、删除、更新操作时，我们需要这些操作时间为常量。

本文参考链接：https://blog.csdn.net/neweastsun/article/details/120508469