通过JDK源码学习LinkedList常用方法通过JDK源码学习LinkedList常用方

对于 LinkedList ，我们先来看一下JDK中对LinkedList源码的一点解释：

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).

大致意思就是：LinkedList 是 List 和 Deque 的双链表实现，实现所有可选列表操作，并允许所有元素（包括null）。
链表 是数据结构中 线性结构 的一种。
再简单说一下Deque吧，它不是这篇文章的主角！

Deque 是 double ended queue 的简写，即“双端队列”。Deque是线性集合，支持两端插入和移除元素。大多数Deque实现对它们可能包含的元素数量没有固定限制，但是此接口支持容量限制的双锻链表以及没有固定大小限制的。此接口定义了访问双端队列两端元素的方法。提供了插入，移除和检查元素的方法。这些方法中的每一种都以两种形式存在：一种在操作失败时抛出异常，另一种返回特殊值（null或false，具体取决于操作）。后一种形式的插入操作专门设计用于容量限制的Deque实现；在大多数实现中，插入操作不会失败。

LinkedList 是非线程安全的，插入和删除速度快，但是随机访问的速度就比较慢了。为什么呢？接下来我们就从源码一探究竟吧！

以下源码基于 JDK 1.8.0_11。

首先来说一下 LinkedList 内部维护的 Node 节点私有静态内部类吧。看源码：

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; } }

增加对于添加功能来说，最常用的两个方法分别是 add(E e) 和 add(int index, E element)
(1). add(E e)：直接添加元素至链表尾部

