LinkedList概述
LinkedList是有序并且可以元素重复的集合，底层是基于双向链表的。也正因为是链表，所以也就没有动态扩容的步骤了。
除了 实现List 接口之外，LinkedList 还实现了 Deque，Cloneable，Serializable 三个接口。这说明该数据结构支持队列，克隆和序列化操作的。与 ArrayList 一样，允许 null 元素的存在，且是（不支持多线程）的。
成员变量
LinkedList 提供了以下三个成员变量。size，first，last。
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
其中 size 为 LinkedList 的大小，first 和 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;
}
}
Node 是 LinkedList 的内部类，定义了存储的数据元素，前一个节点和后一个节点，典型的双向链表结构。
构造方法
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
构造方法一个是默认的，另外一个是传入一个集合，然后调用 addAll 方法添加集合所有的元素。
添加元素
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
// 保存原来链表尾部节点，last 是全局变量，用来表示队尾元素
final Node<E> l = last;
// 包装元素数据构建新节点 pre赋值
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
// 如果尾节点为空，将新节点赋值给first节点
first = newNode;
else
// 如果尾节点不为空，将新节点添加至尾部 next赋值
l.next = newNode;
size++;
modCount++;
}
// 向指定位置添加元素
public void add(int index, E element) {
// 检查index是否有效
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
// node(index) 方法是获取index索引上的 节点
linkBefore(element, node(index));
}
// 添加一个元素在链表的头节点位置 把e元素插入到succ节点前面
void linkBefore(E e, Node<E> succ) {
// pred指向succ的前一个结点
final Node<E> pred = succ.prev;
//生成一个新结点，结点的值为e，其前向指针指向pred,后向指针指向succ
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
总之：linkLast linkBefore方法都是对新元素创建节点 完成节点的pred,next指向（存在前后节点的情况下），前一个节点的next,当前节点的pre,next,后一个节点的pre
获取元素
// 在内部调用了 node(index) 方法
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// 如果 index 在前半段，从前往后遍历获取 node
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 如果 index 在后半段，从后往前遍历获取 node
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
node()获取元素方法：得到 index 对应的节点，在速度上做了算法优化。
移除元素
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
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指向
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
// 设置该节点的下一个节点的 prev 为该节点的 prev，断掉该节点的next指向
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
修改元素
修改节点，LinkedList 只提供了 set(int index, E element) 一个方法。
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
判断角标是否越界->采用 node 方法查找对应索引的节点 -> 设置新值返回旧的值
Deque 双端队列
我们都知道 Queue 是一个队列，遵循 先进先出 准则，我们也知道 Stack 是一个栈结构，遵循 先进后出 准则。 而Deque 这个双端队列就厉害了,它既可以实现栈的操作，也可以实现队列的操作，换句话说，实现了这个接口的类，既可以作为栈使用也可以作为队列使用。
继承自双端队列的添加方法：
//入栈，其实就是在头部添加元素
public void push(E e) {
addFirst(e);
}
//安全的添加操作，在尾部添加
public boolean offer(E e) {
return add(e);
}
//在头部添加
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//尾部添加
public boolean offerLast(E e) {
addLast(e);
return true;
}
继承自双端队列的删除方法：
public E pop() {
return removeFirst();
}
public E pollFirst() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollLast() {
final Node l = last;
return (l == null) ? null : unlinkLast(l);
}
总结
- ArrayList是基于动态数组实现的，LinkedList是基于双向链表实现的；因此添加删除效率高，查找效率低。
- LinkedList是基于链表实现的，因此不存在容量不足的问题，所以这里没有扩容的方法.
LinkedList在数据存储上不存在浪费空间的情况。ArrayList动态扩容会导致有一部分空间是浪费的。 - 实现了栈和队列的相关方法,LinkedList也可以作为栈、队列和双端队列来使用
- 无参构造方法直接建立一个仅包含head节点的空链表
- 在查找和删除某元素时，源码中都划分为该元素为null和不为null两种情况来处理，LinkedList中允许元素为null。