首页 > 编程语言 >JAVA实现单链表修改和删除数据节点

JAVA实现单链表修改和删除数据节点

时间：2023-04-08 14:13:13浏览次数：45  
标签：getNext 单链 JAVA temp IdDataNode 节点 链表 id

JAVA实现单链表修改和删除数据节点

一、修改单链表中的一个节点

①实现思路

  1. 因为带头节点的链表中头节点的next域不能发生改变（始终指向单链表的头节点），否则将找不到该链表。所以我们需要先找一个辅助节点temp来进行节点代理操作。
  2. 通过遍历链表，使辅助节点temp后移，找到要修改的节点。
  3. 然后进行修改操作。

②updateNode代码实现

/**
 * 修改节点的信息，根据id修改除id之外的节点信息，id是不能改变的
 * 根据IdDataNode的id来修改
 *
 * @param idDataNode 待修改的数据节点
 */
public void updateNode(IdDataNode idDataNode) {
    // 先判断链表是否为空
    if (head.getNext() == null) {
        System.out.println("链表为空");
    }

    // 定义辅助节点
    IdDataNode temp = head.getNext();

    // 标记是否找到了数据节点
    boolean flag = false;

    // 遍历找到要修改的数据节点
    while (true) {
        if (temp.getNext() == null) {
            break;
        }
        if (temp.getId() == idDataNode.getId()) {
            flag = true;    // 说明找到这个编号为id的节点了
            break;
        }
        temp = temp.getNext();  // 辅助节点后移
    }

    // 根据flag判断是否找到了要修改的节点
    if (flag) {
        temp.setData(idDataNode.getData());
    } else {
        System.out.println("没有找到等于这个节点的编号，修改失败！");
    }

}

③updateNode方法测试-整体代码

说明：本次实验的整体测试代码是在《JAVA实现节点加入到单链表时按需求排序》一文实验代码上做出的updateNode方法增加。

/**
 * ClassName: SingleLinkedListAddOrder
 * Package: com.zhao.test
 * Description:
 *
 * @Author XH-zhao
 * @Create 2023/3/27 13:31
 * @Version 1.0
 */
public class SingleLinkedListAddOrder {

    // 创建单链表头节点
    private IdDataNode head = new IdDataNode(0, "");

    // 将数据节点按照数据id添加进链表
    public void addByIdOrder(IdDataNode idDataNode) {

        // 使用辅助变量temp代替head进行移动
        IdDataNode temp = head;

        while (true) {

            // 说明temp走到了最后，必须要添加元素了（添加到最后）
            if (temp.getNext() == null) {
                break;
            }

            // temp节点的后一个节点的id比要添加节点的id大代表可以添加元素了
            if (temp.getNext().getId() > idDataNode.getId()) {
                break;
            } else if (temp.getNext().getId() == idDataNode.getId()) {
                System.out.println("您添加的元素已经存在了！！");
                // 直接结束方法
                return;
            }

            // 将temp元素后移（继续遍历）
            temp = temp.getNext();
        }

        // 当遍历结束时，temp已经指向了要插入的位置的前一个节点（开始插入）
        idDataNode.setNext(temp.getNext());
        temp.setNext(idDataNode);
    }

    // 遍历整个链表
    public void showLinkedListAll() {
        // 当链表为空时不进行遍历，直接结束
        if (head.getNext() == null) {
            System.out.println("链表为空");
            return;
        }
        // 遍历链表时同样需要辅助变量，因为head节点不能移动，否则就找不到该链表了
        IdDataNode temp = head;
        while (true) {
            // 当链表为空时，不进行遍历，直接结束循环
            if (temp.getNext() == null) {
                break;
            }
            // 直接输出链表节点存的数据
            System.out.println(temp.getNext());
            //将temp指针往后移动
            temp = temp.getNext();
        }
    }

    /**
     * 修改节点的信息，根据id修改除id之外的节点信息，id是不能改变的
     * 根据IdDataNode的id来修改
     *
     * @param idDataNode 待修改的数据节点
     */
    public void updateNode(IdDataNode idDataNode) {
        // 先判断链表是否为空
        if (head.getNext() == null) {
            System.out.println("链表为空");
        }

        // 定义辅助节点
        IdDataNode temp = head.getNext();

        // 标记是否找到了数据节点
        boolean flag = false;

        // 遍历找到要修改的数据节点
        while (true) {
            if (temp.getNext() == null) {
                break;
            }
            if (temp.getId() == idDataNode.getId()) {
                flag = true;    // 说明找到这个编号为id的节点了
                break;
            }
            temp = temp.getNext();  // 辅助节点后移
        }

        // 根据flag判断是否找到了要修改的节点
        if (flag) {
            temp.setData(idDataNode.getData());
        } else {
            System.out.println("没有找到等于这个节点的编号，修改失败！");
        }

    }

}

