Java ——LinkedList的原理及应用

r囧r小猫 2021-07-25 22:24 381阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70]

--------------------

QQ 1274510382  
Wechat JNZ\_aming  
商业互捧 QQ群538250800  
技术搞事 QQ群599020441  
技术合作 QQ群152889761  
加入我们 QQ群649347320  
纪年科技aming  
网络安全 ,深度学习,嵌入式,机器强化,生物智能,生命科学。

--------------------

#### LinkedList也是List接口的实现类， ####

与ArrayList不同之处是采用的存储结构不同  
ArrayList的数据结构为线性表，而LinkedList数据结构是链表。

--------------------

链表数据结构的特点：  
每个元素分配的空间不必连续、  
插入和删除元素时速度非常快、但访问元素的速度较慢。

LinkedList是一个双向链表,  
当数据量很大或者操作很频繁的情况下，添加和删除元素时具有比ArrayList更好的性能。  
但在元素的查询和修改方面要弱于ArrayList。

LinkedList类每个结点用内部类Node表示，  
LinkedList通过first和last引用分别指向链表的第一个和最后一个元素，  
当链表为空时，first和last都为NULL值。  
LinkedList数据结构如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 1]

LinkedList类内部的Node结点代码如下：  
![在这里插入图片描述][20200330073437394.png]  
Node节点一共有三个属性：  
item代表节点值，  
prev代表节点的前一个节点，  
next代表节点的后一个节点。

每个结点都有一个前驱和后继结点，  
并且在 LinkedList中也定义了两个变量分别指向链表中的第一个和最后一个结点。

transient Node first;  
transient Node last;

1、添加元素到LinkedList  
LinkedList提供了多个添加元素的方法：  
●boolean add(E e)  
在链表尾部添加一个元素，  
如果成功，返回true，否则返回false。

●void addFirst(E e)  
在链表头部插入一个元素。

●addLast(E e)  
在链表尾部添加一个元素。

●void add(int index, E element)  
在指定位置插入一个元素。

添加元素到LinkedList示例代码如下:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 2]  
代码通过add、addFirst、addLast方法加入元素，并通过println输出链表元素。

输出结果如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 3]  
2、从LinkedList中删除元素

LinkedList提供了多个删除元素的方法：

●boolean remove(Object o)

从当前链表中移除指定的元素。

● E remove(int index)

从当前链表中移除指定位置的元素。

● E removeFirst()

从当前链表中移除第一个元素。

● E removeLast()

从当前链表中移除最后一个元素。

● E remove()

从当前链表中移除第一个元素，同removeLast()相同。

从LinkedList删除元素示例代码如下:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 4]  
代码通过add方法加入元素，  
再通过remove、removeFirst、removeLast等方法移除元素，  
并通过println输出操作后的链表元素。  
输出结果如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 5]  
3、从LinkedList中获取元素

LinkedList提供了多个获取元素的方法：

● E get(int index)

从当前链表中获取指定位置的元素。

● E getFirst()

从当前链表中获取第一个元素。

● E getLast()

从当前链表中获取最后一个元素。

从LinkedList获取元素示例代码如下:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 6]  
代码通过add方法加入元素，再通过get、getFirst、getLast方法获取元素，并通过println输出操作后的链表元素。  
输出结果如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 7]  
4、LinkedList的遍历方法

同前面介绍的集合类遍历方式一样，  
LinkedList可以通过迭代器、  
foreach语句、  
for循环语句等方法  
遍历集合的所有元素。

遍历LinkedList元素示例代码如下:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 8]  
代码采用for循环、迭代器、foreach方式，  
遍历包含10万个元素的LinkedList，

通过输出结果可以看出，  
foreach语句效率最高，其次是迭代器，效率最差的是for循环。  
输出结果如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 9]

*  LinkedList存储元素的数据结构是双向链表结构，
 *  由存储元素的结点连接而成，
 *  每一个节点都包含前一个节点的引用，
 *  后一个节点的引用和节点存储的值。
 *  当一个新节点插入时，只需要修改其中保持先后关系的节点的引用即可。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70]: /images/20210725/8388781e6e1d493fb0dcfec0cee7ff78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200330073349931.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw,size_16,color_FFFFFF,t_70
[20200330073437394.png]: https://img-blog.csdnimg.cn/20200330073437394.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200330073901947.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200330073922709.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200330074009586.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2020033007403995.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200330074056115.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200330074135942.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200330074212142.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200330074314730.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw,size_16,color_FFFFFF,t_70