数据结构与算法 —— Java 实现(链表)_Gorit的博客-程序员秘密

技术标签: java  java学习  链表  数据结构  

一、单链表

不知大家是否还记得自己刚接触数据结构的时候,是怎么过来的吗,那时候学习数据结构是使用 c语言实现,那时候会充满各种疑问?这个 * 啥意思,那个 & 又是啥意思,为啥结构体里面,有个和结构体名一样的东西,是不是像极了当初学数据结构的你呢?

1.1 链表的定义

链表实际上是一个二元组,它的每一个节点都分别存有 数据下一个节点的地址,这样我们就可以抽象出 链表中具有的基本属性

  1. 定义 节点为 Node
  2. 每个节点中都有数据 data
  3. 和指向下一个地址引用 (指针,java 中没有指针的概念)
    在这里插入图片描述
// 定义一个单链表
public class Node {
    
	private int data; // 这里我默认存储的数据都是整数
	private Node next; // 存放下一个地址的引用
	
	// 编写构造方法
	public Node(int data) {
    
		this.data = data;
	}

    // 获取下一个节点的方法
    public Node next() {
    
        return this.next;
    }

    // 获取节点中的数据
    public int getData() {
    
        return this.data;
    }

}

1.2 链表添加一个新的节点

实现思路:
如果我要在链表中插入一个节点,但是我只知道头结点,所以我需要一个节点一个节点的查找,直至找那个下一个节点为空的节点停止,然后将该节点的地址指向一个我们要插入的节点,即可完成插入操作。不懂?没关系,看下面的动图展示

在这里插入图片描述
下面就来实现一下:

这一步的核心就是找到最后一个节点

    // 为节点追加节点 (解决不断增加的问题)
    public Node append(Node node) {
    
        // 获得当前节点
        Node currentNode = this;
        // 循环向后找,找到下一个节点为空的最后一个节点
        while (true) {
    
            // 取出下一个节点
            Node nextNode = currentNode.next;
            // 如果下一个节点为 Null, 当前节点已经是最后一个节点
            if (nextNode == null) {
    
                break;
            }
            // 赋值给当前节点
            currentNode = nextNode;

        }
        // 把需要追加的节点追加到当前找到的当前节点
        currentNode.next = node;
        return this;
    }

1.3 判断当前节点是否为最后一个节点 (isLast)

只要判断当前节点的引用是否为空即可

    // 当前节点是否为最后一个节点
    public boolean islast() {
    
        return this.next == null;
    }

1.4 删除下一节点 (removeNext)

我们要删除一个节点

  1. 需要将他的指向的节点变成指向为空
  2. 将指向该节点的指针指向下下一个节点
    我们看动画
    在这里插入图片描述
	// 这个就很简单啦,只需要把引用改一下,就完成了
    // 删除下一个节点
    public void removeNext() {
    
        // 取出下下一个节点
        Node newNext = next.next;
        // 把下下一个节点设置为当前节点的下一个节点
        this.next = newNext;
    }

1.5 显示节点信息(show)

使用循环打印出链表中的每个节点对应的值

    // 显示所有节点的信息
    public void show() {
    
        Node currentNode = this;
        while (true) {
    
            System.out.print(currentNode.data+" ");
            // 取出下一个节点
            currentNode = currentNode.next;
            // 如果是最后一个节点
            if (currentNode == null) {
    
                System.out.println();// 换行处理
                break;
            }
        }
    }

1.6 插入一个节点(after)

往当前节点的位置插入一个节点,使其变成当前节点的下一个节点
在这里插入图片描述

    // 插入一个节点,作为当前节点的下一个节点,这就可以类比为 交换两个数字的值
    public void after(Node node) {
    
        // 取出下一个节点,作为下下一个节点
        Node nextNext = next;
        // 把新节点插入为当前节点的下一个节点
        this.next = node;
        // 把下下一个节点作为新节点的下一个节点
        node.next = nextNext;
    }

1.7 编写测试类(TestNode)

import Array.util.Node;

public class TestNode {
    
    public static void main(String[] args) {
    
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        // 追加节点
        n1.append(n2).append(n3).append(new Node(4));

        // 显示所有节点内容
        n1.show();

        // 去除下一个节点
//        n1.next().removeNext(); // 删除3
//        n1.show();

        // 插入一个新节点
        Node node = new Node(5);
        n1.next().after(node);
        n1.show();

        System.out.println(n1.next().getData());
        System.out.println(n2.next().getData());
        System.out.println(n3.getData());
        System.out.println(n3.islast());
    }
}

