linkedList特性本文介绍Java linkedList数据结构。它常用于实现stack、queue，graph，另外稀疏矩阵的存储，HashMap为了防止hash code冲突也用到。
linkedList 同时实现了List 和 Deque接口并实现了所有可用的方法，并支持元素为null 。
这里列举最常用的一些特性：
- 访问元素必须从头或尾开始遍历
- 不是同步的
- Iterator 和 ListIterator 迭代器是快速失败模式（即迭代器创建之后，如果list被修改了，则会抛出ConcurrentModificationException异常）
- 每个元素是一个节点，包括前面和后面节点的引用
- 维护插入顺序
虽然linkedList 不是同步的，我们可以利用 Collections.synchronizedList 实现同步版本:
List list = Collections.synchronizedList(new linkedList(...));对比ArrayList
虽然两者都实现了List接口，但语义不同，不同是应用场景不同。
-
内部结构
ArrayList底层基于数组按照索引访问的数据结构。提供元素随机访问方式，性能为O(1).
linkedList按照链表方式存储数据，每个元素于前后元素进行链接，这时搜索操作时间复杂度为 O(n).
-
操作性能
linkedList的插入、添加、删除操作比较快，因为不需要扩大数组或更新索引（当增加元素至特定位置），仅引用周边元素会改变.
-
内存使用
linkedList消费内存较ArrayList更多，因为其每个节点需要额外存储两个引用（前后节点的引用），ArrayList不需要存储该引用。
下面通过一些示例代码展示如何使用linkedList。
-
创建
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 更合适，如在频繁的插入、删除、更新操作时，我们需要这些操作时间为常量。
