Java集合框架剖析(4)——LinkedList ╰+哭是因爲堅強的太久メ 2022-05-28 06:14 218阅读 0赞 ![这里写图片描述][70] * LinkedList是一个继承与AbatractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 * LinkedList实现了List接口,能对它进行队列操作。 * LinkedList实现了Deque接口,即能将LinkedList当作双端队列使用。 * LinkedList实现了java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。 顺便说一下LinkedList的父类AbstractSequentialList ![这里写图片描述][70 1] 虽然LinkedList没有实现RandomAccess接口,但是其父类AbstractSequentialList实现了get、set、add、remove方法 这些接口都是随机访问List的,LinkedList是双向链表,既然它继承与AbstractSequentialList,就相当于已经实现了“get(int index)”这些接口,可以支持随机访问了。 此外,如果我们需要通过AbstractSequentialList实现一个自己的列表,只需要扩展此类,并提供listIterator()和size()方法的实现即可。若要实现不可修改的列表,则需要实现列表迭代器的hashNext、next、hashPrevious、previous和index方法即可。 下面先总览一下LinkedList的构造函数和API: ![这里写图片描述][70 2] LinkedList包含三个重要的成员:first、last和size:first是双向链表的表头,last是双向链表的尾节点,size是双向链表中的节点个数。 ![这里写图片描述][70 3] 这里先说一下`transient关键字`的用法: 一个对象只要实现了Serilizable接口,这个对象就可以被序列化,java的这种序列化模式为开发者提供了很多便利,可以不必关系具体序列化的过程, 只要这个类实现了Serilizable接口,这个的所有属性和方法都会自动序列化。但是有种情况是有些属性是不需要序列号的,所以就用到这个关键字。 只需要实现Serilizable接口,将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会序列化到指定的目的地中。 ## 源码剖析 ## ## 属性 ## ![这里写图片描述][70 4] 其中Node是一个内部类: ![这里写图片描述][70 5] 参数为前一个节点,元素,后一个节点 ## 构造函数 ## ![这里写图片描述][70 6] 依然是规范了两种构造函数 ## 头尾节点的添加 ## ![这里写图片描述][70 7] ![这里写图片描述][70 8] 其中的判定`f==null`表示此时的链表为空, modCount为Modified Count的缩写,表示修改次数。 ## 头尾节点的删除 ## ![这里写图片描述][70 9] public接口,供外部调用 ![这里写图片描述][70 10] ![这里写图片描述][70 11] ## 获取头尾节点 ## ![这里写图片描述][70 12] ## 判定是否在链表中,以及index获取 ## ![这里写图片描述][70 13] ![这里写图片描述][70 14] 循环遍历,O(1)时间复杂度 ## add、remove ## ![这里写图片描述][70 15] 都是已元素为参数的,并且满足一个即返回 ## addAll、clear ## ![这里写图片描述][70 16] ![这里写图片描述][70 17] ## 随机位置操作 ## ![这里写图片描述][70 18] ![这里写图片描述][70 19] **都是循环遍历的方式,所以如果用随机位置循环来遍历LinkedList的话,那真是脑门被门夹了。** ## 搜索操作 ## ![这里写图片描述][70 20] ![这里写图片描述][70 21] ## Queue操作 ## ![这里写图片描述][70 22] ## DeQueue操作 ## ![这里写图片描述][70 23] ![这里写图片描述][70 24] ![这里写图片描述][70 25] ## 迭代器 ## LinkedList的迭代器分为双向迭代器(ListItr)和前向迭代器(DescendingIterator) ## 双向迭代器 ## ![这里写图片描述][70 26] ![这里写图片描述][70 27] ![这里写图片描述][70 28] ![这里写图片描述][70 29] 都是链表的基本操作 ## 前向迭代器 ## ![这里写图片描述][70 30] 前向迭代器的next其实获取的是previous ## 总结 ## 1. LinkedList是通过双向链表去实现的。 从LinkedList的实现方式中可以看出,它不存在容量不足的问题,因为是链表 2. LinkedList实现java.io.Serializable的方式。当写入到输出流时,先写入“容量”,再依次写出“每一个元素”;当读出输入流时,先读取“容量”,再依次读取“每一个元素”。 3. LinkdedList的克隆函数,即是将全部元素克隆到一个新的LinkedList中。 4. 由于LinkedList实现了Deque,而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。 5. LinkedList可以作为**FIFO(先进先出)的队列**,作为FIFO的队列时,下标的方法等价: ![这里写图片描述][70 31] 1. LinkedList可以作为LIFO(后进先出)的栈,作为LIFO的栈时,下表的方法等价: ![这里写图片描述][70 32] ## 遍历方式 ## 1 .for方式 2. 迭代器方式 3. 快速随机访问 LinkedList适合for和迭代器,如果用快速随机访问的话那么复杂度是O(n) **再次强调一遍不要用随机访问遍历LinkedList** [70]: /images/20220528/8c1bdffc65234839b71ab315922c5011.png [70 1]: /images/20220528/0edf768b8501451d9035c745c660081f.png [70 2]: /images/20220528/93a363bd34114d8389f6d61cd6d19661.png [70 3]: /images/20220528/e5c4fdf23a694f6589c8714a0b2eb648.png [70 4]: /images/20220528/5d2321afd0744e45b5f240bcc37067cb.png [70 5]: /images/20220528/2573ede78f5d4d5f9c884d429c735874.png [70 6]: /images/20220528/6d226a21178542e4bd6bf00978857021.png [70 7]: /images/20220528/86618076954d400e8ee90f8e6eb76c48.png [70 8]: /images/20220528/22ec9f5e9b0b45d7951b1d78c1af3ca4.png [70 9]: /images/20220528/95cb224db82f45d5924862bb5dbd015f.png [70 10]: /images/20220528/997859fbb36a45c5875a0ef116f8e319.png [70 11]: /images/20220528/804c832de6194d638f7e419f4b316dc2.png [70 12]: /images/20220528/7a8138747a7043179c46bc59d310550a.png [70 13]: /images/20220528/334a773a6a814ac4ab086ed1f48c252a.png [70 14]: /images/20220528/e31f8611d2d047a6a29510f357e513bb.png [70 15]: /images/20220528/903c32431d684e40b34e454d9ed10aa7.png [70 16]: /images/20220528/a81c5024023c42bc967e612d853c3a9c.png [70 17]: /images/20220528/ebee82afabb3479b80182e8ac70e4ffc.png [70 18]: /images/20220528/e5e25ca34ecc4d97981fd1e6b560e5bb.png [70 19]: /images/20220528/2eb20d317c1d4fa0b327fe001e8343ed.png [70 20]: /images/20220528/d60ced4c2ef243ce86f5cac3456c60da.png [70 21]: /images/20220528/1c951289fefd4174b761d332e7fc49ed.png [70 22]: /images/20220528/21293621c679456bab8dc9bc58110280.png [70 23]: /images/20220528/e1ab6948f97f4638b80a65374a815a5e.png [70 24]: /images/20220528/ba4dfa9652ae49d09ce21901e9e41d8a.png [70 25]: /images/20220528/031a9486ea7c4f709793951c47cf4bf8.png [70 26]: /images/20220528/90a168c7e96643ba9a23fcd09f855cfb.png [70 27]: /images/20220528/eac68a7db35143eda293bdb51d14f931.png [70 28]: /images/20220528/63b521ffd54b4b82953c5ef90c525165.png [70 29]: /images/20220528/9fb91e19770040babd41859b03b08a3d.png [70 30]: /images/20220528/959c270c98be44c8b337c5e8089fb865.png [70 31]: /images/20220528/fef62490f44a4b32bd99cd3df3d5b242.png [70 32]: /images/20220528/90ab8fcff3d643f4888754103d64cb29.png
相关 Java集合框架:ArrayList与LinkedList对比 在Java的集合框架中,ArrayList和LinkedList是两种常用的动态数组。它们各自有特定的应用场景和特性。 1. ArrayList: - **特点**: ゞ 浴缸里的玫瑰/ 2024年09月10日 11:36/ 0 赞/ 24 阅读
相关 Java集合框架详解:ArrayList vs LinkedList 在Java的集合框架中,ArrayList和LinkedList是两种常用的动态数组。它们各有特点,适用于不同的场景。 1. ArrayList: - 数据结构:基于数组实现 た 入场券/ 2024年09月04日 09:24/ 0 赞/ 19 阅读
相关 java集合框架入门解析-----linkedList java集合框架入门解析-----linkedList 0.结构图 1.linkedList是什么 2.linkedList的特点 3.Linke 素颜马尾好姑娘i/ 2022年12月29日 04:39/ 0 赞/ 142 阅读
相关 【Java集合源码剖析】LinkedList源码剖析 LinkedList简介 LinkedList是基于双向循环链表(从源码中可以很容易看出)实现的,除了可以当做链表来操作外,它还可以当做栈、队列和双端队列来使用。 谁借莪1个温暖的怀抱¢/ 2022年07月18日 00:24/ 0 赞/ 251 阅读
相关 java集合框架剖析(8)——Hashtable \\Hashtable继承结构: ![这里写图片描述][70] 们可以看出,HashTable不但继承了Dictionary,而且实现了Map、Cloneable和Se 缺乏、安全感/ 2022年05月28日 10:36/ 0 赞/ 192 阅读
相关 java集合框架剖析(7)——HashMap ![这里写图片描述][70] HashMap不仅继承了AbstractMap,而且实现了Map、Cloneable和Serializable接口,所以HashMap也可以序 向右看齐/ 2022年05月28日 07:45/ 0 赞/ 187 阅读
相关 Java集合框架剖析(4)——LinkedList ![这里写图片描述][70] LinkedList是一个继承与AbatractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 ╰+哭是因爲堅強的太久メ/ 2022年05月28日 06:14/ 0 赞/ 219 阅读
相关 Java集合框架剖析(3)——ArrayList ArrayList ![这里写图片描述][70] ArrayList继承了AbstractList,实现了List。它是一个数组队列,相当于动态数组。提供了相关的添加 绝地灬酷狼/ 2022年05月28日 06:12/ 0 赞/ 157 阅读
相关 Java集合LinkedList LinkedList List接口的一个实现类 内部维护了一个双向循环链表 链表中的每一个元素,都使用引用来记录它的前一个元素和后一个元素 从而,将所有的元素连 ╰半夏微凉°/ 2022年05月17日 11:46/ 0 赞/ 214 阅读
还没有评论,来说两句吧...