Java集合框架剖析(4)——LinkedList

╰+哭是因爲堅強的太久メ 2022-05-28 06:14 242阅读 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