// 带ID的数据节点类
class IdDataNode {

    private int id; // 用来作为排序依据，即实现以id进行排序的单链表
    private String data;    // data域，要存储的数据
    private IdDataNode next;  // next域，用于指向下一个数据节点地址

    // 数据节点构造器
    public IdDataNode(int id, String data) {
        this.id = id;
        this.data = data;
    }

    @Override
    public String toString() {
        return "IdDataNode{" +
                "id=" + id +
                ", data='" + data + '\'' +
                '}';
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public IdDataNode getNext() {
        return next;
    }

    public void setNext(IdDataNode next) {
        this.next = next;
    }
}



// 更新节点数据测试类
class SingleLinkedListUpdateNodeTest {
    public static void main(String[] args) {

        // 创建四个数据节点，id分别是1-2-3-4
        IdDataNode dataNode1 = new IdDataNode(1, "data1");
        IdDataNode dataNode2 = new IdDataNode(2, "data2");
        IdDataNode dataNode3 = new IdDataNode(3, "data3");
        IdDataNode dataNode4 = new IdDataNode(4, "data4");

        // 创建带头节点的单链表
        SingleLinkedListAddOrder singleLinkedListAddOrder = new SingleLinkedListAddOrder();

        // 将四个数据节点增添到链表当中
        singleLinkedListAddOrder.addByIdOrder(dataNode1);
        singleLinkedListAddOrder.addByIdOrder(dataNode2);
        singleLinkedListAddOrder.addByIdOrder(dataNode3);
        singleLinkedListAddOrder.addByIdOrder(dataNode4);

        IdDataNode dataNode1_update = new IdDataNode(1, "data1_被修改");
        IdDataNode dataNode5_update = new IdDataNode(5, "data5_被修改");

        singleLinkedListAddOrder.updateNode(dataNode1_update);
        singleLinkedListAddOrder.updateNode(dataNode5_update);
        
        System.out.println("***************************************");
        
        // 显示链表中元素，查看数据是否被修改
        singleLinkedListAddOrder.showLinkedListAll();

    }
}

④测试结果

没有找到等于这个节点的编号，修改失败！
***************************************
IdDataNode{id=1, data='data1_被修改'}
IdDataNode{id=2, data='data2'}
IdDataNode{id=3, data='data3'}
IdDataNode{id=4, data='data4'}

进程已结束,退出代码0

二、删除单链表中的一个节点

①实现思路

理论思路：

  1. 我们依旧要找一个辅助节点temp来进行节点代理操作，通过遍历链表，找到需要删除的这个节点的前一个节点，将temp指向该节点。
  2. 然后将待删除节点的后一个节点的引用赋值给待删除节点前一个节点的next域（temp.next=temp.next.next）
  3. 待删除的节点，将不会有其他引用指向，会被垃圾回收机制回收

图解思路：

image-20230327194446569

②deleteNode代码实现

// 删除节点
public void deleteNode(IdDataNode idDataNode) {

    // 先判断链表是否为空
    if (head.getNext() == null) {
        System.out.println("链表为空");
    }

    // 使用辅助节点temp来进行节点代理操作
    IdDataNode temp = head;

    boolean flag = false;   // 标识是否找到删除节点的上一个节点

    while(true) {

        if(temp.getNext() == null) {
            break;
        }

        if(temp.getNext() == idDataNode){

            // 找到了要删除节点的上一个节点了，此时temp代理该节点
            flag = true;
            break;
        }

        temp = temp.getNext();  // 辅助节点后移

    }

    if(flag) {
        temp.setNext(temp.getNext().getNext()); // 然后将待删除节点的后一个节点的引用赋值给待删除节点前一个节点的next域
    }else {
        System.out.println("没有找到要删除的节点！");
    }

}

③deleteNode方法测试-整体代码

/**
 * ClassName: SingleLinkedListAddOrder
 * Package: com.zhao.test
 * Description:
 *
 * @Author XH-zhao
 * @Create 2023/3/27 13:31
 * @Version 1.0
 */
public class SingleLinkedListAddOrder {

    // 创建单链表头节点
    private IdDataNode head = new IdDataNode(0, "");

