概述
LinkedList底层采用的是双向链表结构，有一个头节点first，一个尾节点last，双向链表意味着我们可以从头开始正向遍历，或者是从尾开始逆向遍历，并且可以针对头部和尾部进行相应的操作。
双向链表结构.png
继承关系
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList继承了AbstractSequentialList，这个类其实可以算简化版的List的实现，因为里面只有一些简单的方法，比如get，set，add，remove，addAll等等，但这些实现是基于迭代器的，也就是说要遍历链表中最多一半的数据(如果i大于数组大小的一半，则从尾部开始遍历)，所以性能相对于实现随机访问接口RandomAccess，肯定是慢的。
另外，这个类实现了Deque，双端队列，那么这就意味着LinkedList是双端队列的一种实现方式，所以基于双端队列的操作在LinkedList中都是有效的。
属性
/**
* 链表大小，transient修饰，不需要序列化
*/
transient int size = 0;
/**
* 首节点，transient修饰，不需要序列化
*/
transient Node<E> first;
/**
* 尾节点，transient修饰，不需要序列化
*/
transient Node<E> last;
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;
}
}
方法
add，addFirst，addLast方法
public boolean add(E e) {
// 在链表尾部添加
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
// 构造一个新的节点，pre指向尾节点，next指向null
final Node<E> newNode = new Node<>(l, e, null);
// 重新赋值尾节点
last = newNode;
// 如果原先尾节点是null，赋值给头节点
if (l == null)
first = newNode;
// 尾节点不为空，尾节点的next为新生成的节点
else
l.next = newNode;
size++;
// 结构性修改加1，线程相关
modCount++;
}
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(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++;
}
addAll方法，中间包括了node(index)方法
public boolean addAll(int index, Collection<? extends E> c) {
// 校验index是否合法
checkPositionIndex(index);
// 将集合转为数组
Object[] a = c.toArray();
int numNew = a.length;
// 如果数组为空，直接返回
if (numNew == 0)
return false;
// 构造要插入元素位置的pre与next
Node<E> pred, succ;
// 如果要插入的是链表末尾
if (index == size) {
succ = null;
pred = last;
} else {
// 不是在链表尾部插入，通过node()获取到这个位置的节点
succ = node(index);
// 将这个节点的pre指向要插入的节点
pred = succ.prev;
}
// 遍历数组
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
// 构造数组中的元素为Node节点，并且pre指向
Node<E> newNode = new Node<>(pred, e, null);
// 表示在第一个元素之前插入
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
// 在最后一个元素之后插入
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
Node<E> node(int 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;
}
}
// 这样就只需要遍历最多一半的结点就可以找到指定索引的结点
步骤大概如下：
- 构造两个节点pred(待插入位置的上一个节点)，succ(待插入位置的下一个节点)
- 遍历数组，将新节点的pre指向pred, 并将pred的next指向newNode；
- 将新节点的next指向succ，并将succ的pre指向新节点；
链表添加.png
其实第二步的图画的有些问题，因为pred在变化，不过将就着看吧，反正能看懂。
remove方法
至于remove方法，即是在删除元素的时候，将要删除的节点从链表中断开，比较简单，不做过多讲解了。
总结
LinkedList是基于链表实现的，所以也就具备了链表的优点与缺点，利于插入删除，不利于查询。
