004--认识单链表

news/2024/4/23 15:17:10/文章来源:https://blog.csdn.net/m0_56116754/article/details/129209360

一、链表介绍

链表是有序的列表：

链表是以节点的方式来存储，是链式存储
每个节点包含data域：存放数据，next域：指向下一个节点； Head节点：data域不存放具体的数据，作用就是表示单链表表头，next域指向下一个节点；如果next域为空null，则结束
发现链表的各个节点不一定是连续存放的；通过next域来确定下一个节点
链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。

二、单链表创建和遍历

添加（创建）：

先创建一个head头节点，作用就是表示单链表的头
后面我们每添加一个节点，就直接加入到链表的最后
遍历：通过一个辅助变量，帮助遍历整个链表

代码实现

第一种：不考虑编号顺序，直接把添加的放在最后一个元素、

package com.xqh.linklist;public class SingleLinkedListDemo {public static void main(String[] args) {//进行测试，先创建节点HeroNode hero1 = new HeroNode(1,"宋江","及时雨");HeroNode hero2 = new HeroNode(2,"吴用","智多星");HeroNode hero3 = new HeroNode(3,"卢俊义","玉麒麟");HeroNode hero4 = new HeroNode(4,"杨志","青面虎");//创建一个链表SingleLinkedList singleLinkedList = new SingleLinkedList();singleLinkedList.add(hero1);singleLinkedList.add(hero2);singleLinkedList.add(hero3);singleLinkedList.add(hero4);singleLinkedList.list();}}//定义SingleLinkedList  管理我们的英雄
class SingleLinkedList{//先初始化一个头节点，头节点不要动，不存放具体的数据private HeroNode head = new HeroNode(0,"","");//添加节点到单向链表/*思路：当不考虑编号顺序时，直接插入到表尾* 1、找到当前链表的最后节点* 2、将最后这个节点的next 指向 新的节点* */public void add(HeroNode heroNode) {//因为head节点不能动，因此需要一个辅助变量来遍历链表 tempHeroNode temp = head;//遍历链表，找到最后while(true) {//找到链表的最后if(temp.next == null) {break;}//如果没有找到最后，将temp后移temp = temp.next;}//当退出while循环时，temp就指向了链表的最后//将最后这个节点的next指向新的节点temp.next = heroNode;}//显示链表【遍历】public void list() {//判断链表是否为空if(head.next == null) {System.out.println("链表为空");return;}//因为头节点，不能动，因此我们需要一个辅助变量来遍历HeroNode temp = head.next;while(true) {//判断是否到链表最后if(temp==null) {break;}//输出节点的信息System.out.println(temp);//将temp后移temp = temp.next;}}}//定义HeroNode ，每个heroNode 对象就是一个节点
class HeroNode{public int no;public String name;public String nickname;public HeroNode next;  //指向下一个节点//构造器public HeroNode(int no ,String name,String nickname) {this.no = no;this.name = name;this.nickname = nickname;}//显示方法，重写toString@Overridepublic String toString() {return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname +"]";}}

第二种方式：在添加英雄时，根据排名将英雄插入到指定位置（如果有这个排名，则添加失败，并给出提示）

思路：

首先找到新添加的节点的位置，是通过辅助变量

使新的节点.next = temp.next

将temp.next = 新的节点

package com.xqh.linklist;public class SingleLinkedListDemo {public static void main(String[] args) {//进行测试，先创建节点HeroNode hero1 = new HeroNode(1,"宋江","及时雨");HeroNode hero2 = new HeroNode(2,"吴用","智多星");HeroNode hero3 = new HeroNode(3,"卢俊义","玉麒麟");HeroNode hero4 = new HeroNode(4,"杨志","青面虎");//创建一个链表SingleLinkedList singleLinkedList = new SingleLinkedList();//第一种添加
//		singleLinkedList.add(hero1);
//		singleLinkedList.add(hero2);
//		singleLinkedList.add(hero3);
//		singleLinkedList.add(hero4);//第二种添加singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero3);singleLinkedList.addByOrder(hero2);singleLinkedList.list();}}//定义SingleLinkedList  管理我们的英雄
class SingleLinkedList{//先初始化一个头节点，头节点不要动，不存放具体的数据private HeroNode head = new HeroNode(0,"","");//添加节点到单向链表/*思路：当不考虑编号顺序时，直接插入到表尾* 1、找到当前链表的最后节点* 2、将最后这个节点的next 指向 新的节点* */public void add(HeroNode heroNode) {//因为head节点不能动，因此需要一个辅助变量来遍历链表 tempHeroNode temp = head;//遍历链表，找到最后while(true) {//找到链表的最后if(temp.next == null) {break;}//如果没有找到最后，将temp后移temp = temp.next;}//当退出while循环时，temp就指向了链表的最后//将最后这个节点的next指向新的节点temp.next = heroNode;}//第二种添加方式，在添加英雄时，根据排名将英雄插入到指定位置//(如果有这个排名，则添加失败，并给出提示)public void addByOrder(HeroNode heroNode) {//首先头节点不能动，需要通过一个辅助指针来帮助找到添加的位置，因为单链表//因为单链表，因此我们找的temp是位于添加位置的前一个节点，temp从head开始遍历，直到temp.next.no>hero.no//说明，此时hero就应该插在temp和他的下一个之间HeroNode temp = head;boolean flag = false;  //标识添加的编号是否存在，默认为falsewhile(true) {if(temp.next == null) {//说明此时temp位于最末端，直接退出循环break;}else if(temp.next.no>heroNode.no) {//此时就是插入数据的位置在temp和temp.next之间，一大一小在中间插入break;}else if(temp.next.no == heroNode.no) {//说明编号已经存在flag = true;break;}temp = temp.next;  //如果temp.next.no小于heroNode.no,那么没找到插入位置，那么继续遍历temp}//判断flag的值if(flag) {//编号存在，不能添加System.out.printf("准备插入的英雄的编号%d已经存在了，不能加入\n",heroNode.no);			}else {//插入到链表中heroNode.next = temp.next;temp.next = heroNode;}}//显示链表【遍历】public void list() {//判断链表是否为空if(head.next == null) {System.out.println("链表为空");return;}//因为头节点，不能动，因此我们需要一个辅助变量来遍历HeroNode temp = head.next;while(true) {//判断是否到链表最后if(temp==null) {break;}//输出节点的信息System.out.println(temp);//将temp后移temp = temp.next;}}}//定义HeroNode ，每个heroNode 对象就是一个节点
class HeroNode{public int no;public String name;public String nickname;public HeroNode next;  //指向下一个节点//构造器public HeroNode(int no ,String name,String nickname) {this.no = no;this.name = name;this.nickname = nickname;}//显示方法，重写toString@Overridepublic String toString() {return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname +"]";}}

根据排名插入，如果编号已经存在，就无法插入；

三、单链表节点的修改

先遍历链表，找到符合修改节点的编号-----用flag来标识是否查找到符合节点的编号
如果没找到提示信息，如果找到，修改节点信息，使此时temp所指向的节点的name和nickname修改为修改节点的信息

//根据编号修改,定义一个辅助指针HeroNode temp = head.next;boolean flag = false;while(true) {if(temp==null) {break;//已经遍历结束}if(temp.no == newHeroNode.no) {//找到了修改的节点flag = true;break;}temp = temp.next;}if(flag) {temp.name=newHeroNode.name;temp.nickname=newHeroNode.nickname;}else {//没有找到这个节点System.out.printf("没有找到编号为%d的节点,不能修改 \n",newHeroNode.no);}}....//测试singleLinkedList.list();HeroNode newHeroNode = new HeroNode(2,"豹子头","林冲");singleLinkedList.update(newHeroNode);

四、单链表节点的删除

思路：

我们先找到需要删除的这个节点的前一个节点temp
使temp.next = temp.next.next
被删除的节点，将不会有其他引用指向，会被垃圾回收机制回收

//删除节点public void delete(int no) {if(head.next==null) {System.out.println("链表为空，无法删除");return;}HeroNode temp = head;boolean flag = false;while(true) {if(temp.next==null) {break;}if(temp.next.no== no) {flag=true;break;}temp=temp.next;}if(flag) {temp.next=temp.next.next;}else {System.out.printf("你要删除的编号%d，没有找到\n",no);}}