LinkedList是一个实现了List接口和Deque接口的双端链表。
有关索引的操作可能从链表头开始遍历到链表尾部，也可能从尾部遍历到链表头部，这取决于看索引更靠近哪一端
LinkedtList内部的成员变量如下:
transient int size = 0;
transient Node<E> first; //指向链表头部
transient Node<E> last; //指向链表尾部
其中size表示当前链表中的数据个数。下面是Node节点的定义，Node类LinkedList的静态内部类:
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(E e)
add(E e)用于将元素添加到链表尾部，实现如下:
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;//指向链表尾部
final Node<E> newNode = new Node<>(l, e, null);//以尾部为前驱节点创建一个新节点
last = newNode;//将链表尾部指向新节点
if (l == null)//如果链表为空，那么该节点既是头节点也是尾节点
first = newNode;
else//链表不为空，那么将该结点作为原链表尾部的后继节点
l.next = newNode;
size++;//增加尺寸
modCount++;
}
从上面代码可以看到，linkLast方法中就是一个链表尾部添加一个双端节点的操作，但是需要注意对链表为空时头节点的处理
add(int index,E e)
add(int index,E e)用于在指定位置添加元素。实现如下：
public void add(int index, E element) {
checkPositionIndex(index); //检查索引是否处于[0-size]之间
if (index == size)//如果要插入的索引位置就是链表的长度，就添加在链表尾部
linkLast(element);
else//添加在链表指定位置
linkBefore(element, node(index));
}
从上面代码可以看到，主要分为3步：
- 检查index的范围，否则抛出异常
- 如果插入位置是链表尾部，那么调用linkLast方法
- 如果插入位置是链表之间，那么调用linkBefore方法
linkLast方法前面已经讨论了，下面看一下linkBefore的实现。在看linkBefore之前，先看一下node(int index)方法，该方法返回指定位置的节点，实现如下：
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;
}
}
从上面可以看到，node(int index)方法将根据index是靠近头部还是尾部选择不同的遍历方向。一旦得到了指定索引位置的节点，再看linkBefore()方法，实现如下：
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; //如果指定位置前一个没有节点，则新节点变成第一个节点
else
pred.next = newNode; //前一个有节点则让前一个节点的下个节点指向新节点，也就是新节点就在pred和succ节点之间了
size++;
modCount++;
}
从上图以及代码可以看到linkBefore主要分三步：
- 创建newNode节点，将newNode的后继指针指向succ，前驱指针指向pred
- 将succ的前驱指针指向newNode
- 根据pred是否为null，进行不同操作。
- 如果pred为null，说明该节点插入在头节点之前，要重置first头节点
- 如果pred不为null，那么直接将pred的后继指针指向newNode即可
