1.LinkedList简介

LinkedList类图

LinkedList是用链表实现的List，是一个双向链表。
LinkedList和ArrayList都实现了List接口,实现了相关的增删改查等方法。
和ArrayList不同的地方是，LinkedList继承的是AbstractSequentialList,AbstractSequentialList继承AbstractList，而ArrayList直接继承AbstractList。
LinkedList还是实现了Deque接口，所以我们可以用LinkedList来作为双向队列。
LinkedList实现了Cloneable和Serializable，能够克隆和序列化。
LinkedList继承了Iterable，可以通过迭代器进行遍历。

2.LinkedList数据结构

LinkedList底层维护着一个Node组成的链表，在源码中，是如下图的一个静态内部类：

Node

3.LinkedList遍历方式

LinkedList可以通过for循环、for-each或者迭代器遍历。其中for-each底层也是转换成迭代器的方式进行遍历。我们测试一下for循环和迭代器遍历的效率：

遍历测试代码
测试结果：

测试结果
从测试结果可以发现，通过迭代器会比for循环快非常多。这是为什么呢？

get方法

找到对应Node
分析源码，LinkedList通过index获取元素，首先是index和size/2进行比较，然后确认从first还是last开始进行遍历。这个操作可以减少一半不必要的查询。但是，查询的时间复杂度还是O（n）。

迭代器遍历
而用迭代器访问的话，直接是next.next,相当于直接取当前节点的下一个节点，时间复杂为O（1），所以用迭代器比LinkedList快很多。

小结：通过上述测试和源码分析，我发现用迭代器遍历LinkedList比较好，而且使用迭代器的方式遍历集合框架有很多好处，例如，统一了对容器的访问方式，可以不用关心底层怎么实现的。

4.LinkedList和ArrayList区别

LinkedList底层是用链表的实现，增删速度快，增删操作时间复杂度O（1），但是要先遍历链表，找到对应元素，时间复杂度O（n）
ArrayList底层是用数组实现的，ArrayList查询元素速度快，根据index查询元素时间复杂度O（1）

5.问题：为什么向LinkedList中间插入元素性能比ArrayList要慢?

测试代码：

插入测试代码

测试结果：

测试结果
LinkedList是先判断从头还是末尾开始遍历，然后遍历到中间元素，在插入元素，ArrayList在中间插入操作是先用System.arraycopy（）进行数组移动，然后插入元素，我猜测，JVM对System.arraycopy()进行了优化，在数据量较大的时候，ArrayList用System.arraycopy（）所消耗的时间远远低于LinkedList遍历的时间。