public boolean add(E e) { // 直接插入链表尾部 linkLast(e); return true; }// linkLast(E element) 方法源码 void linkLast(E e) { final Node l = last; final Node newNode = new Node<>(l, e, null); // 默认新节点为链表的尾节点 last = newNode; // 如果原链表的尾节点为 null ，说明链表是空的，则新节点就是第一个节点 // 否则新节点就成了原尾节点的后继节点 if (l == null) first = newNode; else l.next = newNode; // 链表大小 + 1 size++; // modCount + 1 modCount++; }

(2). add(int index, E element)：添加元素 element 至链表指定索引 index 处

public void add(int index, E element) { // 该方法的主要作用是检查 index 是否在区间 [0,size] 内 (size是指链表的大小，初始值为0) checkPositionIndex(index); // 如果要插入的 index == size ，直接插入至链表尾部 // 否则插入到链表 index 位置处 if (index == size) linkLast(element); else linkBefore(element, node(index)); }// linkBefore(E e, Node succ) 方法源码 void linkBefore(E e, Node succ) { // 获取 succ 的前驱节点 final Node pred = succ.prev; final Node newNode = new Node<>(pred, e, succ); // succ 的前驱节点指向新节点 succ.prev = newNode; // 如果原链表 succ 节点的前驱节点为 null，则说明原链表是空链表 // 那么新节点就理所当然的应该是第一个节点了 // 否则，新节点即为原链表 succ 节点的前驱节点的后继节点 if (pred == null) first = newNode; else pred.next = newNode; // 链表大小 + 1 size++; // modCount + 1 modCount++; }

【通过JDK源码学习LinkedList常用方法】linkBefore(E e, Node succ) 方法分析：

文章图片
linkBefore.png 对于在链表中的添加操作，一般用到的就这两种，要么直接添加到链表尾部，要么添加到链表指定位置。根据自己的需求选择对应的方法使用即可。
删除对于删除功能来说，最常用的两个方法分别是 remove(int index) 和 remove(Object o)。
(1). remove(int index)：删除链表指定位置某元素

public E remove(int index) { // 该方法的主要作用是检查 index 是否在区间 [0,size) 内 checkElementIndex(index); // 如果上面的方法不会抛异常，就直接调用 unlink(node(index)); return unlink(node(index)); }// unlink(Node x) 方法：取消链接，即删除元素 E unlink(Node x) { // 获取 x 节点的相关属性 final E element = x.item; final Node next = x.next; final Node prev = x.prev; // 如果x的前驱为 null，说明x就是链表的第一个节点 // 要删除x节点，直接将x的后继节点变为链表的首节点即可 if (prev == null) { first = next; } else { // 否则，让 x 的前驱节点的后继节点赋值为 x 的后继节点，x 的前驱节点置为 null prev.next = next; x.prev = null; } // 如果 x 的后继为 null，说明 x 就是链表的尾节点 // 则直接将链表的尾节点赋值为 x 的前驱节点 if (next == null) { last = prev; } else { // 否则，让 x 的后继节点的前驱节点赋值为 x 的前驱节点，x 的后继节点置为 null next.prev = prev; x.next = null; } // 置空，等待GC回收 x.item = null; // 链表大小 - 1 size--; // modCount + 1 modCount++; // 返回被删除的元素 return element; }

unlink(Node x) 方法其实就是 linkBefore(E e, Node succ) 的逆向过程，这里就不画图分析了。
(2). remove(Object o)：删除链表中的某元素

public boolean remove(Object o) { // 因为链表允许 null 元素，所以这里需要判断待删除元素是否是 null 元素 if (o == null) { for (Node x = first; x != null; x = x.next) { // 找到为 null 的元素 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; }

修改修改链表中的元素使用的是 set(int index, E element) 方法，即修改指定 index 位置处的元素。

public E set(int index, E element) { // 该方法的主要作用是检查 index 是否在区间 [0,size) 内 checkElementIndex(index); // 获取指定 index 处的节点 x Node x = node(index); // 以下两步就完成了新值与旧值的替换工作 E oldVal = x.item; x.item = element; // 修改完后返回的是旧值 return oldVal; }

查询查询使用的是 get(int index) 方法，获取指定 index 位置处节点的 item 值。因为查找的时候要从头节点或者尾节点开始查找，所以当链表比较长的时候效率可能就不是很理想。

public E get(int index) { // 该方法的主要作用是检查 index 是否在区间 [0,size) 内 checkElementIndex(index); // 返回指定 index 处节点的 item 值 return node(index).item; }// node(int index) 方法源码 Node node(int index) { // 根据 size >> 1 即size右移一位的结果，判断是从链表的头节点查找还是从尾节点查找 // 有点类似折半查找的感觉 if (index < (size >> 1)) { Node x = first; // 从头节点开始向后遍历查找 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; } }

遍历为什么说使用迭代器遍历 list 的时候要避免使用类似 add、remove这种修改 list 结构的操作？原因就是如果在创建迭代器之后的任何时候对列表进行结构修改(因为修改list结构的时候modCount会自增)，迭代器将抛出并发修改异常ConcurrentModificationException。比如下面的代码就会抛出 ConcurrentModificationException

public class LinkedListTest { public static void main(String[] args) { List list = new LinkedList(); list.add("first"); list.add("a"); list.add("m"); list.add("p"); list.add(null); list.add("last"); Iterator iterator = list.iterator(); while (iterator.hasNext()){ Object next = iterator.next(); // 第二次循环的时候就会抛异常 list.remove("m"); System.out.println(next); } } }

来看一下调用这个异常的方法实现：

final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }

相关的源码比较多，就不贴出来了，简单说一下抛出这个异常的原因吧：
第一次调用 next() 方法的时候 expectedModCount 就已经被赋值了(expectedModCount = modCount; )，当下面的代码调用了 remove() 方法后，修改了 modCount 的值(modCount++; )，所以当第二次遍历进来的时候，调用 next() 方法，next() 方法再调用 checkForComodification() 方法时，就会检测到这两个值不相等，所以抛出异常。
关于 LinkedList 的常用方法就说这些吧，还有一些方法可能并没有提及，但是也不难，如果你肯努力，你一定会看懂的！请记住，千万不要假装自己很努力！