入门数据结构JAVA DS——如何实现简易的单链表(用JAVA实现)

2024-09-05 02:52

本文主要是介绍入门数据结构JAVA DS——如何实现简易的单链表(用JAVA实现),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

链表(Linked List)是一种线性数据结构,它由一系列节点组成,每个节点包含两个部分:存储数据的部分和指向下一个节点的指针(或引用)。链表的结构使得它能够动态地增长和收缩,适合在不固定长度的序列中进行插入和删除操作。

链表的基本概念:

  1. 节点(Node):链表的基本单位,每个节点包含两个部分:

    • 数据域(Data):存储节点的具体数据。
    • 指针域(Pointer/Next):存储指向下一个节点的引用。
  2. 头节点(Head):链表的第一个节点,通常用于存储链表的入口。

  3. 尾节点(Tail):链表的最后一个节点,它的指针域指向 null(在 Java 等语言中)或 None(在 Python 中),表示链表的结束。

  4. 空链表:当链表中没有任何节点时,它被称为空链表,头节点指向 null

并且,相比于顺序表,链表可以动态的管理大小,在插入或者删除元素时,时间复杂度也更低.

以一言蔽之:

链表在需要动态内存管理、频繁插入删除操作、不确定数据量的场景中优势明显.

那么,我们怎么徒手搓出来一个链表呢? 本文以单向链表为例

如何创建链表中的节点

为了从零开始写出一个链表,我们可以大致分成两个步骤

第一:我们首先要能写出一个节点

           

第二:我们把这些节点以某种方式连接起来

那我们首先做到第一步,怎么 创建一个节点?

很显然,这个节点需要一个值域和一个地址域,前者存储它的值,后者存储下一个节点的地址,

这样就创造了将节点们连接起来的条件

我们只需要创建一个类

public class Listnode
{public int value;public Listnode next;public Listnode(int value){this.value = value;}
}

就正如代码所写的,其中value表示值, next 说人话就是下一个节点的地址. 

说的官方一点就是:它表示一个指向链表中下一个节点的引用.

链表的实现

为了实现 无头单向非循环链表

我们需要如下的一些方法(里面不但存在基本方法,也存在笔者的私货)

       public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到单链表的长度public int size();public void clear();public void reverseList();// 反转链表public void display() ;

 我们可以把它们写进一个接口里

OK,现在我们再写一个类,来正式地实现我们这些方法吧

在实现类中,我们首先要定义好头节点,和使用大小这两个值.

public  class MyIlist implements IList
{public int usedsize;public Listnode head;
}

头插法

就是往链表的头部插入新的元素,这里肯定有两种情况

情况一: 链表为空,那么这个插入的节点就是头结点

情况二:链表不为空,那么我们就要改变原头结点的位置,具体实现如下

新的结点node的地址域中的值就是原来的头结点的地址

然后node结点变成新的节点

代码如下

    @Overridepublic void addFirst(int data) {Listnode node = new Listnode(data);if (head == null) {this.head = node;} else {node.next = this.head;this.head = node;}}

尾插法

往链表的最末端插入新的元素,思路同样很简单,找到末端的结点,它的地址域肯定是null.

然后将它的地址域的值设为新节点的地址

代码如下:

    @Overridepublic void addLast(int data){Listnode node = new Listnode(data);if (head == null) {this.head = node;return;}Listnode cur = this.head;while (cur.next != null) {cur = cur.next;}cur.next = node;}

删除一个值为key的结点

这个相对来说比较麻烦,但是思路很简单,你需要删除那个,你就直接"跳过"它,即将它上一个结点的地址域设置为它的下一个结点的地址

(图很丑,但是能理解意思就好)

为了达到这个目的,我们首先就要找到需要删掉结点的上一个结点

方法如下:

    private Listnode findIndex2(int key) {Listnode cur = this.head;while (cur.next != null) {if (cur.next.value == key) {return cur;}cur = cur.next;}return null;}

但这也漏洞啊,头结点怎么办?头结点也没有前置结点啊?

所以这就是特例,如果是要删的是头结点,就直接让 head=head.next 即可

完整代码如下:

    @Overridepublic void remove(int key) {if (this.head == null) {return;}if (this.head.value == key) {this.head = this.head.next;return;}Listnode cur = findIndex2(key);if (cur == null) {return;}Listnode del = cur.next;// del结点就是要删除的结点cur.next = del.next;// 这步是什么就不用我多说了吧}

 

删除所有值为key的结点

这个呢其实和删除单一结点差不多,只不过是要重复多遍

这里笔者就给一个简洁的概况一切情况的代码

    @Overridepublic void removeAllKey(int key){Listnode dummy = new Listnode(0);dummy.next = this.head;Listnode cur = dummy;while (cur.next != null) {if (cur.next.value == key) {cur.next = cur.next.next;} else {cur = cur.next;}}this.head = dummy.next;}

 

在指定下标插入元素

该方法同样思路简单,找到 前一个下标的结点

将它的地址域的值赋给需要插入的node的地址域,然后改变前一个下标结点的地址域

    private Listnode findIndex(int idx) {Listnode cur = this.head;int num = 0;while (num != idx - 1) {cur = cur.next;num++;}return cur;}@Overridepublic void addIndex(int index, int data) {if (index < 0 || index > size()) {return;}if (index == 0) {addFirst(data);return;}if (index == size()) {addLast(data);return;}Listnode cur = findIndex(index);Listnode node = new Listnode(data);node.next = cur.next;cur.next = node;}

其他方法

剩下的就是一些其他的方法,比如求链表的大小,求链表是否有值为X的结点,清除链表中的所有元素,按顺序打印链表元素等

笔者在此一并展示

    @Overridepublic int size() {Listnode cur = this.head;this.usedsize = 0;while (cur != null) {usedsize++;cur = cur.next;}return usedsize;}
    @Overridepublic void clear() {Listnode cur = this.head;while (cur != null) {Listnode curNext = cur.next;cur.value = 0;cur.next = null;cur = curNext;}head = null;System.out.println("清空");}
   @Overridepublic boolean contains(int key) {Listnode cur = this.head;while (cur != null) {if (cur.value == key) {return true;}cur = cur.next;}return false;}
    @Overridepublic void display() {Listnode cur = this.head;if (head == null) {System.out.println("链表为空");return;}while (cur != null) {System.out.print(cur.value + " ");cur = cur.next;}System.out.println();}

 

结尾

以上就是实现一个单向无循环链表的基本方法,还有一些细分的方法,笔者未来介绍题目时会带着

希望这篇博客能带您快速入门,并能自己动手写出来

完整代码在鄙人的github中

MyJava/Java DS/src/SLlist/MyIlist.java at main · calljsh/MyJava (github.com)

需要的点进去直接看完整的

这篇关于入门数据结构JAVA DS——如何实现简易的单链表(用JAVA实现)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137771

相关文章

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4