    // 将数据节点按照数据id添加进链表
    public void addByIdOrder(IdDataNode idDataNode) {

        // 使用辅助变量temp代替head进行移动
        IdDataNode temp = head;

        while (true) {

            // 说明temp走到了最后，必须要添加元素了（添加到最后）
            if (temp.getNext() == null) {
                break;
            }

            // temp节点的后一个节点的id比要添加节点的id大代表可以添加元素了
            if (temp.getNext().getId() > idDataNode.getId()) {
                break;
            } else if (temp.getNext().getId() == idDataNode.getId()) {
                System.out.println("您添加的元素已经存在了！！");
                // 直接结束方法
                return;
            }

            // 将temp元素后移（继续遍历）
            temp = temp.getNext();
        }

        // 当遍历结束时，temp已经指向了要插入的位置的前一个节点（开始插入）
        idDataNode.setNext(temp.getNext());
        temp.setNext(idDataNode);
    }

    // 遍历整个链表
    public void showLinkedListAll() {
        // 当链表为空时不进行遍历，直接结束
        if (head.getNext() == null) {
            System.out.println("链表为空");
            return;
        }
        // 遍历链表时同样需要辅助变量，因为head节点不能移动，否则就找不到该链表了
        IdDataNode temp = head;
        while (true) {
            // 当链表为空时，不进行遍历，直接结束循环
            if (temp.getNext() == null) {
                break;
            }
            // 直接输出链表节点存的数据
            System.out.println(temp.getNext());
            //将temp指针往后移动
            temp = temp.getNext();
        }
    }

    /**
     * 修改节点的信息，根据id修改除id之外的节点信息，id是不能改变的
     * 根据IdDataNode的id来修改
     *
     * @param idDataNode 待修改的数据节点
     */
    public void updateNode(IdDataNode idDataNode) {
        // 先判断链表是否为空
        if (head.getNext() == null) {
            System.out.println("链表为空");
        }

        // 定义辅助节点
        IdDataNode temp = head.getNext();

        // 标记是否找到了数据节点
        boolean flag = false;

        // 遍历找到要修改的数据节点
        while (true) {
            if (temp.getNext() == null) {
                break;
            }
            if (temp.getId() == idDataNode.getId()) {
                flag = true;    // 说明找到这个编号为id的节点了
                break;
            }
            temp = temp.getNext();  // 辅助节点后移
        }

        // 根据flag判断是否找到了要修改的节点
        if (flag) {
            temp.setData(idDataNode.getData());
        } else {
            System.out.println("没有找到等于这个节点的编号，修改失败！");
        }

    }

    // 删除节点
    public void deleteNode(IdDataNode idDataNode) {

        // 先判断链表是否为空
        if (head.getNext() == null) {
            System.out.println("链表为空");
        }

        // 使用辅助节点temp来进行节点代理操作
        IdDataNode temp = head;

        boolean flag = false;   // 标识是否找到删除节点的上一个节点

        while(true) {

            if(temp.getNext() == null) {
                break;
            }

            if(temp.getNext() == idDataNode){

                // 找到了要删除节点的上一个节点了，此时temp代理该节点
                flag = true;
                break;
            }

            temp = temp.getNext();  // 辅助节点后移

        }

        if(flag) {
            temp.setNext(temp.getNext().getNext()); // 然后将待删除节点的后一个节点的引用赋值给待删除节点前一个节点的next域
        }else {
            System.out.println("没有找到要删除的节点！");
        }

    }

}

// 带ID的数据节点类
class IdDataNode {

    private int id; // 用来作为排序依据，即实现以id进行排序的单链表
    private String data;    // data域，要存储的数据
    private IdDataNode next;  // next域，用于指向下一个数据节点地址

    // 数据节点构造器
    public IdDataNode(int id, String data) {
        this.id = id;
        this.data = data;
    }

    @Override
    public String toString() {
        return "IdDataNode{" +
                "id=" + id +
                ", data='" + data + '\'' +
                '}';
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public IdDataNode getNext() {
        return next;
    }

    public void setNext(IdDataNode next) {
        this.next = next;
    }
}

// 删除节点数据测试类
class SingleLinkedListDeleteNodeTest {
    public static void main(String[] args) {

        // 创建四个数据节点，id分别是1-2-3-4
        IdDataNode dataNode1 = new IdDataNode(1, "data1");
        IdDataNode dataNode2 = new IdDataNode(2, "data2");
        IdDataNode dataNode3 = new IdDataNode(3, "data3");
        IdDataNode dataNode4 = new IdDataNode(4, "data4");

        // 创建带头节点的单链表
        SingleLinkedListAddOrder singleLinkedListAddOrder = new SingleLinkedListAddOrder();

        // 将四个数据节点增添到链表当中
        singleLinkedListAddOrder.addByIdOrder(dataNode1);
        singleLinkedListAddOrder.addByIdOrder(dataNode2);
        singleLinkedListAddOrder.addByIdOrder(dataNode3);
        singleLinkedListAddOrder.addByIdOrder(dataNode4);

        IdDataNode dataNode5_delete = new IdDataNode(5, "data5");

        singleLinkedListAddOrder.deleteNode(dataNode1);
        singleLinkedListAddOrder.deleteNode(dataNode5_delete);
        System.out.println("***************************************");
        // 显示链表中元素，查看数据是否被修改
        singleLinkedListAddOrder.showLinkedListAll();

    }
}

④测试结果

没有找到要删除的节点！
***************************************
IdDataNode{id=2, data='data2'}
IdDataNode{id=3, data='data3'}
IdDataNode{id=4, data='data4'}

进程已结束,退出代码0

三、实验总结

通过以上实验，我们实现了单链表修改和删除数据节点的操作。

标签：getNext,单链,JAVA,temp,IdDataNode,节点,链表,id
From： https://www.cnblogs.com/zhao-XH/p/17298431.html

相关文章

