本文共 6312 字，大约阅读时间需要 21 分钟。
文章目录
概述
LinkedList是Java集合框架中一个重要的实现，其底层采用的双向链表结构。和ArrayList一样，LinkedList也支持空值和重复值。由于LinkedList基于链表实现，存储元素过程中，无需像ArrayList那样进行扩容。但有得必有失，LinkedList 存储元素的节点需要额外的空间存储前驱和后继的引用。另一方面，LinkedList在链表头部和尾部插入效率比较高，但在指定位置进行插入时，效率一般。 原因是，在指定位置插入需要定位到该位置处的节点，此操作的时间复杂度为O(N)。最后，LinkedList是非线程安全的集合类，并发环境下，多个线程同时操作LinkedList，会引发不可预知的错误。
继承体系
LinkedList的继承体系图如下：
LinkedList继承自AbstractSequentialList，AbstractSequentialList 提供了一套基于顺序访问的接口。通过继承此类，子类仅需实现部分代码即可拥有完整的一套访问某种序列表（比如链表）的接口。深入源码，AbstractSequentialList提供的方法基本上都是通过ListIterator实现的，比如：
public E get(int index) { try { return listIterator(index).next(); } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); }}public void add(int index, E element) { try { listIterator(index).add(element); } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); }}// 留给子类实现public abstract ListIterator listIterator(int index); 所以只要继承类实现了listIterator方法，它不需要再额外实现什么即可使用。LinkedList和其父类一样，也是基于顺序访问。所以LinkedList继承了AbstractSequentialList，但LinkedList并没有直接使用父类的方法，而是重新实现了一套的方法。
另外，LinkedList 还实现了Deque (double ended queue)，Deque又继承自Queue接口。这样LinkedList就具备了队列的功能。
Queuequeue = new LinkedList<>();
源码分析
双向链表
LinkedList是一个双向链表结构，每一个节点有两个指针next和prev。
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
查找
LinkedList底层基于链表结构，无法像ArrayList那样随机访问指定位置的元素。LinkedList查找过程要稍麻烦一些，需要从链表头结点（或尾节点）向后查找，时间复杂度为O(N)。相关源码如下：
public E get(int index) { // 检查index是否小于size checkElementIndex(index); return node(index).item;}Node node(int index) { /* * 查找位置 index 如果小于节点数量的一半， * 则从头节点开始查找，否则从尾节点查找 */ if (index < (size >> 1)) { Node x = first; // 循环向后查找，直至 i == index for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; }} 通过遍历的方式定位目标位置的节点。获取到节点后，取出节点存储的值返回即可。这里面有个小优化，即通过比较index与节点数量size/2的大小，决定从头结点还是尾节点进行查找。
遍历
通常情况下，我们会使用foreach遍历LinkedList，而foreach最终转换成迭代器形式。所以分析LinkedList的遍历的核心就是它的迭代器实现，相关代码如下：
public ListIteratorlistIterator(int index) { checkPositionIndex(index); return new ListItr(index);}private class ListItr implements ListIterator { private Node lastReturned; private Node next; private int nextIndex; private int expectedModCount = modCount; /** 构造方法将 next 引用指向指定位置的节点 */ 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; // 调用 next 方法后，next 引用都会指向他的后继节点 nextIndex++; return lastReturned.item; } // 省略部分方法}
LinkedList不擅长随机位置访问，如果用随机访问的方式遍历LinkedList，效率会很差，如下面代码：
Listlist = new LinkedList<>();list.add(1)list.add(2)......for (int i = 0; i < list.size(); i++) { Integet item = list.get(i); // do something}
时间复杂度达到O(N^2)
插入
LinkedList除了实现了List接口相关方法，还实现了Deque接口的很多方法，所以有很多种方式插入元素。LinkedList插入元素的过程实际上就是链表链入节点的过程。
/** 在链表尾部插入元素 */public boolean add(E e) { linkLast(e); return true;}/** 在链表指定位置插入元素 */public void add(int index, E element) { checkPositionIndex(index); // 判断 index 是不是链表尾部位置，如果是，直接将元素节点插入链表尾部即可 if (index == size) linkLast(element); else linkBefore(element, node(index));}/** 将元素节点插入到链表尾部 */void linkLast(E e) { final Node l = last; // 创建节点，并指定节点前驱为链表尾节点 last，后继引用为空 final Node newNode = new Node<>(l, e, null); // 将 last 引用指向新节点 last = newNode; // 判断尾节点是否为空，为空表示当前链表还没有节点 if (l == null) first = newNode; else l.next = newNode; // 让原尾节点后继引用 next 指向新的尾节点 size++; modCount++;}/** 将元素节点插入到 succ 之前的位置 */void linkBefore(E e, Node succ) { // assert succ != null; final Node pred = succ.prev; // 1. 初始化节点，并指明前驱和后继节点 final Node newNode = new Node<>(pred, e, succ); // 2. 将 succ 节点前驱引用 prev 指向新节点 succ.prev = newNode; // 判断尾节点是否为空，为空表示当前链表还没有节点 if (pred == null) first = newNode; else pred.next = newNode; // 3. succ 节点前驱的后继引用指向新节点 size++; modCount++;} linkBefore图解：
删除
删除操作通过解除待删除节点与前后节点的链接，即可完成任务。
public boolean remove(Object o) { if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { // 遍历链表，找到要删除的节点 for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); // 将节点从链表中移除 return true; } } } return false;}public E remove(int index) { checkElementIndex(index); // 通过 node 方法定位节点，并调用 unlink 将节点从链表中移除 return unlink(node(index));}/** 将某个节点从链表中移除 */E unlink(Node x) { // assert x != null; final E element = x.item; final Node next = x.next; final Node prev = x.prev; // prev 为空，表明删除的是头节点 if (prev == null) { first = next; } else { // 将 x 的前驱的后继指向 x 的后继 prev.next = next; // 将 x 的前驱引用置空，断开与前驱的链接 x.prev = null; } // next 为空，表明删除的是尾节点 if (next == null) { last = prev; } else { // 将 x 的后继的前驱指向 x 的前驱 next.prev = prev; // 将 x 的后继引用置空，断开与后继的链接 x.next = null; } // 将 item 置空，方便 GC 回收 x.item = null; size--; modCount++; return element;} 删除节点图解：
注：LinkedList 还可以用作栈、队列和双向队列。
转载地址：http://qxgmi.baihongyu.com/