Java 中 LinkedList 的底层源码

        在 Java 的集合框架中，LinkedList是一个独特且常用的成员。它基于双向链表实现，与数组结构的集合类如ArrayList有着显著差异。深入探究LinkedList的底层源码，有助于我们更好地理解其工作原理和性能特点，以便在实际开发中做出更合适的选择。

        这里如何具体在idea里查看底层源码的教程在我ArrayList那篇文章有，基本大差不差，具体步骤我就不再演示了，我直接把所有底层源码总结下来供大家参考。

咱们可以根据这个代码逻辑自己推一下，捋清楚了思路就好理解多了。

一、基本结构与成员变量

LinkedList的底层核心是一个双向链表，其内部通过节点来存储数据。以下是LinkedList源码中关键的成员变量定义：

// 头节点
transient Node<E> first;
// 尾节点
transient Node<E> last;
// 元素数量
transient int size = 0;
// 底层双向链表节点的内部类
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;}
}

first和last分别指向双向链表的头节点和尾节点，通过它们可以方便地对链表进行遍历和操作。size变量用于记录链表中元素的个数。Node内部类则定义了链表节点的结构，每个节点不仅存储了元素值item，还持有指向前驱节点prev和后继节点next的引用，这使得双向链表能够灵活地在两个方向上进行遍历和元素的插入、删除等操作。

二、构造函数剖析

无参构造函数

public LinkedList() {
}

无参构造函数非常简洁，它只是创建了一个空的LinkedList对象。此时，first和last都为null，size为 0，链表中没有任何元素。

带集合参数的构造函数

public LinkedList(Collection<? extends E> c) {this();addAll(c);
}

该构造函数先调用无参构造函数创建一个空链表，然后通过addAll方法将传入集合中的所有元素添加到新创建的LinkedList中。这为我们在初始化LinkedList时提供了一种便捷的方式，可以直接将其他集合中的元素导入进来。

三、元素添加操作

在链表尾部添加元素

add(E e)方法用于在链表尾部添加一个元素，它是LinkedList中最常用的添加元素的方式之一。

public boolean add(E e) {linkLast(e);return true;
}
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;elsel.next = newNode;size++;modCount++;
}

add(E e)方法内部调用了linkLast方法。linkLast方法首先记录原链表的尾节点l，然后创建一个新的节点newNode，使其前驱指向原尾节点l，后继为null。接着更新last指向新节点，如果原尾节点为空，说明链表之前是空的，此时first也指向新节点；否则将原尾节点的后继指向新节点。最后，更新元素数量size和修改次数modCount。这个过程使得在链表尾部添加元素的操作非常高效，时间复杂度为 O (1)。

在指定位置插入元素

add(int index, E element)方法可以在链表的指定位置插入一个元素。

public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));
}

该方法首先调用checkPositionIndex方法检查索引是否越界（要求0 <= index <= size）。如果索引等于size，说明要在链表尾部插入元素，直接调用linkLast方法即可；否则，调用linkBefore方法在指定节点前插入元素。这里的node(index)方法用于获取指定索引位置的节点：

Node<E> node(int 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;}
}

node(index)方法通过判断索引与链表长度一半的大小关系，决定从链表头部还是尾部开始遍历查找指定索引位置的节点。如果索引小于链表长度的一半，从链表头部开始遍历；否则从链表尾部开始遍历。这种优化策略可以减少遍历的节点数量，提高查找效率。

四、元素删除操作

移除指定位置的元素

remove(int index)方法用于移除链表中指定位置的元素。

public E remove(int index) {checkElementIndex(index);return unlink(node(index));
}

该方法先调用checkElementIndex方法检查索引是否越界（要求0 <= index < size），然后通过node(index)方法获取指定索引位置的节点，最后调用unlink方法移除该节点并返回其存储的元素。

E unlink(Node<E> x) {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方法通过调整节点之间的引用关系，将指定节点从链表中移除。它先保存要移除节点的元素值、后继节点和前驱节点，然后根据前驱和后继节点的情况更新链表的头节点first或尾节点last，以及相关节点的前驱和后继引用。最后将被移除节点的元素值置为null，更新元素数量size和修改次数modCount，并返回被移除的元素。

移除指定元素的第一个匹配项

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和不为null的情况。找到匹配的元素后，调用unlink方法将其移除并返回true；如果遍历完链表都没有找到匹配元素，则返回false。

五、元素查找操作

查找指定元素首次出现的索引

indexOf(Object o)方法用于返回指定元素在链表中首次出现的索引，如果不存在则返回 -1。

public int indexOf(Object o) {int index = 0;if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}return -1;
}

该方法从链表头部开始遍历，分别处理查找元素为null和不为null的情况，找到匹配元素时返回其索引，遍历完链表都未找到则返回 -1。

查找指定元素最后一次出现的索引

lastIndexOf(Object o)方法用于返回指定元素在链表中最后一次出现的索引，如果不存在则返回 -1。

public int lastIndexOf(Object o) {int index = size;if (o == null) {for (Node<E> x = last; x != null; x = x.prev) {index--;if (x.item == null)return index;}} else {for (Node<E> x = last; x != null; x = x.prev) {index--;if (o.equals(x.item))return index;}}return -1;
}

该方法从链表尾部开始遍历，分别处理查找元素为null和不为null的情况，找到匹配元素时返回其索引，遍历完链表都未找到则返回 -1。

通过对LinkedList底层源码的剖析，我们清楚地了解了它的结构和各种操作的实现原理。LinkedList在插入和删除元素时具有高效性，尤其是在链表中间位置进行操作时，不需要像ArrayList那样进行大量元素的移动。然而，由于其基于链表结构，随机访问元素的时间复杂度较高，需要遍历链表来查找指定位置的元素。因此，在实际开发中，我们应根据具体的需求和操作场景，合理选择使用LinkedList或其他集合类，以达到最佳的性能和功能实现。