Java——数据结构之双向链表

矫情吗；* 2022-10-15 04:54 201阅读 0赞

### 文章目录 ###

*  Java——数据结构之双向链表
 *  1.单链表的实现
 *   *  （1）定义一个节点类型
     *  （2）头插法
     *  （3）尾插法
     *  （4）根据下标插入节点
     *  （5）查找关键字
     *  （6）删除第一次出现的关键字
     *  （7）删除所有出现的关键字key
     *  （8）节点的回收
     *  （9）链表打印展示
 *  2.完整代码展示
 *  完！

# Java——数据结构之双向链表 #

接上篇[Java——数据结构之单链表][Java]

在之前的学习中，我们主要了解了很多 Java 的 基本语法，但是 在之后的 Java学习中，了解 基础 数据结构的知识 非常重要，数据结构的思想 可以帮助我们更加清晰 明白的了解 Java 的解题思路等等。

今天我们就来开始学习 实现一个 Java 基础的 不带头双向非循环链表。

# 1.单链表的实现 #

## （1）定义一个节点类型 ##

我们创建一个 ListNode 的类作为节点类型，那么我们如何定义成员属性呢？

通过上面的结构分析，我们需要定义两个成员变量 val --作为该节点的存储的数值， next – 保存下一个节点的地址/引用， prev - 保存上一个节点的地址/引用

同时定义之后，他们的默认值为 0 ，null ，null，所以要想赋予这个节点数值，要写一个构造方法去首先保存数值。

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

这里我们提供了两个构造方法，一个是实现提供数值的节点，另一个是没有提供数值的节点，方便我们之后使用。

作为双向链表，可以从头节点遍历到尾节点，同时也可以从尾节点遍历到头节点，所以我们要定义两个节点—— head头节点，last尾节点

public ListNode head;
        public ListNode last;

之后我们在 LinkedList 的类中实现单链表的各种方法。

## （2）头插法 ##

以上述结构为例，这个单链表没有专门的傀儡节点来充当头节点，首个节点就定义为头节点，所以头插法，就是我们定义一个节点，插在这个链表的最前面，作为新的 head。

思路：

这里分两种情况：

> 第一次插入

> 不是第一次插入

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

代码展示：

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

## （3）尾插法 ##

和头插法类似，同样插入一个节点，在链表的最后。

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

代码展示：

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

## （4）根据下标插入节点 ##

第一个数据节点为0号下标，任意位置插入节点。

还以上面的链表为例，我们想将新的节点插入到2 号位置

思路：

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

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

> 1.先判断传入的 index 下标位置是否合法

> 2.如果传入的index==0，头插法

> 3.如果传入的index==sizeof(),尾插法

> 4.插入中间节点时，改变cur前后节点的属性

代码展示：

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

## （5）查找关键字 ##

以上面的链表为例，我们现在要查找这个链表中是否出现 val=20 的节点，如果存在，那么返回true，如果不存在，则返回 false.

遍历链表，走过每一个节点，如果 cur.val == key，则 return ture ，遍历完后还未找到 key，那么return false.

思路：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 4]

代码展示：

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

## （6）删除第一次出现的关键字 ##

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

思路：

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

代码展示：

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

## （7）删除所有出现的关键字key ##

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

思路：

删除的思路与上一个方法一致，不过上面第一次遇到关键字删除后，直接return了，要想删除所有关键字，将return 改为 cur = cur.next; 继续向后进行遍历。

特殊情况：节点全部出现关键字

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

代码展示：

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

## （8）节点的回收 ##

节点的回收有两种方式：

> 1.暴力法

直接将head、last 置空

> 2. 挨个置空

遍历单链表，将每一个节点的next、prev都置为 null.

思路：

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

代码展示：

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

## （9）链表打印展示 ##

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

# 2.完整代码展示 #

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

好了今天的知识就分享到这里，希望大家多多练习，谢谢大家的欣赏与关注！！

感谢支持！！！

# 完！ #

[Java]: https://blog.csdn.net/rain67/article/details/116849015?spm=1001.2014.3001.5501
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/b56438d984414e43916634a69f3cc0ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70]: /images/20221014/1aafa6be51a34832a7f9ceb737e49ee8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221014/5a75a06572d948788eff6c4ae184f69d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 1]: /images/20221014/dd4628e6256c4233baf47b36815a11c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221014/80d2b46bae064f9984800b4e7465e9a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 2]: /images/20221014/eac6b565df424823bb5b04bd84029cdf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 3]: /images/20221014/f5e8c179077b49f19878242adf22863d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221014/4d0ab8979c8a46e09bdb53321054b771.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 4]: /images/20221014/0f4c1638d18c4fc39a8f96194407f779.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221014/7a541a2c31d54bfe9647134157620453.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 5]: /images/20221014/b9a1df8163fb4f4ba79e7c846143baf5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 6]: /images/20221014/debb31f0ae3647fd84fef1c16b8f41d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221014/420a040738f24609b57689869d4270f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 7]: /images/20221014/90b79c5c32f04099b0b5c13b960967f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 8]: /images/20221014/658ec0d654c14d30962ccc3373342713.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221014/54e243fd580342d89d90197d82b570d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 9]: /images/20221014/8e6de112cb30428a8aabdab5461710a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221014/90a772909d094173a41f58a30c920db3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221014/7bee73439eef4d0d97f81e98423bba76.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221014/8201a31ab27e441aa479f26d46b91227.png