概述
继承结构
类描述
如继承结构所示，LinkedList是两个接口(List和Deque)的混合实现。其实现了List接口中所有的可选操作，并且LinkedList允许所有元素（包括null）的插入和访问操作。LinkedList的所有操作均基于双向链表实现，当根据下标对链表中的元素进行访问，将通过从头至尾或者从尾至头遍历链表中的所有元素，来到达指定位置。
LinkedList和ArrayList都不是线程安全的。当多个线程同时访问一个链表时，如果有一个对链表的结构进行了修改，则必须在外部显示的进行同步的处理。一般情况下，通过对包含本链表的对象进行同步处理。如果没有这种类型的对象，则可以通过如下方式生成一个线程安全的链表：
List list = Collections.synchronizedList(new LinkedList(...));该类中的iterator和listIterator返回的迭代器仍然采用快速失败(fail-fast)机制：当链表由于调用除该迭代器的remove和add方法外，产生了结构行修改，该迭代器将抛出一个同步修改异常(ConcurrentModificationException)。因此，当发生同步修改时，迭代器将不会在未来的某个时间里，返回潜在的脏数组，或者产生不可预期的行为。
注意：快速失败机制并不会保证方法生非同步并发修改时行为的正确性（我想到的情况是：在两个进程进行列表结构修改操作的时间相同，且对方法中进行失败机制校验的方法调用时间也极其接近时，可能出现两个进程均通过同步修改校验， 且均对链表进行了结构行修改），这样对于这两个进程，仍然认为链表的是同步的，其实已经产生了脏数据。快速失败机制只是在保证检测到同步修改时，抛出异常，证明脏数据存在的可能。因此，在编码过程中最好不要依赖同步修改异常做逻辑处理，但快速失败机制一般可用于调试bug。
内部类介绍
数据节点类(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类为一个静态内部类，其不需要外部对象即可初始化。由Node的结构及属性可以看出，LinkedList的数据存储结构与C
语言中双向链表形式相同。每个节点除持有该节点的有效数据外，还需要持有指向上个节点和下个节点的指针，因此其单个节点占用的空间高于ArrayList中采用数组存储的节点。
列表迭代器类(ListItr)
属性介绍
private Node<E> lastReturned;用户最后一次调用next()或者previous返回的节点；
private Node<E> next;用户下次调用next()返回的节点；
private int nextIndex;用户下次调用next()返回的节点的下标值。
private int expectedModCount = modCount;迭代器创建时，其持有的链表对象发生结构性修改的次数，主要用于并发修改的校验；
构造方法
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}生成一个由链表特定位置开始的列表迭代器。当用户传入的index（有效下标为0 ～ size-1）与链表长度size相等时，则代表调用next()方法时，将不会返回任何有效元素（抛出异常或者返回null）。
方法介绍
public boolean hasNext() {
return nextIndex < size;
}判断链表迭代器下次调用next方法时，是否还能返回有效的元素。由于链表中元素的有效下标范围时0 ～ size-1，因此当迭代器游标位置小于链表长度size时，则返回true，否则返回false。
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}返回列表迭代器当前游标对应的元素。在进行元素访问之前，需要进行并发修改的校验。由代码可以看出，LinkedList迭代器的原生迭代器抛出异常来代表链表中不再有有效元素，而不是返回一个特殊值（null）。
public boolean hasPrevious() {
return nextIndex > 0;
}判断列表迭代器下次调用previous时，是否还能返回有效的元素。当列表迭代器的游标大于0时，则代表列表迭代器可以向前遍历，返回true，否则返回false。
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}返回迭代器当前游标的前一个元素。注意，在调用本方法时，当迭代器位于链表的尾端时，需要特殊处理。因为迭代器位于链表尾端时，迭代器中的的next对应的节点为null。
public int nextIndex() {
return nextIndex;
}返回链表下次调用next()方法返回元素的下标，与nextIndex相等。
public int previousIndex() {
return nextIndex - 1;
}返回链表下次调用previous()方法返回元素的下标，一般的值为：nextIndex - 1。
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}删除链表上次调用next()或者previous()访问的元素。当迭代器上次访问的元素为当前游标指向的元素时（一般为调用previous()方法，这时链表最后一次访问的元素与链表迭代器游标指向的元素相同），则需要做指针的移动，否则做迭代器游标移动。
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}用e替代链表迭代器最后一次返回的元素。
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}在链表迭代器当前指向的节点之前添加一个新节点，如果迭代器指向链表末尾时，则将新元素追加到链表的尾部。
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}这是Java 8为Iterator新增的默认方法,该方法可使用Lambda表达式来遍历集合元素
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}检测当前链表是否有并发结构修改，如果有，则抛出并发修改异常。
反向迭代器(DescendingIterator)
属性介绍
private final ListItr itr = new ListItr(size());基链表迭代器实现，初始化时，将迭代器的游标置于链表尾部，列表迭代器初始化游标为size，而不是0。
方法介绍
public boolean hasNext() {
return itr.hasPrevious();
}判断反向迭代器是否仍有有效元素，基于链表迭代器的hasPrevious()实现。
public E next() {
return itr.previous();
}返回反向迭代器的下一个元素，基于链表迭代器的previous()实现。
public void remove() {
itr.remove();
}删除反向迭代器上一次访问的元素。
属性介绍
transient int size = 0;链表长度，即：链表中有效元素的个数；
transient Node<E> first;链表中的第一个节点，需要满足的条件为：(first == null && last == null)(链表为空时)或者(first.prev == null && first.item != null)(链表不为空时)。
transient Node<E> last;链表中的最后一个节点，需要满足的条件为：(first == null && last == null)(链表为空时)或者(last.next == null && last.item != null)(链表不为空时)。
构造方法
public LinkedList() {
}链表默认构造方法，生成一个不包含任何元素的空链表。
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}生成一个包含集合c中所有元素的链表。元素在链表中的顺序与集合c的迭代器返回元素的顺序相同。
方法介绍
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++;
}将e作为链表新的头节点插入到链表中。链表中指针的移动与C语言中在链表头部插入一个新元素基本相同，注意：C语言中的链表一般带有一个头节点（即：仅代表链表的开始，并不存储有效数据，next指针指向链表真实的第一个元素），而在LinkedList中是不包含这种类型的节点的。
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++;
}将e作为链表新的尾节点插入到链表中。
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++;
}在指定节点succ前新增一个节点e。
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}将节点f及以前的元素从链表中移除。在jdk中，认为f就是该链表的头节点，并将本方法声明为private，防止该方法的滥用。实际上，该方法可以将f及以前的元素从链表中移除，但是由于在本方法中，仅仅将f节点对应的数据进行了置空操作，用于协助GC机制的执行，因此如果该方法被滥用，删除的f不是链表的头节点时，可能出现内存溢出的问题。
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}将节点f及以后的元素从链表中移除，与unlinkFirst类似，声明为private，防止滥用导致的内存溢出。
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;
}将节点x从链表中移除，并做指针的移动，其移动规则与C语言中类似。
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}返回链表中的第一个有效元素，当链表为空时候，抛出NoSuchElementException。
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}返回链表中的最后一个有效元素，当链表为空时候，抛出NoSuchElementException。
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}删除链表的第一个有效元素，当链表为空时候，抛出NoSuchElementException。
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}删除链表的最后一个有效元素，当链表为空时候，抛出NoSuchElementException。
public void addFirst(E e) {
linkFirst(e);
}在链表头部插入一个新的节点。
public void addLast(E e) {
linkLast(e);
}在链表尾部插入一个新的节点。
public boolean contains(Object o)判断链表中是否包含元素o，如果包含，返回true，否则返回false。
public int size()返回链表中有效元素的个数。
public boolean add(E e)将元素e追加到链表的尾部，与addLast方法功能基本相同，本方法在插入成功后会返回true。
public boolean remove(Object o)从链表中删除第一个与元素o相等的节点，如果有该元素，则返回true，否则返回false。
public boolean addAll(Collection<? extends E> c)将集合c中的所有元素追加到链表的末尾，其追加顺序与c的迭代器返回元素的顺序相同。但是，如果在此期间，c发生了结构性修改，则可能导致不可预期的结果。
public boolean addAll(int index, Collection<? extends E> c)将集合c中所有的元素追加到链表的指定位置，其追加顺序与c的迭代器返回元素的顺序相同。其首先调用c的toArray方法，将c转化为一个数组，而后遍历这个数组，将数组中的元素依次插入到指定位置中。
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}删除链表中所有的节点。注意，在删除的过程中，需要从头节点开始遍历链表中的每一个节点，将每个节点的均设为null，保证GC机制可以回收链表占用的内存。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}返回链表中指定位置节点中的元素。
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}将链表指定位置的元素替换为element，并将该位置原始值返回。
public void add(int index, E element)在链表的指定位置插入一个新元素，其内部基于函数linkLast(element)和linkBefore(element, node(index))实现。
public E remove(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;
}
}返回链表指定位置的节点。其使用右移操作判断需要检索的index位于链表的前端还是后端，而后决定采取正向遍历还是逆向遍历访问节点。
public int indexOf(Object o)返回元素o在链表中第一次出现的位置。当元素o在链表中不存在时，返回-1。
public int lastIndexOf(Object o)返回元素o在链表中最后一次出现的位置。当元素o在链表中不存在时，返回-1。
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}返回链表中的第一个有效元素，当链表为空时，返回null。
public E element()返回链表中的第一个有效元素，实现逻辑与getFirst()相同，在链表为空时，抛出NoSuchElementException异常。
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}返回并删除链表中的第一个元素，当链表为空时，返回null。
public E remove()返回并删除链表中的第一个元素，实现逻辑与removeFirst()相同，当链表为空时，抛出NoSuchElementException异常。
public boolean offer(E e)将元素e追加到链表的尾部，实现逻辑与add(e)相同。
public boolean offerFirst(E e)将元素e追加到链表的头部，实现逻辑与addFirst(e)相同。
public boolean offerLast(E e)将元素e追加到链表的尾部，实现逻辑与addLast(e)相同。
public E peekFirst()返回链表的第一个有效元素，实现逻辑与peek()相同。
public E peekLast()返回链表的最后一个有效元素，当链表为空时，返回null。
public E pollFirst()返回并删除链表的第一个有效元素，实现逻辑与poll()相同。
public E pollLast()返回并删除链表的最后一个有效元素，当链表为空时，返回null，而removeLast()方法则会抛出NoSuchElementException异常。
public void push(E e)将元素e追加到链表的头部，与函数addFirst()等价，且内部基于addFirst()实现。
public E pop()返回并删除链表的第一个元素，其内部基于removeFirst()实现，因此当链表为空时，则会抛出NoSuchElementException异常。
public boolean removeFirstOccurrence(Object o)删除元素o在列表中第一次出现的节点。
public boolean removeLastOccurrence(Object o)删除元素o在列表中最后一次出现的节点。
public ListIterator<E> listIterator(int index)返回由链表指定位置开始的列表迭代器。
public Iterator<E> descendingIterator()返回链表的一个反向基础迭代器。
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}将链表转化为数组。其基本思想为：申请一个与链表长度相同的数组，而后正向遍历链表，将链表节点中的元素设定到数组的指定位置中，并将其返回。
public <T> T[] toArray(T[] a) {
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}将链表转化为数组，并将其保存到a中。其实现逻辑与ArrayCollection类似，参见java.util.AbstractCollection学习笔记。