在这里插入图片描述

二、循环单链表

循环链表,就是把链表的尾部和头部相连

2.1 循环单链表定义

public class LoopNode {
    
    // 节点内容
    private int data;
    // 下一个节点
    private LoopNode next = this;
    public LoopNode(int data) {
    
        this.data = data;
    }
}

2.2 获取下一个节点及数据

 // 获取下一个节点的方法
    public LoopNode next() {
    
        return this.next;
    }

    // 获取节点中的数据
    public int getData() {
    
        return this.data;
    }

2.3 插入节点

    // 插入一个节点,作为当前节点的下一个节点
    public void after(LoopNode node) {
    
        // 取出下一个节点,作为下下一个节点
        LoopNode nextNext = next;
        // 把新节点插入为当前节点的下一个节点
        this.next = node;
        // 把下下一个节点作为新节点的下一个节点
        node.next = nextNext;
    }

2.4 删除节点

    // 删除下一个节点
    public void removeNext() {
    
        // 取出下下一个节点
        LoopNode newNext = next.next;
        // 把下下一个节点设置为当前节点的下一个节点
        this.next = newNext;
    }

2.5 循环遍历每一个节点

    // 显示所有节点的信息
    public void show() {
    
        LoopNode currentNode = this;
        while (true) {
    
            System.out.print(currentNode.data+" ");
            // 取出下一个节点
            currentNode = currentNode.next;
            // 如果是最后一个节点
            if (currentNode == null) {
    
                System.out.println();
                break;
            }
        }
    }

三、循环双链表

循环双链表,是指头和尾部相连,同时又具有前节点和后节点的引用

3.1 双向循环链表的定义

// 双向链表实现
public class DoubleLoop {
    
    // 上一个节点
    private DoubleLoop pre;
    // 下一个节点
    private DoubleLoop next = this;
    // 节点的数据
    private int data;

    public DoubleLoop(int data) {
    
        this.data = data;
    }

    public int getData() {
    
        return data;
    }
}

3.2 获取上(下)一个节点

    // 下一个节点
    public DoubleLoop next() {
    
        return this.next;
    }

    // 上一个节点
    public DoubleLoop pre() {
    
        return this.pre;
    }

3.3 增加节点

    // 增加节点
    public void after(DoubleLoop node) {
    
        // 原来的下一个节点
        DoubleLoop nextNext = next;
        // 新节点作为当前节点的下一个节点
        this.next = node;
        // 当前节点作为新节点的前一个节点
        node.pre = this;
        // 原来的下一个节点作为新节点的下一个节点
        node.next = nextNext;
        // 让原来的下一个节点的上一个节点为当前新节点
        nextNext.pre = node;
    }
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/caidewei121/article/details/105249133

智能推荐

STM32 串口通信介绍及cubemx配置_Nie_Hen的博客-程序员资料

学习理解STM32的串口通信,中断以及I2C的使用。应用:使用中断和串口通通信获取按键值发送出来并显示到数码管上。使用I2C 将获取到的按键值保存到内存中。串口通信计算机的CPU与外部设备之间的信息交换,以及计算机与计算机之间的信息交换过程称为通信。并行通信数据字节的各位同时传送的通信方式。并行通信的优点是数据传送速度快,缺点是占用的传输线条数多,适用于近距离通信。串行通信(Se...

android 背景图缩放,解决android:background背景图片被拉伸问题_weixin_39639600的博客-程序员资料

ImageView中XML属性src和background的区别:background会根据ImageView组件给定的长宽进行拉伸,而src就存放的是原图的大小,不会进行拉伸。src是图片内容(前景),bg是背景,可以同时使用。此外:scaleType只对src起作用;bg可设置透明度,比如在ImageButton中就可以用android:scaleType控制图片的缩放方式如上所述,backg...

qt用odbc连接mysql_【原创】Qt 使用ODBC driver 连接SQL Server_午餐时间到了的博客-程序员资料

最近在做数据库的课程设计。第一个需要解决的问题是使用什么工具来实现这个系统。经过一番资料查找,决定使用SQL Server Express 2012作为服务器,使用Qt作为编写客户端程序语言。问题是client如何连接SQL Server? 下面是我的解决方法。1.开启windows上的SQL Server 的ODBC驱动ODBC 是一个调用级接口,它使得应用程序得以访问任何具有 ODBC 驱动程...

翻页时钟代码大公开_lovefan的博客-程序员资料_翻页钟开源代码

不少朋友向我要翻页时钟的代码,现在贴给大家。代码水平有限,见谅。看不明白的可以问我:)js// miniprogram/pages/flipClock/jsconst moment = require('../../../utils/moment-with-locales.min.js');const Lunar = require('../../../utils/lunar.js');var startX, endX;var moveFlag = true; // 判断执行滑动事件.

