Java数据结构链表

物理上不一定连续，但逻辑上连续

链表是由一个一个的节点组织起来的，整体就叫做链表。

public class MySingleLinkedList {
    //将节点定义为内部类
    class ListNode{//节点有两个域
        public int val;
        public ListNode next;//next为引用类型

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;//为链表的头节点

    public void createList(){
        ListNode node1=new ListNode(12);
        ListNode node2=new ListNode(23);
        ListNode node3=new ListNode(34);
        ListNode node4=new ListNode(45);
        ListNode node5=new ListNode(56);
    }

}

如何让第一个节点和第二个节点关联起来，依此类推.......?

node1.next=node2(代表整个对象，存地址）

怎么从第一个节点走到第二个节点？

head=head.next;

链表什么时候遍历完？

head为空时 即head==null

为什么不是head.next==null?

会少打印一个值。如果要把每个结点的值都遍历完，head==null

public void display(){
        ListNode cur=head;//以防再遍历链表的时候找不到head
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

求长度：

public int size(){
        ListNode cur=head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }

插入结点的时候，一般首先绑后边

头插法：

public void addFirst(int val){
        ListNode node=new ListNode(val);
        node.next=head;
        head=node;
    }
public class Test {
    public static void main(String[] args) {
        MySingleLinkedList msl=new MySingleLinkedList();
        //msl.createList();此时这种琼剧创建链表的方式可以用插入来替代了
        msl.addFirst(1);
        msl.addFirst(2);
        msl.addFirst(3);
        msl.addFirst(4);
        msl.display();
        System.out.println(msl.size());
    }
}

尾插：

1.找到链表的尾巴

cur.next==null cur指向的就是尾巴

2.cur.next=node

public void addLast(int val){
        ListNode node=new ListNode(val);
        ListNode cur=head;
        //尾插需注意：cur.next 空指针异常
        if(head==null){
            head=node;//node为第一个节点
            return;
        }
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
    }

在任意位置插入:

1.得找到index位置的前一个

cur走index-1步

2.如何连接？

3.index==0 头插

4.index==len 尾插

5.index不合法呢？即index<0 || index>len

查找链表中是否包含某个数

public boolean contains(int val){
        ListNode cur=head;
        while(cur!=null){
            if(cur.val==val){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

删除某个数

1.得找到那个数的前一个cur

if(cur.next.val==val)->找到了

2.删除

cur.next=del.next;

cur.next=del.next;

3.循环条件是什么

while(cur.next!=null)

        if(cur.next.val==val)

public void remove(int val){
        ListNode cur=head;
        while(cur.next!=null){
            if(cur.next.val==val){
                ListNode del=cur.next;
                cur.next=del.next;
                return;
            }
            cur=cur.next;
        }
    }

但是还删不了头节点

public void remove(int val) {
        //空连表不可删
        if (head == null)
            return;
        if (head.val == val) {
            head = head.next;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == val) {
                ListNode del = cur.next;
                cur.next = del.next;
                return;
            }
            cur = cur.next;
        }
    }

删除所有需要删除的值 

最后再删除头节点或者首先就用while循环一直删掉所有和值相等的头节点 

cur代表当前需要删除的节点

prev代表当前需要删除节点cur的前驱节点

public void removeAllKey(int val){
        //1.判空
        if(head==null){
            return;
        }
        //2.定义 prev和null
        ListNode prev=head;
        ListNode cur=head.next;
        //3.开始判断并删除
        while(cur!=null){
            if(cur.val==val){
                prev.next=cur.next;
            }else{
                prev=cur;//prev=prev.next;
            }
            cur=cur.next;
        }
        //4.处理头节点
        if(head.val==val){
            head=head.next;
        }
    }

完整代码：

public class MySingleLinkedList {
    //将节点定义为内部类
    class ListNode {//节点有两个域
        public int val;
        public ListNode next;//next为引用类型

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;//为链表的头节点

    public void createList() {
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.head = node1;
    }//当方法结束后node1 node2...这些变量都不存在了-局部变量被回收

    public void display() {
        ListNode cur = head;//因为此时为不带头链表，以防再遍历链表的时候找不到head
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public int size() {
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public void addFirst(int val) {
        ListNode node = new ListNode(val);
        node.next = head;
        head = node;
    }

    public void addLast(int val) {
        ListNode node = new ListNode(val);
        ListNode cur = head;
        //尾插需注意：cur.next 空指针异常
        if (head == null) {
            head = node;//node为第一个节点
            return;
        }
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    public void addIndex(int index, int val) {
        //1.判断index的合法性
        try {
            checkIndex(index);
        } catch (IndexNotLegalException e) {
            e.printStackTrace();
        }
        //2.index==0 || index==size()
        if (index == 0) {
            addFirst(val);
            return;
        }
        if (index == size()) {
            addLast(val);
            return;
        }
        //3.找到index的前一个位置
        ListNode cur = findIndexSubOne(index);
        //4.进行连接
        ListNode node = new ListNode(val);
        node.next = cur.next;
        cur.next = node;
    }

    private ListNode findIndexSubOne(int index) {
        int count = 0;
        ListNode cur = head;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    private void checkIndex(int index) throws IndexNotLegalException {
        if (index < 0 || index > this.size()) {
            throw new IndexNotLegalException("index不合法");
        }
    }

    public boolean contains(int val) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public void remove(int val) {
        //空连表不可删
        if (head == null)
            return;
        if (head.val == val) {
            head = head.next;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == val) {
                ListNode del = cur.next;
                cur.next = del.next;
                return;
            }
            cur = cur.next;
        }
    }

    public void removeAllKey(int val) {
        //1.判空
        if (head == null) {
            return;
        }
        //2.定义 prev和null
        ListNode prev = head;
        ListNode cur = head.next;
        //3.开始判断并删除
        while (cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;
            } else {
                prev = cur;//prev=prev.next;
            }
            cur = cur.next;
        }
        //4.处理头节点
        if (head.val == val) {
            head = head.next;
        }
    }

    //清空
    public void clear() {
        // head=null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curN = cur.next;
            cur.next = null;
            cur = curN;
        }
        head = null;
    }
}

public class IndexNotLegalException extends RuntimeException{
    public IndexNotLegalException() {
    }
    public IndexNotLegalException(String msg) {
        super(msg);
    }

}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/505177.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【C++入门】输入输出、命名空间、缺省参数、函数重载、引用、内联函数、auto、基于范围的for循环

【C++入门】输入输出、命名空间、缺省参数、函数重载、引用、内联函数、auto、基于范围的for循环

目录 命名空间 命名空间的定义 命名空间的使用 输入输出 缺省参数 函数重载 引用 常引用 引用的使用场景 内联函数 auto 基于范围的for循环 命名空间 请看一段C语言的代码&#xff1a; #include <stdio.h> #include <stdlib.h>int rand 10;int main…
阅读更多...
机器学习-关联规则算法Apriori及编码实现

机器学习-关联规则算法Apriori及编码实现

一、前置知识 在了解关联规则之前首先了解一些相关概念&#xff0c;包含项集、频繁项集、支持度、置信度、提升度等基础概念。假如我们在经营一家商品超市&#xff0c;顾客进行购买商品的订单信息如下&#xff1a; TID ItemsT1 {耳机&#xff0c;背包}T2{背包&#xff0c;手…
阅读更多...
实践笔记-harbor仓库镜像上传与拉取

实践笔记-harbor仓库镜像上传与拉取

harbor仓库镜像上传与拉取 1.上传镜像修改 daemon.json 配置文件上传镜像至harbor 2.拉取镜像登录账号&#xff08;跟上传镜像那里一样操作登录步骤就可以了&#xff09;拉取镜像 环境&#xff1a;centos7 1.上传镜像 修改 daemon.json 配置文件 # 编辑daemon.json文件&#…
阅读更多...
【Entity Framework】创建并配置模型

【Entity Framework】创建并配置模型

【Entity Framework】创建并配置模型 文章目录 【Entity Framework】创建并配置模型一、概述二、使用fluent API配置模型三、分组配置四、对实体类型使用EntityTypeConfigurationAttribute四、使用数据注释来配置模型五、实体类型5.1 在模型中包含类型5.2 从模型中排除类型5.3 …
阅读更多...
RabbitMQ--04--发布订阅模式 (fanout)-案例

RabbitMQ--04--发布订阅模式 (fanout)-案例

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 发布订阅模式 (fanout)---案例前言RabbitListener和RabbitHandler的使用 1.通过Spring官网快速创建一个RabbitMQ的生产者项目2.导入项目后在application.yml文件中配…
阅读更多...
MSTP环路避免实验（华为）

MSTP环路避免实验（华为）

思科设备参考&#xff1a;MSTP环路避免实验&#xff08;思科&#xff09; 一&#xff0c;技术简介 MSTP&#xff08;多生成树协议&#xff09;&#xff0c;MSTP解决了STP和RSTP没有考虑vlan的问题&#xff0c;STP和RSTP将所有的vlan共享为一个生成树实例&#xff0c;无法实现…
阅读更多...
数据链路层之信道：数字通信的桥梁与守护者

数据链路层之信道：数字通信的桥梁与守护者

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…
阅读更多...
蓝桥杯刷题第五天（昨天刷了忘记更了）

蓝桥杯刷题第五天（昨天刷了忘记更了）

思路&#xff1a; 用dp来记录最短消耗时间 dp[坐标][zhuangtai] 状态0表示在底部&#xff0c;状态1表示在传送门处&#xff1b; 先初始化dp[1][0] 和dp[1][1]然后循环遍历到dp[n][0] 和dp[n][1]&#xff0c;用动态规划方程去赋值&#xff1b; ps&#xff1a;易错点在于要开…
阅读更多...
基于spark的大数据分析预测地震受灾情况的系统设计

基于spark的大数据分析预测地震受灾情况的系统设计

基于spark的大数据分析预测地震受灾情况的系统设计 在本篇博客中，我们将介绍如何使用Apache Spark框架进行地震受灾情况的预测。我们将结合数据分析、特征工程、模型训练和评估等步骤，最终建立一个预测模型来预测地震造成的破坏程度，同时使用可视化大屏的方式展示数据的分布…
阅读更多...
CCF-CSP19＜2020-06＞-第1/2题

CCF-CSP19＜2020-06＞-第1/2题

202006-1 线性分类器 题目分析&#xff1a; 给定n个点&#xff0c;并标记为AB两类&#xff0c;问给定直线是否能将其分为两个点集。 简单数学知识&#xff0c;点在直线上满足axbyc0&#xff0c;点在直线割平面所得的上下其值会正负相反。 AC代码&#xff1a; // -*- codin…
阅读更多...
C++入门知识详细讲解

C++入门知识详细讲解

C入门知识详细讲解 1. C简介1.1 什么是C1.2 C的发展史1.3. C的重要性1.3.1 语言的使用广泛度1.3.2 在工作领域 2. C基本语法知识2.1. C关键字(C98)2.2. 命名空间2.2 命名空间使用2.2 命名空间使用 2.3. C输入&输出2.4. 缺省参数2.4.1 缺省参数概念2.4.2 缺省参数分类 2.5. …
阅读更多...
日历插件fullcalendar【笔记】

日历插件fullcalendar【笔记】

日历插件fullcalendar【笔记】 前言版权开源推荐日历插件fullcalendar一、下载二、初次使用日历界面示例-添加事件&#xff0c;删除事件 三、汉化四、动态数据五、前后端交互1.环境搭建-前端搭建2.环境搭建-后端搭建3.代码编写-前端代码fullcalendar.htmlfullcalendar.js 4.代码…
阅读更多...
【前端】layui前端框架学习笔记

【前端】layui前端框架学习笔记

【前端目录贴】 参考视频:LayUI 参考笔记:https://blog.csdn.net/qq_61313896/category_12432291.html 1.介绍 官网&#xff1a;http://layui.apixx.net/index.html 国人16年开发的框架,拿来即用,门槛低 … 2. LayUi的安装及使用 Layui 是一套开源的 Web UI 组件库&#xff0…
阅读更多...
乐乐音乐鸿蒙版-支持krc歌词(动感歌词、翻译和音译歌词)

乐乐音乐鸿蒙版-支持krc歌词(动感歌词、翻译和音译歌词)

简介 乐乐音乐主要是基于HarmonyOS开发的音乐播放器&#xff0c;它支持lrc歌词和动感歌词(ksc歌词、krc歌词和hrc歌词等)、多种格式歌词转换器及制作动感歌词、翻译歌词和音译歌词。 开发环境 ArkTS、Stage模型、SDK3.1、 API 9 注&#xff1a;没试过在真机条件下调试。 功…
阅读更多...
SpringCloud-Eureker配置中心搭建

SpringCloud-Eureker配置中心搭建

一、基于本地配置文件的 Eureker配置中心搭建 1.、创建一个springBoot项目 <properties><project.build.sourceEncoding>UTF-8</project.build.sourceEncoding><java.version>1.8</java.version><component.version>0.0.1-SNAPSHOT</…
阅读更多...
机器学习：探索数据中的模式与智能

机器学习：探索数据中的模式与智能

文章目录 导言介绍&#xff1a;机器学习的定义和重要性发展历程&#xff1a;从概念到现实应用 基础概念机器学习的基本原理监督学习、无监督学习和强化学习的区别与应用1.监督学习2.无监督学习3.强化学习 常见的机器学习任务和应用领域 结语 导言 当代科技领域中最为引人注目的…
阅读更多...
两张图片相似度匹配算法学习路线

两张图片相似度匹配算法学习路线

大纲&#xff1a;​​​​​​目标跟踪基础&#xff1a;两张图片相似度算法-腾讯云开发者社区-腾讯云 (tencent.com) 目标跟踪基础&#xff1a;两张图片相似度算法 (qq.com) 一、传统方法 1.欧式距离&#xff08;用于判断是否完全相同&#xff09; [三维重建] [机器学习] 图…
阅读更多...
NC13610 矩阵

NC13610 矩阵

题目描述 给出一个n * m的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出最大正方形的边长。 输入描述: 第一行两个整数n, m代表矩阵的长和宽&#xff1b; 接下来n行&#xff0c;每行m个字符&#xff08;小写字母&#xff09;&#x…
阅读更多...
IAG—高潮

IAG—高潮

阅读更多...
Java8 新特性 Stream流操作

Java8 新特性 Stream流操作

数据准备 package test;/*** [一句话描述该类的功能]** author : [61692]* version : [v1.0]* createTime : [2024/3/31 14:52]*/ public class Student {private int id;private int age;private int yuwenScore;private int mathScore;private String name;private int yi…
阅读更多...
最新文章

Copyright @ 2022~2023