前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Java——数据结构之双向链表

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

作者头像
RAIN7
发布2021-08-11 16:37:44
6950
发布2021-08-11 16:37:44
举报

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.完整代码展示

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

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

  感谢支持!!!

完!

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021-05-23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Java——数据结构之双向链表
  • 1.单链表的实现
    • (1)定义一个节点类型
      • (2)头插法
        • (3)尾插法
          • (4)根据下标插入节点
            • (5)查找关键字
              • (6)删除第一次出现的关键字
                • (7)删除所有出现的关键字key
                  • (8)节点的回收
                    • (9)链表打印展示
                    • 2.完整代码展示
                    • 完!
                    领券
                    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档