jdk源码追踪-LinkedList
关于List接口的类结构和AbstractList的讲解，可以看看上一篇文章jdk源码追踪-ArrayList。
AbstractSequentialList
AbstractSequentialList使用迭代器来实现get(int index), remove(int index), add(int index, E e)基本算法。迭代器是实际调用抽象方法listIterator，需要子类实现，是LinkedList的父类。由于它对于index元素的操作都是通过迭代器的next循环实现，所以效率比起ArrayList的数组直接操作下标元素的方式慢很多。
####LinkedList
LinkedList继承AbstractSequentialList，ListedList实现的数据结构是标准的双向链表，有两个属性first和last两个Node类型的属性。LinkedList实现或重写的有
- 链表存储结构
- get(int index)，
- add(T t)，
- add(T t, int index)，
- remove(int index)，
- 它实现了list迭代器，list迭代器是迭代器的具体实现。
LinkedList的存储数据结构
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
//transient 变量修饰符，用transient关键字标记的成员变量不参与序列化过程
transient int size = 0;
//头节点
transient Node<E> first;
//尾节点
transient Node<E> last;
public LinkedList() {
}
//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;
}
}
}get(int index)方法采用的是二分再遍历的查找，如果index小于size/2时，从头正序遍历，否则，反序遍历到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;
}
}add(T t)，add(T t, int index))，remove(int index)都采用的十分标准的链表插入，删除实现。
//add(T t, int index))调用
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;
size++;
modCount++;
}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;
}remove时会把remove的那个节点的前驱，后驱，item都设空，目的是为了GC。
它自己实现了list迭代器，list迭代器是它的父类AbstractSequentialList用来实现迭代器的。为什么要实现这个迭代器？AbstractList中list迭代器的实现是通过get(int index)和记录当前index来实现，对于链表来说，每次的next()，都意味着从头遍历到当前节点，这么做效率肯定很慢。LinkedList的实现是保存上传返回结点lastReturned和下一个结点next。next()执行时，将next的引用赋给lastReturned，next.next赋给next返回lastReturned的数据。
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
}