LinkedList 的整体架构

当链表为空时，first 和 last 都为 null

  1. public class LinkedList<E> extends AbstractSequentialList<E>
  2.     implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
  4.     transient int size = 0;
  6.     /**
  7.      * 指向第一个节点的指针
  8.      * 不变量：(first == null && last == null) ||
  9.      *            (first.prev == null && first.item != null)
  10.      */
  11.     transient Node<E> first;
  13.     /**
  14.      * 指向最后一个节点的指针
  15.      * 不变量: (first == null && last == null) ||
  16.      *            (last.next == null && last.item != null)
  17.      */
  18.     transient Node<E> last;
  20.     // 构造一个空 list
  21.     public LinkedList() {
  22.     }
  24.     public LinkedList(Collection<? extends E> c) {
  25.         this();
  26.         addAll(c);
  27.     }
  29.     private static class Node<E> {
  30.         // 节点值
  31.         E item;
  32.         // 指向的下一个节点
  33.         Node<E> next;
  34.         // 指向的前一个节点
  35.         Node<E> prev;
  37.         Node(Node<E> prev, E element, Node<E> next) {
  38.             this.item = element;
  39.             this.next = next;
  40.             this.prev = prev;
  41.         }
  42.     }
  43. }

LinkedList 的节点新增

LinkedList 追加节点时，可以追加到链表头部，也可以追加到链表尾部。
add() 默认是从尾部追加，addFirst() 是从头部追加。
新增第一个节点后，first 和 last 同时指向这个新节点，新节点 的 prev 和 next 都为 null

add() 的底层源码实现如下：

  1. public boolean add(E e) {
  2.     linkLast(e);
  3.     return true;
  4. }
  6. public void addLast(E e) {
  7.     linkLast(e);
  8. }
  10. // 将 e 构成新节点，追加到尾部
  11. void linkLast(E e) {
  12.     // 将旧尾节点暂存
  13.     final Node<E> l = last;
  14.     // 构建新节点
  15.     final Node<E> newNode = new Node<>(l, e, null);
  16.     // 新节点作为头节点
  17.     last = newNode;
  18.     // 如果链表为空（l 是旧尾节点，尾节点为空，链表即空），头部和尾部是同一个节点，都是新节点
  19.     if (l == null)
  20.         first = newNode;
  21.     // 否则（链表不为空）把旧尾节点的下一个节点，指向当前尾节点
  22.     else
  23.         l.next = newNode;
  24.     // 长度和结构修改次数都 + 1
  25.     size++;
  26.     modCount++;
  27. }

addFirst() 的底层源码实现如下：

  1. public void addFirst(E e) {
  2.     linkFirst(e);
  3. }
  5. // 将 e 构成新节点，追加到头部
  6. private void linkFirst(E e) {
  7.     // 将旧头节点暂存
  8.     final Node<E> f = first;
  9.     // 构建新节点
  10.     final Node<E> newNode = new Node<>(null, e, f);
  11.     // 新节点作为头结点
  12.     first = newNode;
  13.     // 如果链表为空（f 是旧头节点，头节点为空，链表即空），头部和尾部是同一个节点，都是新节点
  14.     if (f == null)
  15.         last = newNode;
  16.     // 否则（链表不为空）把旧头节点的上一个节点，指向当前头节点
  17.     else
  18.         f.prev = newNode;
  19.     // 长度和结构修改次数都 + 1
  20.     size++;
  21.     modCount++;
  22. }

LinkedList 的节点删除

节点删除的方式和追加类似，可以选择从头部删除，也可以选择从尾部删除。
remove() 默认是从头部移除，removeLast() 是从尾部移除。
删除操作会把节点的值，前后指向节点都置为 null，让 GC 进行回收。
LinkedList 在删除元素时，推荐通过迭代器进行删除。

remove() 的底层源码实现如下：

  1. public E remove() {
  2.     return removeFirst();
  3. }
  5. // 移除并返回链表中的第一个元素
  6. public E removeFirst() {
  7.     final Node<E> f = first;
  8.     if (f == null)
  9.         throw new NoSuchElementException();
  10.     return unlinkFirst(f);
  11. }
  13. // 断开非空的第一个节点 f
  14. private E unlinkFirst(Node<E> f) {
  15.     // assert f == first && f != null;
  16.     // 暂存头节点的值，作为方法的返回值
  17.     final E element = f.item;
  18.     // 暂存头节点的下一个节点，它将作为新的头结点
  19.     final Node<E> next = f.next;
  20.     // 帮助 GC 回收头节点
  21.     f.item = null;
  22.     f.next = null; // help GC
  23.     // 更新头节点
  24.     first = next;
  25.     // 如果 next 为空，表明链表为空
  26.     if (next == null)
  27.         last = null;
  28.     // 链表不为空，新头节点的 prev 指向 null
  29.     else
  30.         next.prev = null;
  31.     // 链表的长度 -1 ，结构修改次数 + 1
  32.     size--;
  33.     modCount++;
  34.     return element;
  35. }

