devbox
小惠珠哦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】单链表的增删改查

作者：小惠珠哦 | 2024-07-27 07:53:36

赞

踩

【数据结构】单链表的增删改查
介绍

链表是有序的列表，但是它在内存中是如下存储的：

①链表以节点的方式进行存储，是链式存储的

②每个节点包含 data 域、next 域：指向下一节点

③链表的各个节点不一定是连续存放的

④链表分为有头节点的链表和没有头节点的链表 

head节点

1.不存放具体数据

2.作用就是表示单链表头

一、将英雄直接添加到链表尾部
  1. public class SingleLinkedListDemo {
  2.     public static void main(String[] args) {
  3.         //进行一个测试
  4.         //先创建节点
  5.         HeroNode heroNode1 = new HeroNode(1, "孙悟空", "大圣");
  6.         HeroNode heroNode2 = new HeroNode(2, "猪八戒", "老猪");
  7.         HeroNode heroNode3 = new HeroNode(3, "沙悟净", "沙和尚");
  8.         HeroNode heroNode4 = new HeroNode(4, "唐三藏", "唐僧");
  9.  
  10.         //创建一个链表
  11.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  12.         //加入
  13.         singleLinkedList.add(heroNode1);
  14.         singleLinkedList.add(heroNode2);
  15.         singleLinkedList.add(heroNode3);
  16.         singleLinkedList.add(heroNode4);
  17.  
  18.         //显示一把
  19.         singleLinkedList.list();
  20.     }
  21. }
  22.  
  23. //定义StringLinkedList 管理我们的英雄
  24. class SingleLinkedList {
  25.     //先初始化一个头节点，头节点不要动，不存放具体的数据
  26.     private HeroNode head = new HeroNode(0, "", "");
  27.  
  28.     //添加节点到单向链表
  29.     /*
  30.     思路：当不考虑编号顺序时
  31.     1.找到当前链表的最后节点
  32.     2.将最后这个节点的next 指向 新的节点
  33.      */
  34.     public void add(HeroNode heroNode) {
  35.         //因为head节点不能动，因此我们需要一个辅助变量 temp
  36.         HeroNode temp = head;
  37.         //遍历链表，找到最后
  38.         while (true) {
  39.             //找到链表的最后
  40.             if (temp.next == null) {
  41.                 break;
  42.             }
  43.             //如果没有找到链表的最后
  44.             temp = temp.next;
  45.         }
  46.         //当退出while循环时，temp就指向了链表的最后
  47.         temp.next = heroNode;
  48.     }
  49.  
  50.     //显示链表【遍历】
  51.     public void list() {
  52.         //判断链表是否为空
  53.         if (head.next == null) {
  54.             System.out.println("链表为空");
  55.             return;
  56.         }
  57.         //因为头节点不能动，因此我们需要一个辅助节点来遍历
  58.         HeroNode temp = head.next;
  59.         while (true) {
  60.             //输出节点信息
  61.             System.out.println(temp);
  62.             //判断是否到链表最后
  63.             if (temp.next == null) {
  64.                 break;
  65.             }
  66.             //将temp后移，一定小心，否则是死循环
  67.             temp = temp.next;
  68.         }
  69.     }
  70. }
  71.  
  72. //定义一个HeroNode，每个HeroNode 对象就是一个节点
  73. class HeroNode {
  74.     public int no;
  75.     public  String name;
  76.     public String nickname;
  77.     public HeroNode next;  //指向下一节点
  78.     //构造器
  79.     public HeroNode(int no, String name, String nickname) {
  80.         this.no = no;
  81.         this.name = name;
  82.         this.nickname = nickname;
  83.     }
  84.  
  85.     //为了显示方便，我们重写toString方法
  86.     @Override
  87.     public String toString() {
  88.         return "HeroNode{" +
  89.                 "no=" + no +
  90.                 ", name='" + name + '\'' +
  91.                 ", nickname='" + nickname + '\'' +
  92.                 '}';
  93.     }
  94. }
