书中自有黄金屋，书中自有颜如玉
————————————————————————————————————
本文在《码出高效：Java开发手册》书本讲解内容的基础上，将和大家一起对JDK1.8版本中的LinkedList源代码进行分析学习，同时和ArrayList的实现代码进行对比说明，争取做到知其然，也知其所以然。

好的，我们正式开始，先看图

继承实现关系如下

LinkedList 的本质是双向链表。与 ArrayList 相比 LinkedList 的插入和删除速度
更快，但是随机访问速度则很慢。测试表明，对于10万条的数据，与 ArrayList 相比，随机提取元素时存在数百倍的差距。除继承 AbstractList 抽象类外，LinkedList 还实现了另一个接口 Deque ，即 double-ended queue 。这个接口同时具有队列和栈的性质。
LinkedList 包含3个重要的成员 size 、first、 last，size 是双向链表中节点的个数。first last 分别指向第一个和最后一个节点的引用。 LinkedList 的优点在于可以将零散的内存单元通过附加引用的方式关联起来，形成按链路顺序查找的线性结构，内存利用率较高。

---

以上是书中的总结内容，下来我们直接看源码，首先还是看一下内部属性值

// 在看内部属性之前先稍微了解一下一个内部类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;}
}
--------------------------------------------------------------------
// size是节点个数，也可以理解为集合的长度
transient int size = 0;/*** Pointer to first node.* Invariant: (first == null && last == null) ||*            (first.prev == null && first.item != null)* 链表首元素first，上边官方的注释是将首元素的条件说明了一下* 比如要么链表没有元素，此时首尾元素都是null → (first == null && last == null)* 要么链表中有元素，此时首元素不能为null，并且其上一个元素为null → (first.prev == null && first.item != null)*/
transient Node<E> first;/*** Pointer to last node.* Invariant: (first == null && last == null) ||*            (last.next == null && last.item != null)* 链表尾元素last，注释就不再说明了，比较简单。*/
transient Node<E> last;

下来看一下构造方法

// 无参构造，直接啥也木有
public LinkedList() {}// 有参构造，入参为一个集合对象，然后调用内部addAll方法，在下边有列出
public LinkedList(Collection<? extends E> c) {this();addAll(c);
}
------------------------------------------------------------
// 将已有的节点个数和传入的集合统一再传给另一个同名方法
public boolean addAll(Collection<? extends E> c) {return addAll(size, c);
}// 此方法为最终进行元素插入的方法，具体内容不仔细看了，这里直接说明
// 牵扯到集合的传入，肯定之后会有循环，因为LinkedList是链表节点存储，所以
// 大部分时间是在对节点前后元素指向的修改，主要就是prev和next来回换
// 逻辑并不复杂，仔细看都能看懂，说起来比较费时间。。。
public boolean addAll(int index, Collection<? extends E> c) {checkPositionIndex(index);Object[] a = c.toArray();int numNew = a.length;if (numNew == 0)return false;Node<E> pred, succ;if (index == size) {succ = null;pred = last;} else {succ = node(index);pred = succ.prev;}for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;Node<E> newNode = new Node<>(pred, e, null);if (pred == null)first = newNode;elsepred.next = newNode;pred = newNode;}if (succ == null) {last = pred;} else {pred.next = succ;succ.prev = pred;}size += numNew;modCount++;return true;
}

下来我们说明解释一下大家都了解的内容，为什么说LinkedList的增删速度快而查询遍历速度慢，进行一个源码的分析和验证，首先我们看一下插入元素，因为插入元素方法是在是有很多，例如add(E e)，addFirst(E e)，add(int index, E element)，addAll(Collection<? extends E> c)和addAll(int index, Collection<? extends E> c)，这里我们就找两个方法看一下，大同小异

