LinkedList 接口源码解读（一）
前言
因为追求质量，所以写的较慢。大概在接下来的三天内会把LinkedList源码解析出完。大概还有两篇文章。废话不多说，正片开始！
大家都知道，LinkedList是在Java底层中是由 双向链表 实现的。那么今天我们就来阅读下源码，看看Java是如何实现这个功能强大的集合。
注意： JDK1.6 之前为双向循环链表，JDK1.7 取消了循环，只使用了双向链表。
首先，我们看一下LinkedList类定义
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable {// transient 关键字表示被该关键字修饰的属性不会被序列化。transient int size;transient Node<E> first;transient Node<E> last;private static final long serialVersionUID = 876323262645176354L;
}
一. 继承和实现关系
LinkedList 类继承了 AbstractSequentialList ，而AbstractSequentialList 又继承了 AbstractList 。
- 我们知道
ArrayList也继承了AbstractList，所以LinkedList中的大部分方法会和ArrayList相似。
LinkedList类实现了List、Deque 、Cloneable、Serializable 接口。
-
List： **表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。 ** -
Deque： 继承自Queue接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构。 -
Cloneable：Cloneable注解是一个标记接口，我们点进去会发现它并没有任何方法。此接口表明LinkedList具有拷贝能力，可以进行深拷贝或浅拷贝操作 。package java.lang;public interface Cloneable { } -
Serializable: 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。
二、属性实现
LinkedList 中的元素属性是通过 Node 类来声明的：
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;}
}
三、初始化
在进入正题之前，我先来给各位科普下 transient 关键字的作用是什么？
相信大家在阅读源码的过程中，很多属性的定义前都会加transient关键字。
transient是Java语言的关键字，用来表示一个成员变量不是该对象序列化的一部分。当一个对象被序列化的时候，transient所修饰的变量的值不包括在序列化的结果中。
transient int size; // 链表节点的个数，默认为 0
transient Node<E> first; // 指向链表的第一个节点
transient Node<E> last; // 指向链表的最后一个节点
private static final long serialVersionUID = 876323262645176354L;// 无参构造方法，调用此构造方法创建的集合长度默认为 0
public LinkedList() {this.size = 0;
}// 有参构造方法，传入一个集合类型作为参数，会创建一个与传入集合相同元素的链表对象
public LinkedList(Collection<? extends E> c) {this();this.addAll(c);
}
在调用有参构造方法时，LinkedList会调用两个方法this()、addAll()。
-
this()：调用有参构造的时候，首先会去调用无参构造，创建一个默认大小为 0 的集合。 -
addAll()：底层就是将传过来的集合类型转换成Object[]数组，然后依次遍历数组中的每个元素，添加到链表上。
源码：
// 将集合类型保存到链表中
public boolean addAll(Collection<? extends E> c) {// 底层调用了重载后的 addAll(int index, Collection<? extends E> c) return this.addAll(this.size, c); // 等同于 return this.addAll(0, c);
}
// addAll() 最终实现类
public boolean addAll(int index, Collection<? extends E> c) {// 索引越界检查，条件为：index >= 0 && index <= this.size// 满足条件返回true，否则报错this.checkPositionIndex(index);Object[] a = c.toArray(); // 转换成 Object[]int numNew = a.length;// 非空校验if (numNew == 0) {return false;} else {// 核心逻辑！！// pred 可以理解为记录节点位置的指针。每有一个新节点就会更新 pred 的值// succ 是一个标记节点，循环结束后会判断当前 succ 是否为 nullNode pred; Node succ;if (index == this.size) { // 调用有参构造方法时，size = 0 并且 index = 0，所以会进入下方的逻辑succ = null;pred = this.last; // 此时，链表为空，所以 last = null。可以转换成 pred = null} else {succ = this.node(index);pred = succ.prev;}Object[] var7 = a;int var8 = a.length;// 循环数组，依次往链表中添加元素for(int var9 = 0; var9 < var8; ++var9) {Object o = var7[var9]; // 取出指定索引的值E e = o;// LinkedList 底层是由双向链表实现的// 此语句的意思为：创建一个前缀指针指向 pred，值为 e，后缀指针指向 null 的新节点Node<E> newNode = new Node(pred, e, (Node)null);if (pred == null) { // 第一次循环时 pred 肯定为 null，进入下方逻辑// 表明当前 newNode 是链表的第一个节点// 设置 LinkedList 的 first 指针指向此新节点this.first = newNode; } else { // 除了第一次进入循环，后面的每次循环都会进下方逻辑// 依次往链表中添加元素 1 -> 2 -> 3pred.next = newNode;}// 更新 pred 的值pred = newNode;}if (succ == null) {// 此时的 pred 节点是当前链表的最后一个值// 设置 LinkedList 的 last 指针指向此循环结束后的最后一个 pred 节点this.last = pred; } else {pred.next = succ;succ.prev = pred;}// 无关操作 更新链表中的节点数// size 是链表所用来记录当前节点值的// modCount 是 List 集合存储元素个数的值// 因为 LinkedList 继承了 AbstractSequentialList，所以 List 的操作它也都有this.size += numNew;++this.modCount;return true;}}
四、插入元素
LinkedList 除了实现了 List 接口相关方法，还实现了 Deque 接口的很多方法，所以我们有很多种方式插入元素。
下面我将以 List 、Queue、Stack这三种数据结构分开带大家阅读源码。
可能会有朋友好奇，Stack是什么？Stack是栈这种数据结构，他的特点是只有一端能进出，这就导致栈的特点是先进后出，这和队列Queue的先进后出恰好相反
那朋友们又要好奇了，LinkedList在他的类方法定义上也没看到一个叫 Stack的接口啊，它怎么能当作栈呢？
大家要记住，数据结构底层都是相通的。栈有多种实现方式，可以通过单向链表实现栈、数组实现栈、双向链表实现栈，而 LinkedList正是通过双向链表来实现了对栈的操作
/*** 为了让大家能够明白上面那句话的意思，我用单向链表实现了一个栈，各位可以看看代码* @Description 单向链表实现栈* @Author Mr.Zhang* @Date 2024/8/2 14:40* @Version 1.0*/
public class LinkedListStack<E> implements Iterable<E> {// 容量private int capacity;private int size; // 栈中元素的个数// 头指针指向哨兵节点private Node<E> head = new Node<>(null, null);public LinkedListStack(int capacity) {this.capacity = capacity;}static class Node<E> {E value;Node<E> next;public Node(E value, Node<E> next) {this.value = value;this.next = next;}}/*** 向栈顶压入元素** @param value 待压入值* @return 压入成功返回 true，否则返回 false*/@Overridepublic boolean push(E value) {if (isFull()) {return false;}head.next = new Node<E>(value, head.next);size++;return true;}/*** 从栈顶弹出元素** @return 栈非空返回栈顶元素，栈为空返回 null*/@Overridepublic E pop() {if (isEmpty()) {return null;}E value = head.next.value;head.next = head.next.next;size--;return value;}/*** 返回栈顶元素，不弹出** @return 栈非空返回栈顶元素，栈为空返回 null*/@Overridepublic E peek() {if (isEmpty()) {return null;}return head.next.value;}/*** 检查栈是否为空** @return 空返回 true，否则返回 false*/@Overridepublic boolean isEmpty() {return head.next == null;}/*** 检查栈是否已满** @return 满了返回 true，否则返回 false*/@Overridepublic boolean isFull() {return capacity == size;}/*** 方便我用 增强for循环 测试*/@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {Node<E> p = head.next;@Overridepublic boolean hasNext() {return p != null;}@Overridepublic E next() {E value = p.value;p = p.next;return value;}};}
}Listadd(E e)： 用于在LinkedList的尾部插入元素，即将新元素作为链表的最后一个元素，时间复杂度为 O(1)。addAll(int index, Collection<? extends E> c)：用于通过给定的集合类型数据创建一个LinkedList。 (此源码已经在上面了，下方不重复解读)add(int index, E element)：用于在指定位置插入元素。这种插入方式需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。
源码：
// 在 LinkedList 尾部添加元素
public boolean add(E e) {this.linkLast(e);return true;
}// 向 LinkedList 尾部添加元素的底层实现方法
void linkLast(E e) {Node<E> l = this.last; // 获取最后一个节点// 根据传入的 e 创建新节点，新节点的前一个指针指向之前链表的最后一个节点Node<E> newNode = new Node(l, e, (Node)null); this.last = newNode; // 更新新节点的值if (l == null) { // 判断如果当前链表为空this.first = newNode; // 则将 LinkedList 的 last 指针也指向这个新节点} else {l.next = newNode; // 更新 l 的 next 指向的节点}// 无关操作 更新链表中的节点数++this.size;++this.modCount;
}// 根据指定的索引插入元素
public void add(int index, E element) {// 索引越界检查，条件为：index >= 0 && index <= this.size// 满足条件返回true，否则报错this.checkPositionIndex(index);if (index == this.size) { // 如果传递过来的 index 正好等于数组长度，则证明是向链表最后添加元素this.linkLast(element);} else {// 核心代码this.linkBefore(element, this.node(index)); // this.node(index)：找到待插入索引目前存在的节点元素}
}// 根据指定的索引插入元素的底层实现方法
void linkBefore(E e, Node<E> succ) {// 定义一个节点元素保存 succ 的 prev，也就是它的前一节点信息Node<E> pred = succ.prev;// 初始化节点，并指明前驱和后继节点Node<E> newNode = new Node<>(pred, e, succ);// 将 succ 节点前驱引用 prev 指向新节点succ.prev = newNode;// 判断前驱节点是否为空，为空表示 succ 是第一个节点if (pred == null) {this.first = newNode; // 当前 newNode 节点就是新的首节点，所以要让 first 指向 newNode} else {pred.next = newNode;}// 无关操作 更新链表中的节点数++this.size;++this.modCount;
}