网上商城网站建设公司,wordpress 取消标志,黄埔营销型网站建设,wordpress手机版弹出式导航目录
一、前言
二、LinkedList类简介
三、LinkedList类的底层实现
四、LinkedList类的源码解读 1.add方法解读 : 〇准备工作 。 ①跳入无参构造。 ②跳入add方法。 ③跳入linkList方法。 ④增加第一个元素成功。 ⑤向链表中添加第二个元素。 2.remove方法解读 : 〇准备工…目录
一、前言
二、LinkedList类简介
三、LinkedList类的底层实现
四、LinkedList类的源码解读 1.add方法解读 : 〇准备工作 。 ①跳入无参构造。 ②跳入add方法。 ③跳入linkList方法。 ④增加第一个元素成功。 ⑤向链表中添加第二个元素。 2.remove方法解读 : 〇准备工作 。 ①关于LinkedList类的remove方法。 ②跳入remove() 方法。 ③跳入removeFirst() 方法。 ④跳入unlinkFirst() 方法。 ⑤第一个元素被除去。
五、总结 一、前言 大家好今天给大家带来的是LinkedList类的内容分享。对于单列集合List的三个最常用的实现类——ArrayList, Vector, LinkedList在前面的小节中我们已经分析过了ArrayList类和Vector类的源码。但对于List接口的第三大实现类LinkedList由于其底层涉及了较多数据结构的知识而本篇博文属于《java基础》专栏因此主要面向基础阶段因此up准备简单给大家过一下就好不会讲太深大家可放心食用更多内容up准备在将来的数据结构专栏再深度讲解。 注意 : ① 代码中的注释也很重要 ② 不要眼高手低自己跟着过一遍才能知道怎么用。 ③ 点击侧边栏目录或者文章开头的目录可以跳转。良工不示人以朴所有文章都会适时改进。大家如果有什么问题都可以在评论区一块儿交流或者私信up。 感谢阅读 二、LinkedList类简介 1.LinkedList是一种常见的线性表每一个结点中都存放了下一个结点的地址。LinkedList类属于java.base模块java.util包下如下图所示 : 我们再来看看LinkedList 类的类图如下所示 : 2.链表又分为单向链表和双向链表。一个单向链表包含两个值——当前结点的值和下一个结点的地址值一个双向链表包含三个值——前一个结点的地址值当前结点的值和下一个结点的地址值。 3.LinkedList底层实现了双向链表和双端队列的特点。 4.同ArrayList类似可以向LinkedList集合中添加任意元素包括null并且元素可以重复。 5.同ArrayList一样LinkedList也没有实现线程同步因此线程不安全。 三、LinkedList类的底层实现 1.LinkedList的底层维护了一个双向链表。在IDEA的类图中我们查看LinkedList类的字段可以发现LinkedList类中维护了两个属性first和last见名知意它们分别指向双向链表的首结点和尾结点。 2.每个节点Node对象中又维护了prevnextitem三个属性其中通过prev指向前一个结点通过next指向后一个结点从而实现双向链表。 3.LinkedList中元素的添加和删除在底层不是通过数组来完成的而是通过链表来完成的因此LinkedList相对来说效率更高。 PS : 以上内容涉及到了数据结构基础中关于链表的部分知识比如什么是首结点和尾结点当然仅仅是涉及到一些基础的概念性的知识。 双向链表的示意图如下 : 这里up用java来模拟一个简单的双向链表现在我们想创建三个璃月人对象——刻晴甘雨钟离并且让它们形成如下的双向链表关系 以Link_Simulation类为例代码如下 :
package csdn.knowledge.api_tools.gather.list;import java.util.LinkedList;/*** author : Cyan_RA9* version : 21.0*/
public class Link_Simulation {public static void main(String[] args) {//演示 : 用java模拟一个简单的双向链表。//创建璃月人对象Node keqing new Node(刻晴);Node ganyu new Node(甘雨);Node zhongli new Node(钟离);//完成双向链表keqing.next ganyu;ganyu.next zhongli;zhongli.pre ganyu;ganyu.pre keqing;Node first keqing;Node last zhongli;//遍历链表头 —— 尾while (true) {if (first null) {break;}System.out.println(first); //输出当前对象的信息first first.next; //更改指向}System.out.println();//遍历链表尾 —— 头while (true) {if (last null) {break;}System.out.println(last); //输出当前对象的信息last last.pre; //更改指向}}
}class Node {public Object item; //存放当前结点的数据。public Node pre; //指向前一个结点public Node next; //指向后一个结点public Node(Object name) {this.item name;}public String toString() {return Node s name item;}
} 运行结果 : 四、LinkedList类的源码解读 1.add方法解读 : 〇准备工作 。 up以LinkedList_Demo1为演示类代码如下 :在创建对象那行代码设置断点
package csdn.knowledge.api_tools.gather.list;import java.util.LinkedList;/*** author : Cyan_RA9* version : 21.0*/
public class LinkedList_Demo1 {public static void main(String[] args) {LinkedList linkedList new LinkedList();linkedList.add(11);linkedList.add(141);System.out.println(linkedList);}
}①跳入无参构造。 如下图所示 : 可以看到LinkedList类的无参构造其实是什么也没有做我们跳出无参构造。无参构造器执行完毕后我们可以看到LinkedList对象已经初始化完毕如下图所示 : 注意看此时 first 和 last 均为null类型。所以链表此时是这样一个效果 : ②跳入add方法。 如下图所示 : 因为我们要向链表中添加的元素为int类型所以第一次跳入add方法是一个自动装箱的过程我们不用管他直接跳出。 再次跳入add方法如下图所示 : ③跳入linkList方法。 形参列表的E e表示我们当前要添加的元素所以此时e 11。add方法中调用了linkLast方法不用想也能猜到这个linkLast方法里面完成了添加元素的操作我们继续追进去看看如下图所示 : 我们一步一步来看—— 首先, Node是“结点”的意思。 其次还记得我们上面提到说——first 和 last此时均为null。所以linkLast方法内第一步是定义了一个Node类型的常指针l并为其赋初值为last即null 接着又定义了一个Node类型的常量newNode见名知意newNode就是我们要添加的新结点。那么为newNode初始化的这个带参构造是怎么执行的呢这三个实参分别是干嘛的别急我们这就通过Ctrl b/B快捷键追到其源码中看看如下图所示 : 一看源码我们就明白了这不就是上文中我们提到的——双向链表的三个值吗所以对应此处的三个实参l就是prev此时为nulle就是已经装箱好的11null就是next的值。因此newNode引用此时指向的就是一个前后均为空值为11的新结点。并且之后又令last指向了该新结点。 继续向下执行是一个if-else的复合条件语句。判断条件l null显然满足令first也指向了该新结点之后又令size自增1size表示当前链表中元素的个数modCount也自增1修改次数)。 ④增加第一个元素成功。 好的linkList方法执行完毕后此时链表就长下面这样子 : 接下来我们逐层跳出直到演示类中。我们可以看到此时链表的状态如下图所示 : 可以看到first 和 last 都指向了同一个结点并且该结点中prev和next均为null。 ⑤向链表中添加第二个元素。 前面几个步骤都一样我们就不再赘述了直接从linkList方法开始说起如下 : 还是一步一步来看—— 首先令Node类型的常指针l 指向了last所指向的结点(即我们刚刚添加的第一个结点。 其次第二个新结点进行初始化工作。注意第一个实参l 代表的是新结点的prev而l 此时又指向了第一个结点因此这一步实现了——第二个新节点的prev指向了第一个结点。 接着又令last指向了第二个新结点此时first仍指向第一个结点。 然后就是if-else的判断语句了因为l 已经指向了第一个结点不为空所以执行ele中的语句令第一个结点的next指向了第二个新结点。 最后就是size和modCount的自增。 所以第二次linkList方法执行完毕后链表就应该长下面这个样子 : 2.remove方法解读 : 〇准备工作 。 up以LinkedList_Demo2为演示类代码如下 :在remove方法那行代码设置断点
package csdn.knowledge.api_tools.gather.list;import java.util.LinkedList;/*** author : Cyan_RA9* version : 21.0*/
public class LinkedList_Demo2 {public static void main(String[] args) {LinkedList linkedList new LinkedList();linkedList.add(11);linkedList.add(141);linkedList.add(5);System.out.println(添加三个元素后当前链表 linkedList);linkedList.remove();System.out.println(删除第一个元素后当前链表 linkedList);}
}运行结果 : 如代码所示我们事先在链表中加入三个元素111415。则在删除元素之前我们的双向链表应该长下面这样子 : ①关于LinkedList类的remove方法。 通过查看API文档我们可得知LinkedList类的remove有三个重载方法如下图所示 : 其中形参列表为空的remove() 方法其内部默认调用的是removeFrist方法即默认删去链表中的第一个元素形参列表需要传入一个索引的remove(int index) 方法可以删去链表中指定索引位置的元素较复杂形参列表需要传入一个Object类型的值的remove(Object o)方法是删去链表中与该值匹配的第一个元素。 up就以最简单的remove() 方法通过Debug来给大家分析一下。 ②跳入remove() 方法。 我们直接在remove方法的调用行设置断点跳过去并跳入remove方法如下图所示 : ③跳入removeFirst() 方法。 可以看到果然是调用了removeFirst() 方法那它底层到底是如何把链表的第一个元素给干掉的我们继续往里面追如下图所示 : removeFirst方法内部还是比较简洁的。首先它令一个Node类型的常指针f 指向了首结点即第一个存放有效数据的结点然后判断头结点是否为空。由于我们一开始就在链表中添加了3个元素所以此处f 肯定不为空。因此if语句中的内容会跳过return一个unlinkFirst() 方法的返回值。 ④跳入unlinkFirst() 方法。 可以看到removeFirst方法内部并没有执行删除操作的代码。我们继续追入unlinkFirst方法如下图所示 : 哎呀我趣看这一大串显然删除操作是在这里面完成的。 老规矩我们一步一步来看—— 首先第一条语句不用看。因为这只是在函数最后return的删除掉的元素的值与删除过程本身无关。 其次第二条语句它令一个Node类型的常指针next指向了第一个结点的next属性所指向的值即指向了第二个结点如下图所示 : 接着又依次置空了第一个结点的item和next并且令first 指向了第二个结点如下图所示 : 继续 由于next现在指向的是第二个结点不为空所以接下里要进入else语句中。else语句中令第二个结点的prev为null如下图所示 : ⑤第一个元素被除去。 至此第一个元素已经被干掉了。回忆一下案发现场jvm先是破掉了第一个结点的盾牌即first接着又切断了第一个结点的逃跑路线(即next最后又斩断了第一个结点的后援即第二个结点的prev。那第一个结点手无寸铁又成了单兵作战留给它的命运只能是被gc垃圾回收器除去哎可悲。bushi 五、总结 以上就是关于LinkedList源码分析的全部内容了。由于《java基础》是面向基础阶段系列博文而LinkedList作为链表已经属于数据结构的内容了。因此本篇博文中up也是尽量避重就轻已不至于过于晦涩。当然对于有些在学C语言的时候接触过链表的小伙伴儿们来说应该还是没什么难度的。好的至此我们的单列集合之List接口就算是全部搞定了。下一小节我们将开始进入set集合的内容大家不见不散。感谢阅读 System.out.println(END----------------------------------------------------------);