// add方法插入元素就是默认在最后插入，这里调用了内部分一个方法linkLast
public boolean add(E e) {linkLast(e);return true;
}// 这里我们都不用看代码，大概也能猜到，方法里会首先判断，当前是否有last节点，
// 也就是判断链表是否为空，为空就比较麻烦，插入的这个元素是链表的第一个元素
// 其既为首节点也是尾节点，如果原先有节点子链表中了，则直接修改原尾节点的next指针就可以了
// 所以这里最多涉及到两个元素的指向修改，速度比ArrayList移动元素快很多
private E unlinkLast(Node<E> l) {// assert l == last && l != null;final E element = l.item;final Node<E> prev = l.prev;l.item = null;l.prev = null; // help GClast = prev;if (prev == null)first = null;elseprev.next = null;size--;modCount++;return element;
}
----------------------------------------------------------------
// 在指定位置插入元素的方法
public void add(int index, E element) {// 首先还是一个下标越界的判断checkPositionIndex(index);if (index == size)// 如果你插入的位置是最后，那就和add()无参方法一样了，直接调用linkLastlinkLast(element);else// 如果你插入的位置不是最后，那就调用linkBefore方法// 这里node方法就是循环找到对应下标的node节点，在删除方法中我们再看源码linkBefore(element, node(index));
}// 这里其实和unlinkLast差不太多，就是插入位置改变了，还是需要判断插入位置是不是第一个节点之前，
// 是的话就作为首节点插入，不是的话就修改插入位置的前后节点对应的prev和next对象指向
// 需要注意是的一点，部分指向修正的代码在Node<>构造方法中做了，不要忽略掉
// 这东西很好理解，画个图立马就搞定，剩下就是看他们如何实现了，不要忽略细节就行。
void linkBefore(E e, Node<E> succ) {// assert succ != null;final Node<E> pred = succ.prev;final Node<E> newNode = new Node<>(pred, e, succ);succ.prev = newNode;if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;
}

从上边add方法来看，往LinkedList集合中加入元素，是非常快的，因为他最多涉及到左右两个相邻元素的指向修改，比起ArrayList的集合元素拷贝，是非常快的。
下来我们就来看一下删除方法，其实不同的节点位置删除速度也是不一样的，直接上代码：

// 首先是删除参数为对象的方法
public boolean remove(Object o) {if (o == null) {// 这里和ArrayList一样// 只会删除第一个出现的相等元素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方法unlink(x);return true;}}}return false;
}// 参数为删除节点的下标
// 内容也一想便知，就是修改删除节点相邻节点的前后指向，以及一些特殊时点的判断
// 比如没有前节点或后节点
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 {prev.next = next;x.prev = null;}if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;
}
---------------------------------------------------------------------
// 下来是删除参数为节点下标的方法
public E remove(int index) {// 首先是永恒的下标越界判断checkElementIndex(index);// 下来依旧是我们上边看到的unlink方法，不过这里多了一步，因为unlink方法的参数// 是节点，而我们的参数只有下标，此时调用了node(index)方法，可以猜到，// node方法就是一个循环，将对应下标的元素节点给我们返回回来，下边可以看一下return unlink(node(index));
}// 获取对应下标的循环方法
// 之所以说LinkedList的随机位置元素读取比ArrayList慢，原因就在这，获取时需要循环遍历整个链表
Node<E> node(int index) {// assert isElementIndex(index);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;}
}

以上便是我们LinkedList中插入和删除方法的冰山一角，我们也可了解到LinkedList插入和删除的迅速，以及查询随机节点的缓慢，其实LinkedList对于首尾节点位置的插入删除和查询都非常快，查询慢主要是针对链表中偏中后位置的元素。

---

这里LinkedList的源码我们大概就先看到这里吧，源码中还有很多方法没有看，但其实都是对节点指向的一些操作，我相信在看过上边的代码说明后，我们再去看LinkedList中其他方法的源码也就没多大问题了，归根结底都是对节点前后引用的变换，最后总结一下

LinkedList 是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，他还提供了 List 接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。

---

LinkedList的内容大概就到这里了，活到老学到老，我们下次再见。