Hello大家好，本章我们简单了解一下LinkedList 。有问题可以联系我mr_beany@163.com。另求各路大神指点，感谢。
说明：本篇文章基于jdk1.8进行阅读，并针对LinkedList中常用的一些方法进行简要说明。
一：LinkedList简介
LinkedList是一种链表类型的数据结构，支持高效的插入和删除操作。其实现了 Deque 接口，使得 LinkedList具有队列的特性。LinkedList 类的底层实现的数据结构是一个双端的链表。
二：数据结构图分析
如图可以看出LinkedList数据结构使用双向链表结构，有一个头节点和一个尾节点，第一个节点的前驱节点为null，最后一个节点的后继节点为null。其中每个节点有两个指针指向前驱节点和后继节点，这意味着我们在添加或修改LinkedList时不必像ArrayList一样进行扩容操作。
三：继承关系分析
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable- 继承于 AbstractSequentialList。而AbstractSequentialList这个类提供了一个基本的 List 接口实现，为实现序列访问的数据储存结构的提供了所需要的最小化的接口实现。他采用的是在迭代器的基础上实现的 get、set、add 和 remove 方法。
- 实现List接口，说明可以对他进行队列的操作
- 实现Deque接口，可以将 LinkedList 当作双端队列使用
- 实现Cloneable接口，说明可以进行克隆
- 实现Serializable接口，说明可以被序列化
四：源码分析
1：成员变量
//transient修饰的变量在序列化时不会被序列化
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == 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)
*/
transient Node<E> last;LinkedList的成员变量很简单，只有三个。其中size表示链表中实际元素的数量。
根据注释结合上面的数据结构图可以看出：
- 当链表为空时，first和last一定都为空。
- 当链表不为空时，first的前驱结点一定为空，first.item一定不为空。last的后续节点一定为空，last.item一定不为空。
2：内部类
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;
}
}3：构造方法
//构建一个空列表
public LinkedList() {
}
/**
* 构建一个包含集合c的列表
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}4：常用方法
- 添加元素到第一个节点
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}分析，通过变量f存储第一个节点，接下来调用Node创建一个新的节点，将新节点作为新first，这时判断，如果之前的first为空，那说明插入之前该链表是空的，那么新插入的节点不仅是first节点而且还是last节点，所以last要指向新插入的 newNode。
如果之前的first不是空，那么不动last，将first的前驱结点设为新节点，此时原first节点为链表的第二个节点。
最后插入成功，将链表节点数量加一
说明：Fail-Fast 机制
变量modCount为记录当前链表被修改的次数。我们知道LinkedList是线程不安全的，在迭代器遍历链表时，迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。在迭代过程中，判断modCount跟expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了。那么将抛出 ConcurrentModificationException。所以当大家遍历那些非线程安全的数据结构时，尽量使用迭代器进行遍历。
重点：向链表中添加元素
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
//添加指定集合到指定位置
public boolean addAll(int index, Collection<? extends E> c) {
//判断需要插入的位置是否合法 index>=0且index小于等于当前链表节点数量
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);
//保存该节点的前驱节点，这里我们将链表断开，准备将集合插入指定位置 succ保存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;
else
//前驱节点的后续节点指向新节点
pred.next = newNode;
//将前驱改成当前节点，以便后续添加c中其它的元素
pred = newNode;
}
//还是两种判断 如果succ为空，说明插入的节点位置是该链表的尾节点的后面
//这时通过上面的遍历我们可以知道，pred肯定指向当前链表最后一个节点，所以将last指向pred
if (succ == null) {
last = pred;
} else {
//此时我们需要将之前断开的链表的后半部分拼接上。pred为当前重组的尾节点，
//则尾节点的后续节点指向succ，succ的前驱节点指向pred
pred.next = succ;
succ.prev = pred;
}
//链表长度增加
size += numNew;
//操作次数增加
modCount++;
return true;
}获取指定位置的节点
//这里我们可以看到对此查找，LinkedList是做了优化的，
//并没有盲目的去全部遍历，而是判断要查找的坐标离头节点近还是尾节点近，来判断是从头遍历还是从尾开始遍历
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;
}
}删除一个元素（元素不为空
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;
}删除 LinkedList 中第一个节点（私有
//根据注释我们可以看出元素必须是第一个元素且不能为空
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//存储待删除节点的值，用作删除成功返回带=待删除节点的值
final E element = f.item;
//存储待删除节点的后续节点
final Node<E> next = f.next;
//把f的值和它的next设置为空
f.item = null;
f.next = null; // help GC
//将他的下一个节点设置为头节点
first = next;
//判断next是否为空，如果为空证明原链表只有一个节点，删除之后是空链表
if (next == null)
//将last也需要设置为空号
last = null;
else
//这是next已经为头节点，需要将头节点的前驱节点设置为空
next.prev = null;
//链表元素数量减一
size--;
//操作次数加一
modCount++;
return element;
}删除 LinkedList 的最后一个节点。（该节点不为空
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 GC
//将他的下一个节点设置为尾节点
last = prev;
//判断prev是否为空，如果为空证明原链表只有一个节点，删除之后是空链表
if (prev == null)
first = null;
else
//将尾节点的后续节点设置为空
prev.next = null;
size--;
modCount++;
return element;
}工具函数
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/**
* Removes and returns the last element from this list.
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}五：总结
元素源码我们可以看出LinkedList在添加删除元素时，不需要像ArrayList一样去扩容。而在根据元素所在位置去查找元素时又不像ArrayList中一样直接去取，而是需要遍历。所以LinkedList更多的适用于频繁添加删除，而查找不多的场景下。
根据位置查找元素时先判断离头节点近还是尾节点近这种优化方式我们也可以用于日常的代码中
LinkedList是线程不安全的，在遍历的过程中我们尽量使用迭代器进行遍历