removeLast() 的底层源码实现如下：

  1. public E removeLast() {
  2.     final Node<E> l = last;
  3.     if (l == null)
  4.         throw new NoSuchElementException();
  5.     return unlinkLast(l);
  6. }
  8. // 移除并返回链表中的最后一个元素
  9. private E unlinkLast(Node<E> l) {
  10.     // assert l == last && l != null;
  11.     // 暂存尾节点的值，作为方法的返回值
  12.     final E element = l.item;
  13.     // 暂存尾节点的前一个节点，它将作为新的尾结点
  14.     final Node<E> prev = l.prev;
  15.     // 帮助 GC 回收头节点
  16.     l.item = null;
  17.     l.prev = null; // help GC
  18.     // 更新尾节点
  19.     last = prev;
  20.     // 如果 prev 为空，表明链表为空
  21.     if (prev == null)
  22.         first = null;
  23.     // 链表不为空，新尾节点的 next 指向 null
  24.     else
  25.         prev.next = null;
  26.     // 链表的长度 -1 ，结构修改次数 + 1
  27.     size--;
  28.     modCount++;
  29.     return element;
  30. }

LinkedList 的节点修改

LinkedList 的节点查询

  1. public E get(int index) {
  2.     checkElementIndex(index);
  3.     return node(index).item;
  4. }
  6. // 返回指定元素索引处的(非空) Node
  7. Node<E> node(int index) {
  8.     // assert isElementIndex(index);
  9.     // 如果 index 处于队列的前半部分，从头开始找
  10.     if (index < (size >> 1)) {
  11.         Node<E> x = first;
  12.         for (int i = 0; i < index; i++)
  13.             x = x.next;
  14.         return x;
  15.     // 如果 index 处于队列的后半部分，从尾开始找
  16.     } else {
  17.         Node<E> x = last;
  18.         for (int i = size - 1; i > index; i--)
  19.             x = x.prev;
  20.         return x;
  21.     }
  22. }

从源码中我们可以发现，LinkedList 并没有采用从头循环到尾的做法，而是采取了简单二分法，首先看看 index 是在链表的前半部分，还是后半部分。如果是前半部分，就从头开始寻找，反之亦然。
通过这种方式，使循环的次数至少降低了一半，提高了查找的性能，这种思想值得我们借鉴。

LinkedList 的迭代器

因为 LinkedList 要实现双向的迭代访问，所以使用 Iterator 接口肯定不行了。
Java 新增了一个 ListIterator 迭代接口，这个接口提供了向前和向后的迭代方法，如下所示：

迭代顺序 方法
从尾到头迭代方法 hasPrevious、previous、previousIndex
从头到尾迭代方法 hasNext、next、nextIndex

