python做的网站如何打开,网站开发蓝云,珠海购物网站制作,网络营销ppt课件LinkedList 接口源码解读
前言
因为追求质量#xff0c;所以写的较慢。大概在接下来的三天内会把LinkedList源码解析出完。已经出完啦#xff01;废话不多说#xff0c;正片开始#xff01; #xff08;文章最后面有后记哦~#xff09;
大家都知道#xff0c;LinkedL…LinkedList 接口源码解读
前言
因为追求质量所以写的较慢。大概在接下来的三天内会把LinkedList源码解析出完。已经出完啦废话不多说正片开始 文章最后面有后记哦~
大家都知道LinkedList是在Java底层中是由 双向链表 实现的。那么今天我们就来阅读下源码看看Java是如何实现这个功能强大的集合。
注意 JDK1.6 之前为双向循环链表JDK1.7 取消了循环只使用了双向链表。 首先我们看一下LinkedList类定义
public class LinkedListE extends AbstractSequentialListE implements ListE, DequeE, Cloneable, Serializable {// transient 关键字表示被该关键字修饰的属性不会被序列化。transient int size;transient NodeE first;transient NodeE 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 NodeE {E item; // 元素值NodeE next; // 指向下一个节点的指针NodeE prev; // 指向上一个节点的指针// 构造方法中初始化参数顺序分别是前驱结点、本身节点值、后继节点Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}
}三、初始化
在进入正题之前我先来给各位科普下 transient 关键字的作用是什么
相信大家在阅读源码的过程中很多属性的定义前都会加transient关键字。
transient是Java语言的关键字用来表示一个成员变量不是该对象序列化的一部分。当一个对象被序列化的时候transient所修饰的变量的值不包括在序列化的结果中。
transient int size; // 链表节点的个数默认为 0
transient NodeE first; // 指向链表的第一个节点
transient NodeE 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 的新节点NodeE 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 LinkedListStackE implements IterableE {// 容量private int capacity;private int size; // 栈中元素的个数// 头指针指向哨兵节点private NodeE head new Node(null, null);public LinkedListStack(int capacity) {this.capacity capacity;}static class NodeE {E value;NodeE next;public Node(E value, NodeE next) {this.value value;this.next next;}}/*** 向栈顶压入元素** param value 待压入值* return 压入成功返回 true否则返回 false*/Overridepublic boolean push(E value) {if (isFull()) {return false;}head.next new NodeE(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 IteratorE iterator() {return new IteratorE() {NodeE 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) {NodeE l this.last; // 获取最后一个节点// 根据传入的 e 创建新节点新节点的前一个指针指向之前链表的最后一个节点NodeE 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, NodeE succ) {// 定义一个节点元素保存 succ 的 prev也就是它的前一节点信息NodeE pred succ.prev;// 初始化节点并指明前驱和后继节点NodeE 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) {// 取出链表的尾指针指向的元素NodeE l this.last;// 根据给定的 e 创建新节点此时新节点的前缀节点为原先尾指针指向的元素后序节点为 nullNodeE 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 源码解读中我只带大家读完了插入操作。那么还有删除、修改操作我希望大家可以自己去读读源码自己搞懂。只有自己亲自读过的源码才能真正的掌握。大家要是在读源码的过程中有什么方法没看懂可以随时在评论区评论或者私信我我会帮助大家理解这个方法的底层到底是在做什么。这一定是你读过最全面解析的最透彻的免费文章希望满意的小伙伴可以评论区三连支持下~~。大家后续还有什么想看我分享的源码都可以和我说。