  • Java-SPI机制详解
    Java之SPI机制详解1:SPI机制简介SPI全称是ServiceProviderInterface，是一种JDK内置的动态加载实现扩展点的机制，通过SPI技术我们可以动态获取接口的实现类，不用自己来创建。这个不是什么特别的技术，只是一种设计理念。2:SPI原理JavaSPI实际上是基于接口的编程＋策略模......
  • JavaScript 有效的字符串方法
    目录获得字符串的长度用处在字符串中查找子字符串找到字符串的位置判断是否包含特定子字符串截取子字符串的方法转换大小写替换字符串的某部分本文内容部分截取自该网站，不同部分则为本人笔记。获得字符串的长度letbrowserType='mozilla';browserType.length;用处检......
  • 剑指offer66(Java)-构建乘积数组（中等）
    题目：给定一个数组A[0,1,…,n-1]，请构建一个数组B[0,1,…,n-1]，其中 B[i]的值是数组A中除了下标i以外的元素的积,即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。 示例:输入:[1,2,3,4,5]输出:[120,60,40,30,24] 提示：所有元素乘积之和不会......
  • 【Java 并发】【九】【AQS】【八】ReentrantReadWriteLock之ReadLock读锁原理
    1 前言上节我们看了下ReentrantReadWriteLock读写锁的写锁的申请和释放过程，这节我们就来看下读锁的。2 线程读锁记录回顾一下之前的例子，在读写并发操作的时候，读取数据的时候加读锁：publicclassReentrantReadWriteLockTest{//声明一个读写锁privatestaticR......
  • 【JAVA树根白话二】——继承
    JAVA树根白话二继承Begin……[ABC]继承——面向对象的三个基本特征之一（另外两个是封装、多态） 应用场景：当封装两个类后，第一个类中有一个非常复杂的成员函数，第二个类也需要同样的一个成员函数。如果第二个类重新编写成员函数，会增加开发时间，并且可能会因为一些疏忽，造......
  • 剑指offer03(Java)-数组中重复的数字（简单）
    题目：找出数组中重复的数字。在一个长度为n的数组nums里的所有数字都在0～n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。示例1：输入：[2,3,1,0,2,5,3]输出：2或3 限制：2<=n<=1000......
  • JavaScript遍历数组用splice方法删除元素，这样写可能有遗漏，你遇到过吗？
    在编写“圳品”信息系统中，有时需要对二维数组中的数据进行筛选并删除一些元素，比如删除二维数组中首个元素为0的行。开始是用for循环访问数组+splice方法删除元素来做：vara=newArray([0,0,0,0],[1,1,1,1],[0,2,2,2],[......
  • JavaScript的引入方式
    外部JS文件deno.jsalert('你好!JavaScript');JS引入方式.html<!--方式一：内部脚本--><!--标签不能自闭和--><script>alert('你好JS')</script><!--方式二：外部引入--><scriptsrc="demo.js"></script>......
  • Java方法
    Java方法方法是什么解决一类问题的步骤的有序组合System.out.print()-------------------System是一个类out是一个对象print()是一个方法方法是一个语句块集合，它们在一起执行一个功能设计原则：保持原子性，一个方法只完成一个功能方法的定义及调用Java只有值传递方法......
  • Java内存模型
    Java内存模型的作用《Java虚拟机规范》中曾试图定义一种“Java内存模型”（JavaMemoryModel，JMM）来屏蔽各种硬件和操作系统的内存访问差异，以实现让Java程序在各种平台下都能达到一致的内存访问效果。在此之前，主流程序语言（如C和C++等）直接使用物理硬件和操作系统的内存模......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99