[置顶] 【JDk源码解析之二】LinkedList源码解析

1.LinkedList的继承关系如图，和ArrayList一样都实现了List接口。但是ArrayList是基于动态数组的实现，LinkedList是基于链表的实现。

2.LinkedList是基于链表实现的，增加和删除容易，查找相对费时间。首先来看LinkedList的Node节点定义，如图所示。可以看到Node节点不仅有只向下一个节点的引用，还有只向前一个节点的引用，是双向的。所以LinkedList是双向链表。特别强调，不再是循环链表。

再来看LinkedList的构造方法，如下图所示。transient关键字，表示被修饰的属性不会被序列化。LinkedList有first和last属性，分别只向链表的第一个和最后一个元素。

3.具体源码分析

3.1  add方法

由于有first和last，所以可以在LinkedList的首尾增加节点，首先来看在末尾增加一个元素的方法，如下图所示。add（E e）和addLast(E e)是一样的，都是最终调用linkLast（E e）方法，实现在LinkedList的尾部增加元素。

那么在首部增加元素是怎样的呢，如图所示。

最重要的是，它支持在指定的index增加元素。在查找index的元素的时候，用了一个简单的优化操作，就是看这个index距离first近还是last近，然后在按照相应的方法去查。

3.2 remove方法

remove方法和add方法类似，都是能在收尾进行删除，直接看源码，没有什么特别的。

3.3 addAll()方法

按照index插入元素的时候，需要调用node(index),以此获得index位置的元素，所以这种结构不适合随机访问和查找。

3.4 get方法

每次按照index获取元素的时候，都要记得check 索引是否已经越界。

3.5 set方法

对于链表的操作，无非增删改查，下面看看改是怎么实现的。改也就是set方法

4. 总结

LinkedList 是基于链表实现的list，是一个双向链表。有的博客说是双向循环链表，这其实现在是不对的。在Jdk7里面，已经不再是循环链表了，所以不要看着别人说双向循环，就说双向循环，我的代码分析都是基于jdk7，jdk8的没看。