Java数据结构之单链表详解
作者：rain67 发布时间：2023-11-04 17:02:20
目录
一、图示
二、链表的概念及结构
三、单链表的实现
四、完整代码的展示
一、图示
二、链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
单向、双向
带头、不带头
循环、非循环
今天，我们实现的是一个 单向 无头 非循环的链表。
下面是此链表的结构组成。
三、单链表的实现
（1）定义一个节点类型
我们创建一个 ListNode 的类作为节点类型，那么我们如何定义成员属性呢？
通过上面的结构分析，我们需要定义两个成员变量 val --作为该节点的存储的数值， next – 保存下一个节点的地址/引用。
同时定义之后，他们的默认值为 0 ，null ，所以要想赋予这个节点数值，要写一个构造方法去首先保存数值。
这里我们提供了两个构造方法，一个是实现提供数值的节点，另一个是没有提供数值的节点，方便我们之后使用。
之后我们在 MyListNode 的类中实现单链表的各种方法。
（2）头插法
以上述结构为例，这个单链表没有专门的傀儡节点来充当头节点，首个节点就定义为头节点，所以头插法，就是我们定义一个节点，插在这个链表的最前面，作为新的 head。
代码实现：
1.定义一个插入的节点
ListNode cur = new ListNode(2);
此时我们就创建了一个val 为2 的节点。
2.插在头节点的前面
这里分两种情况，
第一次插入节点
不是第一次插入节点
头插之后的结构：
代码实现：
（3）尾插法
和头插法类似，同样插入一个节点，在链表的最后。
这里插入也分为两种情况
第一次插入节点
不是第一次插入节点
代码实现：
（4）根据下标插入节点
第一个数据节点为0号下标，任意位置插入节点。
还以上面的链表为例，我们想将新的节点插入到2 号位置
如果想插到2号位置，我们需要改变原来的 1号位置节点和2号位置节点的相关属性。
思路实现：
1.先判断传入的 index 下标位置是否合法
2.如果传入的index==0，头插法
3.如果传入的index==sizeof(),尾插法
4.如果 sizeof() > index > 0 在链表中间插入,我们首先要找到 index-1 位置的节点 prev
查找 index-1
修改 prev节点的属性 以及 新节点的属性
node.next = prev.next
prev.next = node;
代码实现过程
（5）查找关键字
以上面的链表为例，我们现在要查找这个链表中是否出现 val=20 的节点，如果存在，那么返回true，如果不存在，则返回 false.
遍历链表，走过每一个节点，如果 cur.val == key，则 return ture ，遍历完后还未找到 key，那么return false.
（6）删除第一次出现的关键字
思路实现：
代码实现：
（7）得到单链表的长度
（8）单链表打印展示
不能是this.head.next != null 这样写 最后一个节点是不能被打印的
（9）节点的回收
节点的回收有两种方式：
1.暴力法
直接将head 置空
2. 挨个置空
遍历单链表，将每一个节点的next都置为 null.
四、完整代码的展示
来源：https://blog.csdn.net/rain67/article/details/116849015
0
投稿猜你喜欢
- ProgressDialog 继承自AlertDialog，AlertDialog继承自Dialog,实现DialogInterface接口
本文实例为大家分享了Android Chronometer计时器基本使用方法，供大家参考，具体内容如下在默认情况下，Chronometer组- 概述在Winform中从后台添加控件相对比较容易，但是在WPF中，我们知道界面是通过XAML编写的，如何把后台写好的控件动态添加到前台呢？本
- 本文实例讲述了java实现清理DNS Cache的方法。分享给大家供大家参考。具体分析如下：一、测试环境OS：Windows7 x64JDK
- 在 C# 语言中 StreamReader 类用于从流中读取字符串。它继承自 TextReader 类。StreamReader 类的构造方
- 本文实例为大家分享了C#实现窗体抖动的具体代码，供大家参考，具体内容如下原理：围绕中心点运动一圈方法一：通过线程实现需求:需要using S
- 在 C语言中，占位符是一种用于格式化输出的特殊字符，通常用于 printf() 等输出函数中，用于指定输出的格式和内容。在本文中，我们将详细
- 1.新建Android studio工程2.新建class：AppKey.java.主要为了保存密钥代码块package com...adm
- 一、前言Java 8 引入了默认方法以及可以在接口中定义的静态方法。默认方法是一个普通的 java 方法，但以 default 关键字开头，
- 简单使用redis-zset实现排行榜此方法实现一个根据某字段的查询次数进行排行，查询的次数越多排行越前（从大到小排序），适用于初学者1.添
- 在前面的文章中也有关于 HorizontalScrollView 的使用：Android使用HorizontalScrollView实现水平
- springcloud整合stream,rabbitmq实现消息驱动功能1.代码实现：创建项目stream添加依赖<parent>
- 性能优化点：1.使用int不使用double。（单位用分不用元）也省去了还要用math.round四舍五入，把double类型数据只留小数点
- 相关知识：Java中三种简单注解介绍和代码实例一、作用用 @Deprecated注解的程序元素，不鼓励程序员使用这样的元素，通常是因为它很危
- 本项目使用的环境：开发工具：Intellij IDEA 2017.1.3springboot: 1.5.6jdk：1.8.0_161mave
- Java 8 Instant 时间戳用于“时间戳”的运算。它是以Unix元年(传统 的设定为UTC时区1970年1月1日午夜时分)开始 所经
- 本文实例为大家分享了Android实现图像切换器的具体代码，供大家参考，具体内容如下java代码：private int[] imageId
- 1.介绍有时候我们在Linux中运行Java程序时，需要调用一些Shell命令和脚本。而Runtime.getRuntime().exec(
- using System;using System.Collections;using System.Text;using Sy
- 大家好，这是 C# 9.0 新特性短系列的第 5 篇文章。弃元（Discards） 是在 C# 7.0 的时候开始支持的，它是一种人为丢弃不
