入门数据结构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实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Android实现两台手机屏幕共享和远程控制功能

《Android实现两台手机屏幕共享和远程控制功能》在远程协助、在线教学、技术支持等多种场景下,实时获得另一部移动设备的屏幕画面,并对其进行操作,具有极高的应用价值,本项目旨在实现两台Android手... 目录一、项目概述二、相关知识2.1 MediaProjection API2.2 Socket 网络

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

使用Python实现图像LBP特征提取的操作方法

《使用Python实现图像LBP特征提取的操作方法》LBP特征叫做局部二值模式,常用于纹理特征提取,并在纹理分类中具有较强的区分能力,本文给大家介绍了如何使用Python实现图像LBP特征提取的操作方... 目录一、LBP特征介绍二、LBP特征描述三、一些改进版本的LBP1.圆形LBP算子2.旋转不变的LB

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

SpringBoot多数据源配置完整指南

《SpringBoot多数据源配置完整指南》在复杂的企业应用中,经常需要连接多个数据库,SpringBoot提供了灵活的多数据源配置方式,以下是详细的实现方案,需要的朋友可以参考下... 目录一、基础多数据源配置1. 添加依赖2. 配置多个数据源3. 配置数据源Bean二、JPA多数据源配置1. 配置主数据

C# Where 泛型约束的实现

《C#Where泛型约束的实现》本文主要介绍了C#Where泛型约束的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录使用的对象约束分类where T : structwhere T : classwhere T : ne

将Java程序打包成EXE文件的实现方式

《将Java程序打包成EXE文件的实现方式》:本文主要介绍将Java程序打包成EXE文件的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录如何将Java程序编程打包成EXE文件1.准备Java程序2.生成JAR包3.选择并安装打包工具4.配置Launch4

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr