准备知识
结构图：
LinkedList.png
①LinkedList是一种双向链表。
②根据双向链表的特点，会有头节点和尾节点，并且节点之间是通过前驱指针和后继指针来维护关系的，而不是像数组那样通过位置下标来维护节点间关系的。所以既可以从头到尾遍历，又可以从尾到头遍历。
LinkedList中Node节点类的数据结构
//E类型的Node类，作为LinkedList双向链表中的节点
private static class Node<E> {
//E类型的值item
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;
}
}
属性
// 初始化链表的长度为0
transient int size = 0;
说明：双向链表的长度
//指向头节点的变量first
transient Node<E> first;
说明：双向链表的头节点
//指向尾节点的变量last
transient Node<E> last;
说明：双向链表的尾节点
构造方法
构造方法1：构造一个空的LinkedList链表结构
public LinkedList() { }
构造方法2：构造一个包含指定元素的collection集合中元素的LinkedList
public LinkedList(Collection<? extends E> c) {
this();
//使用addAll方法，实际上就是使用遍历c并且采用头插法进行双向链表插入值。
addAll(c);
}
方法
addAll方法将指定集合中的所有元素从指定位置开始插入此列表：
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
追加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。
public boolean addAll(int index, Collection<? extends E> c) {
//判断下标元素是否在链表的长度范围之内
checkPositionIndex(index);
//将集合c转换成Object数组
Object[] a = c.toArray();
int numNew = a.length;
//如果Object数组长度为0，那么就返回添加失败
if (numNew == 0)
return false;
//pred节点为succ节点的前驱
Node<E> pred, succ;
//如果下标等于链表的长度时，pred为尾节点，succ指向为空
if (index == size) {
succ = null;
pred = last;
} else {
/* 如果下标不等于链表长度，node方法就是用来通过下标索引获
* 取链表中的对应的节点对象。
*/
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked")
E e = (E) o;
//将遍历的值包装成节点Node，初始化前驱节点为pred，后继节点为null
Node<E> newNode = new Node<>(pred, e, null);
//如果前驱节点为空，那么肯定是头节点
if (pred == null)
first = newNode;
else
//否则不是头节点，那么前驱的后继节点为当前节点，其实就是类似于链表的插入节点操作。
pred.next = newNode;
pred = newNode;
}
/*
* 因为pred节点是succ节点的前驱节点，反之succ是pred的后继节点.
* 如果succ为空，说明pred为尾节点。
*/
if (succ == null) {
last = pred;
} else {
/* 如果succ不是尾节点，那么只要保证pred节点是succ节点的前驱
* 节点、succ是pred的后继节点这种双向链表的关系
*/
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
add(E e)方法：将元素插入到链表的尾部
//采用双向链表的尾插法
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
//创建临时节点l初始化为尾节点（那么其后继节点为null，前驱节点不为空）。
final Node<E> l = last;
//初始化新节点，前驱节点为l，后继暂为null
final Node<E> newNode = new Node<>(l, e, null);
//由于是在链表尾部插入节点，那么新节点就作为尾节点。
last = newNode;
/**
* l节点作为newNode节点的前驱节点。
* 如果l为空，那么newNode前驱节点为空。
* 在双向链表中，前驱节点为空，那么该节点为头节点。
*/
if (l == null)
first = newNode;
else
l.next = newNode;
size++;//再插入节点后，链表的长度加1
modCount++;
}
说明：如果尾节点为空，那么将新节点作为头节点；否则新节点插入到尾节点后面。
add(int index, E element)方法：在链表指定的位置插入元素
public void add(int index, E element) {
//先检查索引是否在链表的范围内。
checkPositionIndex(index);
if (index == size)
//如果索引等于链表长度，那么直接采用尾插法的linkLast方法。
linkLast(element);
else
linkBefore(element, node(index));
}
/**
* 在节点succ作为通过下标索引在链表中查询出来的对应的节点。
* e值包装的节点插入到succ节点之前。
*/
void linkBefore(E e, Node<E> succ) {
//succ节点的前驱为pred
final Node<E> pred = succ.prev;
//初始化新节点前驱为pred，后继为succ，意思就是想在pred和succ节点之间插入newNode节点
final Node<E> newNode = new Node<>(pred, e, succ);
//到这步，newNode已经确立了，后继节点为succ。succ节点的前驱为newNode。
succ.prev = newNode;
//如果pred为空，那么newNode的前驱节点为空，可以确定newNode为头节点。
if (pred == null)
first = newNode;
else
/* 如果pred不为空，则确定了pred节点后继为newNode，之前已经确
* 定newNode的前驱为pred，这样pred和newNode就确立关系了。
*/
pred.next = newNode;
size++;//新增节点，长度更新为原来长度加1
modCount++;
}
说明：将元素插入指定位置，首先通过位置获取当前对应的定位节点。如果下标对应的定位节点就是尾节点，那么直接使用linkLast方法在链表尾部插入节点。如果对应的定位节点不是尾节点，就插入到定位节点的前面。
addFirst方法：将指定元素插入到链表的头部
/**
* 将指定元素插入到链表的头部
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* 将e作为头结点，采用双向链表的头插法
*/
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++;
}
说明：如果双向链表为空，那么插入节点作为头节点，如果双向链表不为空，那么插入节点作为头结点的前驱节点。
addLast方法：插入元素到链表的尾部
/**
* 将指定元素插入到链表的尾部
*/
public void addLast(E e) {
linkLast(e);
}
//采用双向链表尾插法的方式插入元素
void linkLast(E e) {
//创建临时节点l初始化为尾节点（那么其后继节点为null，前驱节点不为空）。
final Node<E> l = last;
//初始化新节点，前驱节点为l，后继暂为null
final Node<E> newNode = new Node<>(l, e, null);
//由于是在链表尾部插入节点，那么新节点就作为尾节点。
last = newNode;
/**
* l节点作为newNode节点的前驱节点。
* 如果l为空，那么newNode前驱节点为空。
* 在双向链表中，前驱节点为空，那么该节点为头节点。
*/
if (l == null)
first = newNode;
else
l.next = newNode;
size++;//再插入节点后，链表的长度加1
modCount++;
}
说明：如果双向链表为空，那么直接新节点作为头节点。如果双向链表不为空，那么在尾节点后面插入新节点。
remove(Object o)方法：删除双向链表中首次出现的元素
/**
* 列表中移除首次出现的元素
*/
public boolean remove(Object o) {
/* 通过双向链表的前后关系，遍历双向链表。
* 判断是否存在元素和要删除的元素相同。
* 如果遍历到了，那么就删除元素，并且返回true
* 如果没遍历到，那么就返回false
*/
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;
}
/**
* 删除非空节点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 {
/* 如果前驱不为空，那么就直接采用双向链表删除节点的套路，
* 此处是解决前驱节点和删除节点的链接关系
* 直接将前驱节点的后继关系指向后继结点，就解决了前驱节点的后继关系
* 将删除节点x的前驱设置为空，就解决了删除节点的前驱关系
*/
prev.next = next;
x.prev = null;
}
//如果后继结点为空，说明当前删除的节点为尾节点，那么就让其前驱节点作为尾节点
if (next == null) {
last = prev;
} else {
/* 如果后继不为空，那么就直接采用双向链表删除节点的套路，
* 此处是解决删除节点和后继结点的链接关系
* 直接将后继节点的前驱关系指向前驱节点，就解决了后继结点的前驱关系
* 将删除节点x的后继设置为空，就解决了删除节点的后继关系
*/
next.prev = prev;
x.next = null;
}
//如果上面双向链表删除关系不清楚可以自己画图看看就明白了
//将删除节点的值设置为空，便于gc
x.item = null;
size--;
modCount++;
return element;
}
说明：从头结点遍历链表，找到第一次出现的节点；
如果定位节点的前驱为空，那么说明定位节点为头节点，将头结点的后继节点设置为头节点。如果定位节点的前驱节点不为空，那么将定位节点的后继节点设置为定位节点前驱节点的后继节点。
如果定位节点的后继节点为空，那么将尾节点设置为null。
如果定位节点的后继节点不为空，那么将定位节点的后继节点的前驱节点设置定位节点的前驱节点。
get方法：获取双向链表中指定下标的节点值。
public E get(int index) {
// 校验下标不超出范围
checkElementIndex(index);
// 通过下标获取节点，返回节点的值
return node(index).item;
}
// 通过下标获取节点
Node<E> node(int index) {
// 判断下标索引是更靠近头节点还是尾节点
if (index < (size >> 1)) {
// 获取头节点
Node<E> x = first;
// 循环遍历找到index的节点
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 获取尾节点
Node<E> x = last;
// 循环遍历找到index的节点
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
说明：首先判断下标更靠近头节点还是尾节点，减少遍历的次数。
如果靠近头节点，那么就从头节点向后遍历到指定的下标索引节点。
如果靠近尾节点，那么就从尾节点向前遍历到指定的下标索引节点。
总结
1. LinkedList采用一种双向链表实现。
2. LinkedList添加的元素，取时与添加时的顺序一致。因为向双向链表的尾部添加元素，然后按照头节点顺序遍历获取，所以一致。
3. LinkedList允许添加重复元素。
4. LinkedList不是线程安全的集合。
5. LinkedList允许添加null元素。
6. add方法插入元素是在双向链表的尾部插入。
7. get方法遍历双向链表，先判断下标靠近头节点还是尾节点，这样会减少多余的循环。
