数组是连续存储，对内存空间的要求较高，相反链表将存储的对象放在独立节点上，对内容空间要求低，而且利用率还高。链表的每个节点还存放着序列中下一个节点的引用。这种要单链表，如果即存后续节点引用，也存前置节点的引用，那么就是双向链表了，在 Java 中的链表都是双向的。
LinkedList 基于双向链表的方式实现，在插入和删除时更优于 ArrayList，但随机访问则比 ArrayList 逊色些。为追求效率 LinkedList 没有实现同步（ synchronized ），如果需要多个线程并发访问，可以先采用 Collections.synchronizedList() 方法对其进行包装。它实现了 List 接口和 Deque 接口，同时也实现了 Cloneable、Serializable 接口。也就是它既可以看作一个顺序容器，又可以看作一个队列和栈，同时支持复制、序列化。
关于栈或队列，现在首选是 ArrayDeque，它有着比 LinkedList（当作栈或队列使用时）更好的性能。
父类 AbstractSequentialList
AbstractSequentialList 提供了一套基于顺序访问的接口。通过继承此类，子类仅需实现部分代码即可拥有完整的一套访问某种序列表（比如链表）的接口。深入源码，AbstractSequentialList 提供的方法基本上都是通过 ListIterator 实现的，所以只要继承类实现了 listIterator 方法，它不需要再额外实现什么即可使用。
public abstract class AbstractSequentialList<E> extends AbstractList<E> { protected AbstractSequentialList() {} public E get(int index) { try { // 使用 ListIterator 的查找方法 return listIterator(index).next(); } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } } public E set(int index, E element) { try { // 使用 ListIterator 的查找方法 ListIterator<E> e = listIterator(index); E oldVal = e.next(); e.set(element); return oldVal; } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } } public void add(int index, E element) { try { // 使用 ListIterator 的新增方法 listIterator(index).add(element); } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } } public E remove(int index) { try { // 使用 ListIterator 的查找方法 ListIterator<E> e = listIterator(index); E outCast = e.next(); e.remove(); return outCast; } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } } ... public Iterator<E> iterator() { return listIterator(); } // 子类需要实现此抽象方法 public abstract ListIterator<E> listIterator(int index); }
成员变量
// 当前容器所存储的元素数量 transient int size = 0; // 头指针指向元素第一个元素，当链表为空时，first 为空 transient Node<E> first; // 尾指针指向元素最后一个元素，当链表为空时，last 为空 transient Node<E> last;
LinkedList 底层基于双向链表实现，头节点和尾节点分别指向集合中的头尾元素，当元素为空的时候，它们也是空的（null）。
节点的类型结构是 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; } }
两种构造方法
public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
主要操作方法
新增 add
public boolean add(E e) { linkLast(e); // add 方法不出意外会一直返回 true return true; } void linkLast(E e) { final Node<E> l = last; // 创建节点，并将前序节点关联到 l final Node<E> newNode = new Node<>(l, e, null); // 将 last 指针指向最新创建的节点 last = newNode; if (l == null) // 第一次添加，将 first 指针也指向最新创建的节点 first = newNode; else // 将新创建的节点更新为原来尾节点的后序节点 l.next = newNode; // 更新容量 size++; // 更新修改次数 modCount++; }
上面这种新增是最简单的新增返回，直接在末尾插入元素，因为有 last 指向链表末尾，在末尾插入元素的花费是常数时间，只需简单的修改几个相关引用即可。
然而有些情况需要在中间进行插入操作，那么这种新增需要我们指定插入的位置，源码如下：
public void add(int index, E element) { // 下标检查 checkPositionIndex(index); if (index == size) // 目标位置就是最后位置，直接在尾部添加 linkLast(element); else // 需要在目标位置前插入 linkBefore(element, node(index)); } private void checkPositionIndex(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * @param e 新增节点的数据内容 * @param succ 目标位置的节点 */ 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++; }
首先会进行索引检查，指定 index后，需要在目标位置前插入节点。那么 index 一定满足index >= 0 && index <= size，当发现不满足条件后会抛出异常：IndexOutOfBoundsException。
下标检查无误后会检查目标位置是否是最后的位置，如果是最后的位置直接调用 linkLast 将新增的节点添加到最后。否则调用 linkBefore 方法在目标节点前插入添加。
新增全部 addAll
public boolean addAll(Collection<? extends E> c) { // 调用 addAll 的另外一种重载实现 return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c) { // 下标检查 checkPositionIndex(index); // 将目标集合转为数组 Object[] a = c.toArray(); // 需要新增元素的数量 int numNew = a.length; if (numNew == 0) return false; // 两个指针引用，pred 表示在此节点之后插入，succ 表示在此节点之前插入 Node<E> pred, succ; if (index == size) { // 在尾部添加，succ succ = null; pred = last; } else { // 找到 succ 节点，找到要插入的位置 succ = node(index); pred = succ.prev; } for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; // 从目标数组中不断创建节点并插入到 pred 后面 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 { // 将 succ 和最后一个新增的节点连接上 pred.next = succ; succ.prev = pred; } // 更新容量和修改次数 size += numNew; modCount++; return true; }
新增全部的时候因为效率原因并不是直接调用 add 方法，而且新增全部方法对于 modCount 只增加一次。
在头部新增 addFirst(E e)
public void addFirst(E e) { linkFirst(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++; }
头部新增节点对外暴露 addFirst 方法，处理时转交 linkFirst 方法处理。
因为 LinkedList 保留了头、尾节点的引用，所以可以很方便的定位到头部位置。找到头节点后创建新的节点，将新节点的前序设置 null，后序设置为原来的头节点，然后将 first 指针指向新创建的节点。
之后判断原来的头节点是不是为空，为空说明原来这个集合就是空的，这次新增时第一次新增，需要将 first 和 last 都指向新建的节点。如果原来的头节点不为空，那么更新它的前序引用为新创建的节点。最后更新集合大小和更新次数。
在尾部新增 addLast(E e)
public void addLast(E e) { linkLast(e); } 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++; }
尾部新增节点对外暴露 addLast 方法，处理时转交 linkLast 方法处理。
因为 LinkedList 保留了头、尾节点的引用，所以可以很方便的定位到尾部位置。找到尾节点后创建新的节点，将新节点的后序设置 null，前序设置为原来的尾节点，然后将 last 指针指向新创建的节点。
之后判断原来的尾节点是不是为空，为空说明原来这个集合就是空的，这次新增时第一次新增，需要将 first 和 last 都指向新建的节点。如果原来的尾节点不为空，那么更新它的后序引用为新创建的节点。最后更新集合大小和更新次数。
删除 remove(int index)
public E remove(int index) { // 下标检查 checkElementIndex(index); return unlink(node(index)); } /** * @param x 将要被删除的目标节点 */ 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; }
上面的删除是根据下标来进行删除，首先会对下标进行检查，无误后开始删除下标所对应的目标节点，调用 unlink 方法，删除后返回目标节点。
获取到目标节点的前序和后序，对前序和后序进行头尾判断，然后更改前序和后序节点的相关引用，并将目标节点的 prev、next、item 置空，此时目标节点和链表脱离关系，等待垃圾回收机制回收对象。
删除 remove(Object o)
public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
删除指定的对象，从集合中删除第一个匹配的对象（可为 null），匹配依据是调用对象的 equals 方法。删除节点和上面的删除一样，都是调用的 unlink 方法。删除成功后返回 true，没有找到对应的元素则返回 false。
清空元素 clear
为了让 GC 垃圾回收机制更快可以回收集合中的元素，需要将 node 之间的引用关系、node 本身的数据全部赋空。
public void clear() { 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++; }
修改元素 set(int index, E element)
public E set(int index, E element) { // 下标检查 checkElementIndex(index); // 找到目标节点 Node<E> x = node(index); // 获取原数据内容用于返回 E oldVal = x.item; // 修改数据域 x.item = element; return oldVal; }
修改其实核心还是调用 node方法 查找到目标节点，如果目标位置在前半部分就从前往后遍历，否则从后往前遍历查找。
找到后修改数据域，返回旧数据。
获取元素 get(int index)
LinkedList 底层基于链表结构，无法像 ArrayList 那样随机访问指定位置的元素。LinkedList 查找过程要稍麻烦一些，需要从链表头结点（或尾节点）向后查找，时间复杂度为 O(N)。
public E get(int index) { // 下标检查 checkElementIndex(index); return node(index).item; } 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; } }
获取元素时有一个小的注意点，因为 Linkedlist 不支持随机访问，查找的效率很低，所以在查找的方法中设计了一个小技巧，如果目标位置在前半部分就从前往后遍历，否则从后往前遍历查找。
获取头元素 getFirst
public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; }
如果头元素为空则会抛出 NoSuchElementException异常。否则直接返回成员变量 first 的 item 内容。
获取尾元素 getLast
public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }
如果尾元素为空则会抛出 NoSuchElementException异常。否则直接返回成员变量 last 的 item 内容。
迭代器
在用 for 遍历集合的时候是不可以对集合进行 remove 操作，因为 remove 操作会改变集合的大小。从而容易造成结果不准确甚至数组下标越界，更严重者还会抛出 ConcurrentModificationException。
public static void main(String[] args) { List<String> list = new LinkedList<>(); list.add("A"); list.add("B"); list.add("C"); list.add("D"); list.add("E"); list.add("F"); for (String i : list) { if ("C".equals(i)) { list.remove(i); } } }
通过控制台信息，看出异常出自 LinkedList 中的内部类 ListItr 中的 checkForComodification 方法。我们现在必须要去研究一下 LinkedList 的 ListItr 这个东西了。
public ListIterator<E> listIterator(int index) { // 下标检查 checkPositionIndex(index); return new ListItr(index); }
private class ListItr implements ListIterator<E> { // 上次返回的节点 private Node<E> lastReturned; // 将要被遍历的下一个节点 private Node<E> next; // 将要被遍历的下一个下标 private int nextIndex; // 期待修改次数，默认等于 modCount，如果不等则抛出异常 private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } public boolean hasPrevious() { return nextIndex > 0; } public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; } public int nextIndex() { return nextIndex; } public int previousIndex() { return 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 // 如果遍历到头了，next 就为 null，所以满足next == lastReturned nextIndex--; lastReturned = null; expectedModCount++; } public void set(E e) { if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
从源码可以看出，LinkedList 定义了一个内部类 ListItr 实现了 ListIterator 接口。在 ListItr 内部有四个成员变量：
- lastReturned：最后返回的节点（正在操作的节点）
- next：将要被遍历的下一个节点
- nextIndex：将要被遍历的下一个下标
- expectedModCount：代表对 LinkedList 修改次数的期望值，初始值为 modCount
LinkedList 既可以从头往后遍历，也可以从后往前遍历，所以对应提供了相关的判断方法 hasNext、hasPrevious，以及对应的移动方法 next、previous。
相比于 ArrayList 的迭代器，LinkedList 的迭代器提供了更丰富的操作方法，add、set、remove、nextIndex、previousIndex（前者只提供 remove）。
ListItr的构造函数需要接受一个下标 index，大多数情况 index 传入 0，表示从头开始遍历，如果 index 传入的是集合大小（表示从后往前遍历）。构造函数中会对 next 成员变量进行赋值，找到下一个将要遍历的节点，如果 index == size，此时 next 赋 null，否则 next 赋对应下标的节点，最后将 index 赋值给 nextIndex。
hasNext 和 hasPrevious 用来判断是否已经到了最后和最头：
- nextIndex < size：表示还没到最后
- nextIndex > 0：表示还没到最头
next 表示后移操作，将 next 赋给 lastReturned，然后使用 next = next.next 向后移动一个节点，然后将nextIndex加 1，最后返回遍历到的节点（提前赋值给了 lastReturned）的数据域。
previous 表示前移操作，从后往前移动，构造函数中需要传入集合的 size，那么在构造函数中 next 赋 null，nextIndex = size。在第一次执行 previous 方法的时候，会将 lastReturned 和 next 都指向集合的最后面 last，之后开始往前遍历。不断地调用 lastReturned = next = (next == null) ? last : next.prev;实现前移的效果。
每次调用 remove、add 和 set 方法之前一定要先执行 next 或 previous 方法，因为 lastReturned 默认是 null，并且每次都会将 lastReturned 重新赋 null。
使用迭代器来安全的删除元素：
public static void main(String[] args) { List<String> list = new LinkedList<>(); list.add("A"); list.add("B"); list.add("C"); list.add("D"); list.add("E"); list.add("F"); Iterator<String> iterator = list.iterator(); while (iterator.hasNext()) { String next = iterator.next(); if (next.equals("F")) { iterator.remove(); } } }
在 iterator.remove 方法中，调用了链表的 unlink 方法，里面会有 modCount++ 的操作，那么在迭代器 remove 方法中也存在 expectedModCount++ 的操作，所以最后两个数还是一样大的，不会抛出异常。
LinkedList 总结
LinkedList 底层基于双向链表实现，插入和删除的效率很高，只需要修改对应的引用即可，但是使用链表的代价就是不支持随机访问，查找的效率很低（虽然底层对于查找时判断索引是否小于一半来决定遍历的方向可以节省一部分开销）。LinkedList 对于容量而言没有限制。如果需要边遍历边 remove ，必须使用 iterator。且 remove 之前必须先 next，next 之后只能用一次 remove。
LinkedList 也是线程不同步的。如果多个线程同时访问同一个链表，并且至少有一个线程在结构上修改了链表，则必须从外部对修改操作进行线程同步。（结构修改是添加或删除一个或多个元素的任何操作；仅设置元素的值不是结构修改。）可以使用 Collections.synchronizedList 方法”包装” LinkedList。例如：
List list = Collections.synchronizedList(new LinkedList());
笔记大部分摘录自《Java核心技术卷I》，含有少数本人修改补充痕迹。
参考文章：http://gg.gg/12ia45