ArrayList

  1. // 双向迭代器
  2. private class ListItr implements ListIterator<E> {
  3.     // 返回的最后一个节点
  4.     private Node<E> lastReturned;
  5.     // 下一个要返回的节点
  6.     private Node<E> next;
  7.     // 下一个要返回的节点的索引
  8.     private int nextIndex;
  9.     // expectedModCount：迭代过程中期望版本号；modCount：目前最新版本号
  10.     private int expectedModCount = modCount;
  12.     // index 为迭代的起始索引位置
  13.     ListItr(int index) {
  14.         // assert isPositionIndex(index); 该方法 return index >= 0 && index <= size;
  15.         next = (index == size) ? null : node(index);
  16.         nextIndex = index;
  17.     }
  19.     public boolean hasNext() {
  20.         // 下一个要返回的节点的索引 < 链表的长度，表示存在下一个节点可以迭代
  21.         return nextIndex < size;
  22.     }
  24.     public E next() {
  25.         // 迭代过程中，判断版本号有无被修改，有被修改，抛 ConcurrentModificationException
  26.         checkForComodification();
  27.         // 再次检查
  28.         if (!hasNext())
  29.             throw new NoSuchElementException();
  31.         lastReturned = next;
  32.         next = next.next;
  33.         nextIndex++;
  34.         return lastReturned.item;
  35.     }
  37.     public boolean hasPrevious() {
  38.         return nextIndex > 0;
  39.     }
  41.     public E previous() {
  42.         // 迭代过程中，判断版本号有无被修改，有被修改，抛 ConcurrentModificationException
  43.         checkForComodification();
  44.         // 再次检查
  45.         if (!hasPrevious())
  46.             throw new NoSuchElementException();
  47.         // next 为空场景 ListItr 类的构造器入参 index = size
  48.         // next 不为空场景：说明已经发生过迭代了，直接取前一个节点即可(next.prev)
  49.         lastReturned = next = (next == null) ? last : next.prev;
  50.         nextIndex--;
  51.         return lastReturned.item;
  52.     }
  54.     public void remove() {
  55.         checkForComodification();
  56.         // lastReturned 是本次迭代需要删除的值，分以下空和非空两种情况：
  57.         // lastReturned 为空，说明调用者没有主动执行过 next() 或者 previos()，直接报错
  58.         // lastReturned 不为空，是在上次执行 next() 或者 previos()方法时赋的值
  59.         if (lastReturned == null)
  60.             throw new IllegalStateException();
  62.         Node<E> lastNext = lastReturned.next;
  63.         // 断开当前节点
  64.         unlink(lastReturned);
  65.         // previous() 里面可能设置 lastReturned = next
  66.         if (next == lastReturned)
  67.             next = lastNext;
  68.         else
  69.             nextIndex--;
  70.         lastReturned = null;
  71.         expectedModCount++;
  72.     }
  74.     public void set(E e) {
  75.         if (lastReturned == null)
  76.             throw new IllegalStateException();
  77.         checkForComodification();
  78.         lastReturned.item = e;
  79.     }
  81.     public void add(E e) {
  82.         checkForComodification();
  83.         lastReturned = null;
  84.         if (next == null)
  85.             linkLast(e);
  86.         else
  87.             linkBefore(e, next);
  88.         nextIndex++;
  89.         expectedModCount++;
  90.     }
  91. }

LinkedList 作为队列

LinkedList 同时实现了 Queue 接口，在新增、删除、查询等方面增加了很多新的方法，这些方法容易混淆，在链表为空的情况下，返回值也不太一样：

方法含义 返回异常 返回特殊值 底层实现
新增 add(e) offer(e) offer() 底层是只调用 add()
删除 remove() poll(e) 链表为空时，remove 会抛出异常，poll 返回 null
查找 element() peek() 链表为空时，element 会抛出异常，peek 返回 null

Queue 接口注释建议 add 方法操作失败时抛出异常，但 LinkedList 实现的 add 方法一直返回 true。

Deque 接口 继承 Queue 接口
public interface Deque<E> extends Queue<E> {}
LinkedList 也实现了 Deque 接口，对新增、删除和查找都提供从头开始，还是从尾开始两种方向的方法，比如 remove 方法，Deque 提供了 removeFirst 和 removeLast 两种方向的使用方式，但当链表为空时的表现都和 remove 方法一样，都会抛出异常。

LinkedList 的常见问题

说一下你对 LinkedList 的了解

底层数据结构
LinkedList 的底层数据结构是一个双向链表，add 的元素被存储在双向链表的每一个节点中，每一个节点由：该节点的前一个节点、该节点的值、该节点的后一个节点这三部分组成。

特点
双向链表中头节点的前一个节点是 null，尾节点的后一个节点是 null。
当链表为空时，头节点 和 尾节点都为 null。

描述双向链表结构

图片.png
双向链表中，双向的意思是说前后节点之间互相有引用，链表的节点称为 Node。
Node 有三个属性组成：其前一个节点，本身节点的值，其下一个节点。
假设 A、B 节点相邻，A 节点的下一个节点就是 B，B 节点的上一个节点就是 A，两者互相引用。
在链表的头部节点，称为头节点。头节点的前一个节点是 null。
在链表的尾部节点，称为尾节点，尾节点的后一个节点是 null。
当链表为空时，first 和 last 都为 null。

描述双向链表的新增 & 删除

新增：可以从链表头新增，也可以从链表尾新增，如果是从链表尾新增的话，直接把当前节点追加到尾节点之后，本身节点自动变为尾节点。
删除：把要删除节点的后一个节点的 prev 指向其前一个节点，把删除节点的前一个节点的 next 指向其后一个节点，最后把要删除的节点置为 null 即可。