LinkedList原理：
1 基于循环双链表，持有首尾结点引用和存储了元素数量，适合元素的添加和删除。链表结点类包含存储的元素、前驱结点引用和后继结点引用。
2 size方法用于获取元素数量，isEmpty方法用于判断是否为空。
3 实现了List接口，add方法用于尾部插入指定元素，remove方法用于删除指定元素。
4 实现了Queue接口（Deque接口继承了Queue接口），add方法用于队尾插入指定元素，remove方法用于队头获取并删除元素。
5 实现了Deque接口，addFirst方法用于队头插入指定元素，removeFirst方法用于队头获取并删除元素，addLast方法用于队尾插入指定元素，removeLast方法用于队尾获取并删除元素。
package java.util;
// 继承了AbstractSequentialList // 实现了List、Deque、Cloneable和java.io.Serializable接口
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
// 元素数量
transient int size = 0;
// 首结点引用
transient Node<E> first;
// 尾结点引用
transient Node<E> last;
// 无参构造方法
public LinkedList() { }
1 // 通过头插法来插入指定元素
2 private void linkFirst(E e) { 3 // 获取当前首结点引用
4 final Node<E> f = first; 5 // 创建新结点
6 final Node<E> newNode = new Node<>(null, e, f); 7 // 新结点设为首结点
8 first = newNode; 9 // 如果插入前链表无结点，则新结点设为尾结点 10 // 否则，新结点设为当前首结点的前驱结点
11 if (f == null) 12 last = newNode; 13 else
14 f.prev = newNode; 15 // 元素数量+1
16 size++; 17 modCount++; 18 }
1 // 通过尾插法来插入指定元素
2 void linkLast(E e) { 3 // 获取当前尾结点引用
4 final Node<E> l = last; 5 // 创建新结点
6 final Node<E> newNode = new Node<>(l, e, null); 7 // 新结点设为尾结点
8 last = newNode; 9 // 如果插入前链表无结点，则新结点设为首结点 10 // 否则，新结点设为当前尾结点的后继结点
11 if (l == null) 12 first = newNode; 13 else
14 l.next = newNode; 15 // 元素数量+1
16 size++; 17 modCount++; 18 }
1 // 在指定非空结点前插入指定元素
2 void linkBefore(E e, Node<E> succ) { 3 // assert succ != null; 4 // 获取指定非空结点的前驱结点引用
5 final Node<E> pred = succ.prev; 6 // 创建新结点
7 final Node<E> newNode = new Node<>(pred, e, succ); 8 // 新结点设为指定非空结点的前驱结点
9 succ.prev = newNode; 10 // 如果指定非空结点的原来前驱结点为空，则新结点设为首结点 11 // 否则，新结点设为指定非空结点的原来前驱结点的后继结点
12 if (pred == null) 13 first = newNode; 14 else
15 pred.next = newNode; 16 // 元素数量+1
17 size++; 18 modCount++; 19 }
1 // 删除首结点，返回存储的元素
2 private E unlinkFirst(Node<E> f) { 3 // assert f == first && f != null; 4 // 获取首结点存储的元素
5 final E element = f.item; 6 // 获取首结点的后继结点
7 final Node<E> next = f.next; 8 // 删除首结点
9 f.item = null; 10 f.next = null; // help GC 11 // 原来首结点的后继结点设为首结点
12 first = next; 13 // 如果原来首结点的后继结点为空，则尾结点设为null 14 // 否则，原来首结点的后继结点的前驱结点设为null
15 if (next == null) 16 last = null; 17 else
18 next.prev = null; // help GC 19 // 元素数量-1
20 size--; 21 modCount++; 22 // 返回原来首结点存储的元素
23 return element; 24 }
1 // 删除尾结点，返回存储的元素
2 private E unlinkLast(Node<E> l) { 3 // assert l == last && l != null; 4 // 获取尾结点存储的元素
5 final E element = l.item; 6 // 获取尾结点的前驱结点
7 final Node<E> prev = l.prev; 8 // 删除尾结点
9 l.item = null; 10 l.prev = null; // help GC 11 // 原来尾结点的前驱结点设为尾结点
12 last = prev; 13 // 如果原来尾结点的前驱结点为空，则首结点设为null 14 // 否则，原来尾结点的前驱结点的后继结点设为null
15 if (prev == null) 16 first = null; 17 else
18 prev.next = null; 19 // 元素数量-1
20 size--; 21 modCount++; 22 // 返回原来尾结点存储的元素
23 return element; 24 }
1 // 删除指定非空结点，返回存储的元素
2 E unlink(Node<E> x) { 3 // assert x != null; 4 // 获取指定非空结点存储的元素
5 final E element = x.item; 6 // 获取指定非空结点的后继结点
7 final Node<E> next = x.next; 8 // 获取指定非空结点的前驱结点
9 final Node<E> prev = x.prev; 10
11 // 如果指定非空结点的前驱结点为空，则指定非空结点的后继结点设为首结点 12 // 否则，指定非空结点的后继结点设为指定非空结点的前驱结点的后继结点， 13 // 指定非空结点的前驱结点设为null
14 if (prev == null) { 15 first = next; 16 } else { 17 prev.next = next; 18 x.prev = null; 19 } 20
21 // 如果指定非空结点的后继结点为空，则指定非空结点的前驱结点设为尾结点 22 // 否则，指定非空结点的前驱结点设为指定非空结点的后继结点的前驱结点， 23 // 指定非空结点的后继结点设为null
24 if (next == null) { 25 last = prev; 26 } else { 27 next.prev = prev; 28 x.next = null; 29 } 30
31 // 指定非空结点存储的元素设为null
32 x.item = null; 33 // 元素数量-1
34 size--; 35 modCount++; 36 // 返回指定非空结点存储的元素
37 return element; 38 }
1 // 获取首结点存储的元素
2 public E getFirst() { 3 // 获取首结点引用
4 final Node<E> f = first; 5 // 如果首结点为空，则抛出无该元素异常
6 if (f == null) 7 throw new NoSuchElementException(); 8 // 返回首结点存储的元素
9 return f.item; 10 }
1 // 获取首结点存储的元素
2 public E getFirst() { 3 // 获取首结点引用
4 final Node<E> f = first; 5 // 如果首结点为空，则抛出无该元素异常
6 if (f == null) 7 throw new NoSuchElementException(); 8 // 返回首结点存储的元素
9 return f.item; 10 }
1 // 获取尾结点存储的元素
2 public E getLast() { 3 // 获取尾结点引用
4 final Node<E> l = last; 5 // 如果尾结点为空，则抛出无该元素异常
6 if (l == null) 7 throw new NoSuchElementException(); 8 // 返回尾结点存储的元素
9 return l.item; 10 }
1 // 删除首结点，返回存储的元素
2 public E removeFirst() { 3 // 获取首结点引用
4 final Node<E> f = first; 5 // 如果首结点为空，则抛出无该元素异常
6 if (f == null) 7 throw new NoSuchElementException(); 8 // 删除首结点，返回存储的元素
9 return unlinkFirst(f); 10 }
1 // 删除尾结点，返回存储的元素
2 public E removeLast() { 3 // 获取尾结点引用
4 final Node<E> l = last; 5 // 如果尾结点为空，则抛出无该元素异常
6 if (l == null) 7 throw new NoSuchElementException(); 8 // 删除尾结点，返回存储的元素
9 return unlinkLast(l); 10 }
// 头部插入指定元素
public void addFirst(E e) { // 通过头插法来插入指定元素
linkFirst(e); }
// 尾部插入指定元素
public void addLast(E e) { // 通过尾插法来插入指定元素
linkLast(e); }
// 判断是否包含指定元素
public boolean contains(Object o) { return indexOf(o) != -1; }
// 获取元素数量
public int size() { return size; }
1 // 插入指定元素，返回操作结果
2 public boolean add(E e) { 3 // 通过尾插法来插入指定元素
4 linkLast(e); 5 return true; 6 }
1 // 删除顺序下首次出现的指定元素，返回操作结果
2 public boolean remove(Object o) { 3 // 遍历链表，查找到指定元素后删除该结点，返回true
4 if (o == null) { 5 for (Node<E> x = first; x != null; x = x.next) { 6 if (x.item == null) { 7 unlink(x); 8 return true; 9 } 10 } 11 } else { 12 for (Node<E> x = first; x != null; x = x.next) { 13 if (o.equals(x.item)) { 14 unlink(x); 15 return true; 16 } 17 } 18 } 19 // 查找失败
20 return false; 21 }
1 // 删除顺序下首次出现的指定元素，返回操作结果
2 public boolean remove(Object o) { 3 // 遍历链表，查找到指定元素后删除该结点，返回true
4 if (o == null) { 5 for (Node<E> x = first; x != null; x = x.next) { 6 if (x.item == null) { 7 unlink(x); 8 return true; 9 } 10 } 11 } else { 12 for (Node<E> x = first; x != null; x = x.next) { 13 if (o.equals(x.item)) { 14 unlink(x); 15 return true; 16 } 17 } 18 } 19 // 查找失败
20 return false; 21 }
1 // 删除所有元素
2 public void clear() { 3 // Clearing all of the links between nodes is "unnecessary", but: 4 // - helps a generational GC if the discarded nodes inhabit 5 // more than one generation 6 // - is sure to free memory even if there is a reachable Iterator 7 // 遍历链表，删除所有结点
8 for (Node<E> x = first; x != null; ) { 9 Node<E> next = x.next; 10 x.item = null; 11 x.next = null; 12 x.prev = null; 13 x = next; 14 } 15 // 首尾结点置空
16 first = last = null; 17 // 元素数量置0
18 size = 0; 19 modCount++; 20 }
1 // 获取指定位置的元素
2 public E get(int index) { 3 // 判断指定位置是否合法
4 checkElementIndex(index); 5 // 返回指定位置的元素
6 return node(index).item; 7 }
1 // 修改指定位置的元素，返回旧元素
2 public E set(int index, E element) { 3 // 判断指定位置是否合法
4 checkElementIndex(index); 5 // 获取指定位置的结点
6 Node<E> x = node(index); 7 // 获取该结点存储的元素
8 E oldVal = x.item; 9 // 修改该结点存储的元素
10 x.item = element; 11 // 返回该结点存储的旧元素
12 return oldVal; 13 }
1 // 在指定位置前插入指定元素
2 public void add(int index, E element) { 3 // 判断指定位置是否合法
4 checkPositionIndex(index); 5
6 // 如果指定位置在尾部，则通过尾插法来插入指定元素 7 // 否则，在指定位置的结点前面插入指定元素
8 if (index == size) 9 linkLast(element); 10 else
11 linkBefore(element, node(index)); 12 }
1 // 删除指定位置的元素，返回旧元素
2 public E remove(int index) { 3 // 判断指定位置是否合法
4 checkElementIndex(index); 5 // 删除指定位置的结点，返回旧元素
6 return unlink(node(index)); 7 }
// 判断指定位置是否合法
private boolean isElementIndex(int index) { return index >= 0 && index < size; }
// 判断迭代器遍历时或插入元素时指定位置是否合法
private boolean isPositionIndex(int index) { return index >= 0 && index <= size; }
// 获取越界异常信息
private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; }
// 判断指定位置是否合法
private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
// 判断指定位置是否合法
private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
1 // 获取指定下标的结点，index从0开始
2 Node<E> node(int index) { 3 // assert isElementIndex(index); 4 // 如果指定下标<一半元素数量，则从首结点开始遍历 5 // 否则，从尾结点开始遍历
6 if (index < (size >> 1)) { 7 Node<E> x = first; 8 for (int i = 0; i < index; i++) 9 x = x.next; 10 return x; 11 } else { 12 Node<E> x = last; 13 for (int i = size - 1; i > index; i--) 14 x = x.prev; 15 return x; 16 } 17 }
Search Operations
1 // 获取顺序下首次出现指定元素的位置 2 // 如果返回结果是-1，则表示不存在该元素
3 public int indexOf(Object o) { 4 // 遍历链表，顺序查找指定元素
5 int index = 0; 6 if (o == null) { 7 for (Node<E> x = first; x != null; x = x.next) { 8 if (x.item == null) 9 return index; 10 index++; 11 } 12 } else { 13 for (Node<E> x = first; x != null; x = x.next) { 14 if (o.equals(x.item)) 15 return index; 16 index++; 17 } 18 } 19 // 查找失败
20 return -1; 21 }
1 // 获取逆序下首次出现指定元素的位置 2 // 如果返回结果是-1，则表示不存在该元素
3 public int lastIndexOf(Object o) { 4 // 遍历链表，逆序查找指定元素
5 int index = size; 6 if (o == null) { 7 for (Node<E> x = last; x != null; x = x.prev) { 8 index--; 9 if (x.item == null) 10 return index; 11 } 12 } else { 13 for (Node<E> x = last; x != null; x = x.prev) { 14 index--; 15 if (o.equals(x.item)) 16 return index; 17 } 18 } 19 // 查找失败
20 return -1; 21 }
Queue operations
1 // 获取首元素
2 public E peek() { 3 // 获取首结点引用
4 final Node<E> f = first; 5 // 如果首结点为空，则返回null 6 // 否则，返回首结点存储的元素
7 return (f == null) ? null : f.item; 8 }
// 获取首元素
public E element() { // 返回首结点存储的元素
return getFirst(); }
1 // 获取并删除首元素
2 public E poll() { 3 // 获取首结点引用
4 final Node<E> f = first; 5 // 如果首结点为空，则返回null 6 // 否则，删除首结点，返回首结点存储的元素
7 return (f == null) ? null : unlinkFirst(f); 8 }
// 获取并删除首元素
public E remove() { // 删除首结点，返回首结点存储的元素
return removeFirst(); }
// 尾部插入指定元素，返回操作结果
public boolean offer(E e) { // 通过尾插法插入指定元素，返回操作结果
return add(e); }
Deque operations
1 // 头部插入指定元素，返回操作结果
2 public boolean offerFirst(E e) { 3 // 通过头插法来插入指定元素
4 addFirst(e); 5 // 操作成功
6 return true; 7 }
1 // 尾部插入指定元素，返回操作结果
2 public boolean offerLast(E e) { 3 // 通过尾插法来插入指定元素
4 addLast(e); 5 // 操作成功
6 return true; 7 }
1 // 获取首元素
2 public E peekFirst() { 3 // 获取首结点引用
4 final Node<E> f = first; 5 // 如果首结点为空，则返回null 6 // 否则，返回首结点存储的元素
7 return (f == null) ? null : f.item; 8 }
1 // 获取尾元素
2 public E peekLast() { 3 // 获取尾结点引用
4 final Node<E> l = last; 5 // 如果尾结点为空，则返回null 6 // 否则，返回尾结点存储的元素
7 return (l == null) ? null : l.item; 8 }
1 // 获取并删除首元素
2 public E pollFirst() { 3 // 获取首结点引用
4 final Node<E> f = first; 5 // 如果首结点为空，则返回null 6 // 否则，删除首结点，返回首结点存储的元素
7 return (f == null) ? null : unlinkFirst(f); 8 }
1 // 获取并删除尾元素
2 public E pollLast() { 3 // 获取尾结点引用
4 final Node<E> l = last; 5 // 如果尾结点为空，则返回null 6 // 否则，删除尾结点，返回尾结点存储的元素
7 return (l == null) ? null : unlinkLast(l); 8 }
// 头部插入指定元素
public void push(E e) { // 通过头插法来插入指定元素
addFirst(e); }
// 获取并删除首元素
public E pop() { // 删除首结点，返回首结点存储的元素
return removeFirst(); }
// 删除顺序下首次出现的指定元素，返回操作结果
public boolean removeFirstOccurrence(Object o) { // 删除顺序下首次出现的指定元素对应的结点，返回操作结果
return remove(o); }
1 // 删除逆序下首次出现的指定元素，返回操作结果
2 public boolean removeLastOccurrence(Object o) { 3 // 遍历链表，从尾结点开始查找指定元素 4 // 如果查找成功，删除该结点，返回true
5 if (o == null) { 6 for (Node<E> x = last; x != null; x = x.prev) { 7 if (x.item == null) { 8 unlink(x); 9 return true; 10 } 11 } 12 } else { 13 for (Node<E> x = last; x != null; x = x.prev) { 14 if (o.equals(x.item)) { 15 unlink(x); 16 return true; 17 } 18 } 19 } 20 // 查找失败
21 return false; 22 }
1 // 链表结点类
2 private static class Node<E> { 3 // 存储的元素
4 E item; 5 // 后继结点
6 Node<E> next; 7 // 前驱结点
8 Node<E> prev; 9
10 // 前驱结点、存储的元素和后继结点作为参数的构造方法
11 Node(Node<E> prev, E element, Node<E> next) { 12 this.item = element; 13 this.next = next; 14 this.prev = prev; 15 } 16 }
1 // 父类克隆方法
2 @SuppressWarnings("unchecked") 3 private LinkedList<E> superClone() { 4 try { 5 return (LinkedList<E>) super.clone(); 6 } catch (CloneNotSupportedException e) { 7 throw new InternalError(e); 8 } 9 }
1 // 克隆，浅拷贝
2 public Object clone() { 3 LinkedList<E> clone = superClone(); 4
5 // Put clone into "virgin" state 6 // 链表初始化
7 clone.first = clone.last = null; 8 clone.size = 0; 9 clone.modCount = 0; 10
11 // Initialize clone with our elements 12 // 插入结点
13 for (Node<E> x = first; x != null; x = x.next) 14 clone.add(x.item); 15
16 // 返回克隆后的对象引用
17 return clone; 18 }
// 序列化版本号
private static final long serialVersionUID = 876323262645176354L;
1 // 序列化
2 private void writeObject(java.io.ObjectOutputStream s) 3 throws java.io.IOException { 4 // Write out any hidden serialization magic 5 // 默认序列化
6 s.defaultWriteObject(); 7
8 // Write out size 9 // 写入元素数量
10 s.writeInt(size); 11
12 // Write out all elements in the proper order. 13 // 遍历链表，写入所有元素
14 for (Node<E> x = first; x != null; x = x.next) 15 s.writeObject(x.item); 16 }
1 // 反序列化
2 @SuppressWarnings("unchecked") 3 private void readObject(java.io.ObjectInputStream s) 4 throws java.io.IOException, ClassNotFoundException { 5 // Read in any hidden serialization magic 6 // 默认反序列化
7 s.defaultReadObject(); 8
9 // Read in size 10 // 读取元素数量
11 int size = s.readInt(); 12
13 // Read in all elements in the proper order. 14 // 遍历链表，读取所有元素并尾部插入
15 for (int i = 0; i < size; i++) 16 linkLast((E)s.readObject()); 17 }
参考资料
JDK_API_1_6_zh_CN.CHM