不得不看的LinkedList源码分析

之前分析了一下ArrayList的源码，这篇文章继续分析LinkedList，LinkedList同样是我们平时工作中最常用的集合之一。

LinkedList都有哪些特点

LinkedList的底层是通过双向链表实现的LinkedList逻辑上是连续的（因为LinkedList开辟的内存不是连续的），是通过存放上一个节点的引用和下一个节点的引用来实现有序的链表相对于ArrayList来说，LinkedList查询元素的速度较慢，新增和删除元素的速度较快；但是在指定位置新增元素效率较慢，时间复杂度为O(N)LinkedList同样也是支持泛型的LinkedList同样也是非线程安全的，在多线程的环境下可能会引发未知的错误LinkedList没有像ArrayList那样的扩容机制LinkedList还实现了Deque，因此具备队列的特点推荐使用迭代器遍历

查找元素

public E get(int index) { // 首先检查 checkElementIndex(index); return node(index).item; } Node<E> node(int index) { // 如果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的查找方法不会像ArrayList那样简单，LinkedList使用过遍历查找，所以时间复杂度为O(n)。但是这里有一个小小的优化点，如果查找元素的索引下标小于二分之一的链表长度，则从头节点开始查找，反之从尾节点开始查找。

插入元素

LinkedList插入数据的方法同样有两种，分为在链表尾部插入和在指定位置插入元素。

在链表尾部插入元素 public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node<E> l = last; // 创建一个新的节点，指定新节点的头引用为链表的last，尾引用为空 final Node<E> newNode = new Node<>(l, e, null); // 将last引用指向新的节点 last = newNode; // 判断尾节点是否为空，为空表示当前链表没有节点 if (l == null) first = newNode; else // 让原尾节点后继引用 next 指向新的尾节点 l.next = newNode; size++; modCount++; } 在指定位置插入元素 public void add(int index, E element) { checkPositionIndex(index); // 判断是不是链表的尾部，如果是尾部，则直接在尾部插入即可 if (index == size) linkLast(element); else // 否则就在指定位置插入 linkBefore(element, node(index)); } void linkBefore(E e, Node<E> succ) { final Node<E> pred = succ.prev; // 创建新的节点，并指明头引用和尾引用节点 final Node<E> newNode = new Node<>(pred, e, succ); // 将 succ 节点头引用 prev 指向新节点 succ.prev = newNode; // 判断尾节点是否为空，为空表示当前链表还没有节点 if (pred == null) first = newNode; else // succ 节点前驱的尾引用指向新节点 pred.next = newNode; size++; modCount++; }

上面是插入过程的源码，我对源码进行了比较详细的注释，应该不难看懂。上面两个 add 方法只是对操作链表的方法做了一层包装，核心逻辑在 linkBefore 和 linkLast 中。LinkedList 除了实现了 List 接口相关方法，还实现了 Deque 接口的很多方法，所以我们有很多种方式插入元素。我这里分析 List 接口中相关的插入方法，其他的方法感兴趣的小伙伴自己可以去阅读一下源码。

删除元素

如果可以看懂上面的插入源码分析，那么再看删除操作实际上也很简单了。删除操作同样分为两种，删除指定元素和删除指定位置上的元素。

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; } public E remove(int index) { checkElementIndex(index); // 通过 node 方法定位节点，并调用 unlink 将节点从链表中移除 return unlink(node(index)); } /** 将某个节点从链表中移除 */ 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; // 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 的遍历还是需要注意一些，不然可能会导致代码效率低下，LinkedList的遍历是同通过迭代器实现的，所以推荐使用迭代器遍历LinkedList，相关代码如下：

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

for (int i = 0; i < items.size(); i++) { System.out.println(items.get(i)); }

总结

以上内容通过对LinkedList的查找、遍历、添加和删除元素等常用API结合源码做了解读，看起来也不难。LinkedList同样也是最常用的集合之一，也是高频面试题，通过本文可以对LinkedList有一个更全面、深刻的理解。