欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

Java - 双向链表的数据结构

最编程 2024-06-11 12:30:31
...

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

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

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

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

1.单链表的实现

(1)定义一个节点类型

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

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

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

在这里插入图片描述
在这里插入图片描述

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

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

代码语言:javascript
复制
    public ListNode head;
    public ListNode last;

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

(2)头插法

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

思路:

  这里分两种情况:

第一次插入

不是第一次插入

在这里插入图片描述
在这里插入图片描述

代码展示:

在这里插入图片描述
在这里插入图片描述

(3)尾插法

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

在这里插入图片描述
在这里插入图片描述

代码展示:

在这里插入图片描述
在这里插入图片描述

(4)根据下标插入节点

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

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

思路:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

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

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

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

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

代码展示:

在这里插入图片描述
在这里插入图片描述

(5)查找关键字

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

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

思路:

在这里插入图片描述
在这里插入图片描述

代码展示:

在这里插入图片描述
在这里插入图片描述

(6)删除第一次出现的关键字

在这里插入图片描述
在这里插入图片描述

思路:

在这里插入图片描述
在这里插入图片描述

代码展示:

在这里插入图片描述
在这里插入图片描述

(7)删除所有出现的关键字key

在这里插入图片描述
在这里插入图片描述

思路:

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

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

在这里插入图片描述
在这里插入图片描述

代码展示:

在这里插入图片描述
在这里插入图片描述

(8)节点的回收

  节点的回收有两种方式:

1.暴力法

   直接将head、last 置空

2. 挨个置空

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

思路:

在这里插入图片描述
在这里插入图片描述

代码展示:

在这里插入图片描述
在这里插入图片描述

(9)链表打印展示

在这里插入图片描述
在这里插入图片描述

2.完整代码展示

在这里插入图片描述
在这里插入图片描述

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

  感谢支持!!!

完!

推荐阅读