二、将英雄按照排名插入到链表中

1.首先找到新添加的节点的位置，通过辅助指针完成

2.新节点.next = temp.next

3.temp.next = 新节点

  1. public class SingleLinkedListDemo {
  2.     public static void main(String[] args) {
  3.         //进行一个测试
  4.         //先创建节点
  5.         HeroNode heroNode1 = new HeroNode(1, "孙悟空", "大圣");
  6.         HeroNode heroNode2 = new HeroNode(2, "猪八戒", "老猪");
  7.         HeroNode heroNode3 = new HeroNode(3, "沙悟净", "沙和尚");
  8.         HeroNode heroNode4 = new HeroNode(4, "唐三藏", "唐僧");
  9.  
  10.         //创建一个链表
  11.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  12.         //加入
  13. //        singleLinkedList.add(heroNode1);
  14. //        singleLinkedList.add(heroNode2);
  15. //        singleLinkedList.add(heroNode3);
  16. //        singleLinkedList.add(heroNode4);
  17.  
  18.         //按照编号的顺序加入
  19.         singleLinkedList.addByOrder(heroNode4);
  20.         singleLinkedList.addByOrder(heroNode1);
  21.         singleLinkedList.addByOrder(heroNode3);
  22.         singleLinkedList.addByOrder(heroNode2);
  23.  
  24.         //显示一把
  25.         singleLinkedList.list();
  26.     }
  27. }
  28.  
  29. //定义StringLinkedList 管理我们的英雄
  30. class SingleLinkedList {
  31.     //先初始化一个头节点，头节点不要动，不存放具体的数据
  32.     private HeroNode head = new HeroNode(0, "", "");
  33.  
  34.     //添加节点到单向链表
  35.     /*
  36.     思路：当不考虑编号顺序时
  37.     1.找到当前链表的最后节点
  38.     2.将最后这个节点的next 指向 新的节点
  39.      */
  40.     public void add(HeroNode heroNode) {
  41.         //因为head节点不能动，因此我们需要一个辅助变量 temp
  42.         HeroNode temp = head;
  43.         //遍历链表，找到最后
  44.         while (true) {
  45.             //找到链表的最后
  46.             if (temp.next == null) {
  47.                 break;
  48.             }
  49.             //如果没有找到链表的最后
  50.             temp = temp.next;
  51.         }
  52.         //当退出while循环时，temp就指向了链表的最后
  53.         temp.next = heroNode;
  54.     }
  55.  
  56.     //第二种添加英雄的方式
  57.     /*
  58.     根据排名将英雄插入到指定位置
  59.     如果有这个排名，则添加失败，并给出提示
  60.      */
  61.     public void addByOrder(HeroNode heroNode) {
  62.         //因为头节点不能动，因此我们仍然通过一个辅助指针来帮助找到添加的位置
  63.         //因为单链表，因此我们找的 temp 是位于添加位置的前一个节点，否则无法插入
  64.         HeroNode temp = head;
  65.         boolean flag = false; //flag标识添加的编号是否存在，默认为 false
  66.         while (true) {
  67.             if (temp.next == null) {  //说明 temp 已经在链表的最后
  68.                 break;
  69.             }
  70.             if (temp.next.no > heroNode.no) {
  71.                 break;
  72.             } else if (temp.next.no == heroNode.no) {
  73.                 flag = true;  //说明编号存在
  74.                 break;
  75.             }
  76.             temp = temp.next;  //后移，遍历当前链表
  77.         }
  78.         //判断 flag 的值
  79.         if (flag) {  //不能添加，说明编号存在
  80.             System.out.printf("准备插入的英雄编号%d已经存在，不能加入\n", heroNode.no);
  81.         } else {  //插入到链表中，temp的后面
  82.             heroNode.next = temp.next;
  83.             temp.next = heroNode;
  84.         }
  85.     }
  86.  
  87.     //显示链表【遍历】
  88.     public void list() {
  89.         //判断链表是否为空
  90.         if (head.next == null) {
  91.             System.out.println("链表为空");
  92.             return;
  93.         }
  94.         //因为头节点不能动，因此我们需要一个辅助节点来遍历
  95.         HeroNode temp = head.next;
  96.         while (true) {
  97.             //输出节点信息
  98.             System.out.println(temp);
  99.             //判断是否到链表最后
  100.             if (temp.next == null) {
  101.                 break;
  102.             }
  103.             //将temp后移，一定小心，否则是死循环
  104.             temp = temp.next;
  105.         }
  106.     }
  107. }
  108.  
  109. //定义一个HeroNode，每个HeroNode 对象就是一个节点
  110. class HeroNode {
  111.     public int no;
  112.     public  String name;
  113.     public String nickname;
  114.     public HeroNode next;  //指向下一节点
  115.     //构造器
  116.     public HeroNode(int no, String name, String nickname) {
  117.         this.no = no;
  118.         this.name = name;
  119.         this.nickname = nickname;
  120.     }
  121.  
  122.     //为了显示方便，我们重写toString方法
  123.     @Override
  124.     public String toString() {
  125.         return "HeroNode{" +
  126.                 "no=" + no +
  127.                 ", name='" + name + '\'' +
  128.                 ", nickname='" + nickname + '\'' +
  129.                 '}';
  130.     }
  131. }
 三、修改节点的信息
  1. //修改节点的信息，根据编号修改，即编号不能改
  2.     public void update(HeroNode newHeroNode) {
  3.         //判断是否空
  4.         if (head.next == null) {
  5.             System.out.println("链表为空");
  6.             return;
  7.         }
  8.         //根据编号，找到需要修改的节点
  9.         //定义一个辅助变量
  10.         HeroNode temp = head.next;
  11.         boolean flag = false;  //表示是否找到该节点
  12.         while (true) {
  13.              if (temp == null) {
  14.                  break; //已经遍历完链表
  15.              }
  16.              if (temp.no == newHeroNode.no) {
  17.                  //找到
  18.                  flag = true;
  19.                  break;
  20.              }
  21.              temp = temp.next;
  22.         }
  23.         //根据flag 判断是否找到要修改的节点
  24.         if (flag) {
  25.             temp.name = newHeroNode.name;
  26.             temp.nickname = newHeroNode.nickname;
  27.         } else {  //没有找到
  28.             System.out.printf("没有找到编号为%d的节点，不能修改\n", newHeroNode.no);
  29.         }
  30.     }
四、删除节点

从单链表中删除一个节点的思路

1.我们先找到需要删除的节点的前一个节点 temp

2.temp.next = temp.next,next

3.被删除的节点将不会有其他的引用指向，会被垃圾回收机制回收

  1. //删除节点
  2.     /*
  3.     思路
  4.     1.head不能动，因此我们需要一个 temp 辅助节点找到待删除节点的前一个节点
  5.     2.说明：我们在比较时，是 temp.next.no 和 需要删除节点.no 比较
  6.      */
  7.     public void del(int no) {
  8.         HeroNode temp = head;
  9.         boolean flag = false;  //标识是否找到
  10.         while (true) {
  11.             if (temp.next == null) {
  12.                 break;
  13.             }
  14.             if (temp.next.no == no) {
  15.                 //找到了待删除节点的前一个节点
  16.                 flag = true;
  17.                 break;
  18.             }
  19.             temp = temp.next;
  20.         }
  21.         //判断flag
  22.         if (flag == true) {  //找到了
  23.             temp.next = temp.next.next;
  24.         } else {  //没找到
  25.             System.out.printf("编号为%d的节点不存在", no);
  26.         }
  27.     }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小惠珠哦/article/detail/889299
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号