JAVA切换不了FTP服务器目录_解决linux下ftp指定访问目录无法修改的问题_豪睿刘爱上楼楼梯的博客-程序员资料

他的系统是CentOS,是RH派系的。我把vsftpd安装配置好了,以为大功告成,但客户端访问提示如下错误:500 OOPS: cannot change directory:/home/ftp原因是他的CentOS系统安装了SELinux,因为默认下是没有开启FTP的支持,所以访问时都被阻止了。//查看SELinux设置# getsebool -a|grep ftpftpd_disable_tr...

.NET实现网络爬虫_hyunbar的博客-程序员资料_.net 爬虫

爬虫的特征和运行方式User-Agent:主要用来将我们的爬虫伪装成浏览器。Cookie:主要用来保存爬虫的登录状态。连接数:主要用来限制单台机器与服务端的连接数量。代理IP:主要用来伪装请求地址,提高单机并发数量。爬虫工作的方式可以归纳为两种:深度优先、广度优先。深度优先就是一个连接一个连接的向内爬,处理完成后再换一下一个连接,这种方式对于我们来说缺点很明显。 广度优先...

随便推点

一文了解人脸识别:从实现方法到应用场景都讲明白了_大数据v的博客-程序员资料

导读:在本文中,我们将会接触到一个既熟悉又陌生的概念——人脸识别。之所以熟悉,是因为人脸识别技术在我们日常生活中应用极其广泛,例如火车站刷脸验票进站、手机人脸解锁等;之所...

twisted builtins.TypeError: __init__() missing 1 required positional argument: 'dbpool'_锅前带刀小笼包的博客-程序员资料

学习爬虫异步插入,遇到问题Unhandled error in Deferred:2020-05-10 14:41:59 [twisted] CRITICAL: Unhandled error in Deferred:...builtins.TypeError: __init__() missing 1 required positional argument: 'dbpool'发现是函数名写错, 应该是from_settings ,结果写成了from_setting,低级错误,记录一下pip

Paxos、Raft、ZAB算法_知知之之的博客-程序员资料_paxos raft zab

Paxos算法是Leslie Lamport在1990年提出的一种基于消息传递的一致性算法。基于Paxos协议的数据同步与传统主备方式最大的区别在于:Paxos只需超过半数的副本在线且相互通信正常,就可以保证服务的持续可用,且数据不丢失。Paxos将系统中的角色分为提议者 (Proposer),决策者 (Acceptor),和最终决策学习者 (Learner):在多副本状态机中,每个副本同时具有Proposer、Acceptor、Learner三种角色。Paxos算法通过一个决议分为两个阶段(Learn阶段

Bibtex格式类型_小王同学w的博客-程序员资料_bibtex类型

出于保留资源和查找方便,转载自https://blog.csdn.net/kmsj0x00/article/details/85318057类型简介必需关键字可省略关键字@article期刊或杂志上的一篇文章。author, title, journal, year.volume, number, pages, month, [email protected]有确定出版社的书籍。author或editor, title, publisher, year.volume或number, series, address, e

SpringBoot-Google二步验证_apkqfa6158的博客-程序员资料

SpringBoot-Google二步验证概念:Google身份验证器Google Authenticator是谷歌推出的基于时间的一次性密码(Time-based One-time Password,简称TOTP),只需要在手机上安装该APP,就可以生成一个随着时间变化的一次性密码,用于帐户验证。Google身份验证器是一款基于时间与哈希的一次性密码算法的两步验证软件令牌,此软件...

Maven_weixin_41249041的博客-程序员资料

maven帮助构建项目 项目和项目之间的依赖关系,管理jar包。项目管理工具,管理java项目:1、项目对象模型 POM对象模型,每个maven工程中都有一个pom.xml文件,定义工程所依赖的jar包、本工程的坐标、打包运行方式。。2、依赖管理系统(基础核心 )maven通过坐标对项目工程所依赖的jar包统一规范管理。3、maven定义一套项目生命周期清理、初始...

推荐文章

热门文章

相关标签