Java Collection之LinkedList源码分析
上一篇Java Collection之ArrayList源码分析我们对ArrayList做了一个分析。我们知道了它内部是基于数组来实现的，也从源码分析出它的增、删都涉及到数组的copy，都会对数据位置进行移动，造成增、删缓慢的问题。那么LinkedList就会解决这一问题。
经常面试会问到这两者之间的优缺点和不同之处。我们大多数人可能也会答得出来，但是在一多问可能就露馅了。所以我们要深入了解，这样才能不被问住，平时开发中也更能灵活运用。
LinkedList内部结构是一个双向链表，对于链表我们知道每个元素有一个数据域和指针域，而指针域是指向下一个元素的地址。所以双向链表的意思就是把单链表的指针域进行扩充，让它也能指向前一个元素。
我们还是按以往的惯例，从我们平时的使用习惯开始分析。平时的使用当然是先调用构造方法，一般如下：
private LinkedList<String> linkedList=new LinkedList<>();
那么我们开始进入构造方法的源码：
/**
* Constructs an empty list.
*/
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
额。。。这有点尴尬了，两个构造方法，第一个空参，第二个还看不懂。好吧，不管了，我现在要用它，我们还是从增、删、改、查来找突破口吧。
增
首先我们看添加方法：
/**
* 将元素添加到list最后,就像addLast方法
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 在该列表中的指定位置插入指定元素。
* 移动当前位置（如果有的话）右边的后续元素（向索引添加一个元素）。
*/
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/**
*list最前插入
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
*list末尾插入
*/
public void addLast(E e) {
linkLast(e);
}
我们看第一个add方法，调用了linkLast(e);方法。
/**
* Links e as last element.将e链入最后的位置
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
这里我又看不懂了，这个Node是啥？到这里我们停下，先看看这个Node是什么鬼。
transient Node<E> first;//Pointer to first node.指向第一个节点的指针
transient Node<E> last;//Pointer to last node.指向最后一个节点的指针
private static class Node<E> {
E item;//当前节点的数据
Node<E> next;//下一个节点
Node<E> prev;//上一个节点
//构造方法充分体现了双向链表的特征
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
我们看到它是一个静态内部类，会先加载。同时结合我们LinkedList源码官方的介绍其实现方式是双向链表。我们知道这个Node就是一个节点。有关链表这里做一个简单介绍：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点（链表中每一个元素称为节点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
更多关于链表的知识，请自行百度。
现在我们就能很清晰的知道，Node在LinkedList里就是作为了链表的节点。里面包含了当前节点的值，也包含了前一个和后一个节点，这就实现了双向链表。现在我们回到linkLast(E e)方法
//尾节点，我们这里第一次调用 l=last=null;
final Node<E> l = last;
//新的节点，包含了上一个节点 l，当前节点e，和下一个节点null
final Node<E> newNode = new Node<>(l, e, null);
//把新的节点作为尾节点，也是把新的节点放在链表的尾部
last = newNode;
if (l == null)
//第一次时，新的节点也是首节点
first = newNode;
else
//如果已经有了很多元素 ，前一个元素已经作为了尾部元素，将新节点赋值给前一个元素的next。
//也就是前一个元素的下一个指向的是这个新节点
l.next = newNode;
//list存储数量依次+1
size++;
//与上一篇ArrayList中提到过的一样，这里我们不去关心
modCount++;
下面我们看看添加两个元素各阶段的，我们使用debug方式来直观的体验一下，当调用linkedList.add("new one");
第一次插值.jpg
当我们调用
linkedList.add("new two");插入第二个值：
第二次插值.jpg
我们可以直观的看到，当插入第一个值时，add方法会构建一个内部维护的Node，item是当前真正的存放的值，prev是指向了前一个为空的Node对象，next指向了下一个添加进来的值构建的Node对象，这个对象也为空。当第二次插值，当前list的最后一个元素就是第一次插入的值，这时候通过linkLast就能建立两个Node之间的关系。
接下来我们看看第二个插入的方法add(int index, E element)其中checkPositionIndex(index);是为了index在正常范围内。接下来如果要插入的位置刚好等于现在的元素个数index==size那么我们就调用linkLast方法将数据添加到末尾，因为这个方法会新建一个节点并作为尾节点。如果是要在中间插入数据，就调用linkBefore(element, node(index));方法。这里有一个新的方法node(index)我们先看它
Node<E> node(int index) {
// assert isElementIndex(index);
//size>>1可以理解为size/2
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
通过分析该方法，查找第index个节点，我们将列表一分为二，如果在前半段就从第一个开始依次查找下一个元素，如果是后半段就从最后依次查找前一个元素，直到满足条件为止。如果这样难以理解，我们笨的人就用笨的方法吧，举个实际的例子。因为现在我们的场景是在一个列表的中间某个位置插入值。我们看下面的图示，
node(int index).png
所以这个方法的作用就是通过index找到要插入的位置节点。然后我们再回过头去看linkBefore(E e, Node<E> succ)e是我们要插入的值，Node是我们找到的第index个节点，通过这个节点就能调整前后的指向关系。里面的操作和linkLast差不多，唯一不同的是，这里插入值是将值插入到index这个节点之前的。这一点其实通过方法名就能看出来。还有两个方法，
addFirst(E e) addLast(E e)分别是将元素插入列表头，和列表尾。其实现方法和add类似，这里就不在具体分析。
删
接下来我们在看删除方法，这里可能使用广泛的就这四个，其他方法的原理也是大同小异。
//该方法移除列表中第一次出现的该元素，如果元素不存在，将不会发生任何改变
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
//遍历每个元素
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
//如果元素的值相等，就执行断掉链接关系
unlink(x);
return true;
}
}
}
return false;
}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//删除第一个元素
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
//删除最后一个元素
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
我们先看第一个方法，先遍历每个元素，也就是节点，找到和该值相等的然后执行删除操作。
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
//前一个节点的next指向当前节点的next
prev.next = next;
//然后将当前节点的prev置空
x.prev = null;
}
if (next == null) {
last = prev;
} else {
//当前节点的下一个节点的prev，指向当前节点的prev
next.prev = prev;
//然后将当前节点的next 置空
x.next = null;
}
//将当前节点的值置空
x.item = null;
size--;
modCount++;
return element;
}
通过以上代码的分析，结合注释我们很容易理解remove(Object o)方法实际上就是将该节点Node的前一个节点和后一个节点建立链接关系，任何将该节点所有属性置空进行回收。这样就达到了删除的目的。
第二个根据remove(int index)方法，（这里要注意的是，其实这个index不是真正的位置信息，不想数组是一段连续的内存，这里只是它的添加顺序。）是先通过我们前面分析过的通过node()方法找到第index个节点，然后调用unLink进行删除。
第三个removeFirst第四个removeLast方法就更简单了，因为我们定义的全局变量first last就是我们需要删除的节点，这样就直接调整相应的prev和next然后置空就行了，这里不再过多解释。
改
改动的方法和ArrayList一样也只有一个，通过index查找到节点，然后对其值进行从新赋值即可。
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
查
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
很简单的通过index查找到节点，然后获取item就是我们要的值。
至于getFirst和getLast就更简单了，成员变量直接获取。
总结
到这里我们有关于LinkedList的分析就结束了。通过这样的学习，现在我们就能自己说出来他们各自的优缺点了，再也不用死记硬背了。我们来具体看看他们的优缺点，我们还是按照我们的流程来，从构造方法说起，再到数据的操作。
| 对比项目 | ArrayList | LinkedList |
|---|---|---|
| 实现方式 | 数组 | 双向链表 |
| 构造方法 | 初始化空数组 | --- |
| 增 | 始终在末尾，有index参数的涉及到数组的移动copy | 首尾方便，中间涉及大量折半遍历 |
| 删 | 会有大量数组copy | 首尾方便，中间涉及大量折半遍历 |
| 改 | 很方便只需通过下标从新赋值 | 首尾方便，中间涉及大量折半遍历 |
| 查 | 很方便只需通过下标获取 | 首尾方便，中间涉及大量折半遍历 |
