LinkedList接口源码解读

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

• List

  • add(E e) ： 用于在 LinkedList 的尾部插入元素，即将新元素作为链表的最后一个元素，时间复杂度为 O(1)。
  • addAll(int index, Collection<? extends E> c)：用于通过给定的集合类型数据创建一个LinkedList。 (此源码已经在上面了，下方不重复解读)
  • add(int index, E element)：用于在指定位置插入元素。这种插入方式需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。
  • addFirst(E e)： 用于在 LinkedList 的头部插入元素，即将新元素作为链表的第一个元素，时间复杂度为 O(1) 。底层调用LinkedFirst(E e)来插入元素。
  • addLast(E e)： 用于在 LinkedList 的尾部插入元素，即将新元素作为链表的最后一个元素，时间复杂度为 O(1)。 底层调用linkLast(E e)来插入元素。

源码：

// 在 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;
}// 向链表尾部添加元素
void linkLast(E e) {// 取出链表的尾指针指向的元素Node<E> l = this.last;// 根据给定的 e 创建新节点，此时新节点的前缀节点为原先尾指针指向的元素，后序节点为 nullNode<E> newNode = new Node(l, e, (Node)null);// 更改为尾指针指向的元素this.last = newNode;if (l == null) {  // 如果尾指针指向的元素为 null，则证明当前链表为空，此时新节点就是头节点。this.first = newNode;} else {l.next = newNode;  // 否则，将原来的尾指针的 next 指向新节点}// 无关操作  更新链表中的节点数++this.size;++this.modCount;
}

• Queue

  • offer(E e)：队列专用的方法。用于向队列尾部插入元素，即将新元素作为队列的最后一个元素。底层是调用链表的linkLast(E e)实现的插入操作。
  • offerFirst(E e)：队列专用的方法。用于向队列头部添加元素。底层是调用链表的linkFirst(E e)实现的插入操作。
  • offerLast(E e)：队列专用的方法。用于向队列尾部添加元素。底层是调用链表的linkLast(E e)实现的插入操作。

  总结： Queue队列在进行插入操作时，大部分情况下我们会直接使用offer(E e)方法，他们底层都是调用List接口定义的方法，只不过二次封装了。

• Stack

  • push(E e)：栈专用的方法。用于向栈顶压入元素。底层是调用链表的linkFirst(E e)实现的插入操作。

---

后记

在这篇 LinkedList 源码解读中我只带大家读完了插入操作。那么还有删除、修改操作，我希望大家可以自己去读读源码自己搞懂。只有自己亲自读过的源码才能真正的掌握。大家要是在读源码的过程中有什么方法没看懂可以随时在评论区评论或者私信我，我会帮助大家理解这个方法的底层到底是在做什么。这一定是你读过最全面，解析的最透彻的免费文章！希望满意的小伙伴可以评论区三连支持下~~。大家后续还有什么想看我分享的源码都可以和我说。