单链表增删改查(实现对水浒人物的增删改查操作)
前言
参考:B站,尚硅谷数据结构与算法 课程
一、链表(Linked List)介绍
- 用一组任意的存储单元存储线性表的数据元素,这组存储单元可以在内存中未被占用的任意位置。除了存储数据元素信息(data域),还要存储它的后继元素的存储地址(next域),这两部分信息组成了存储映像,称为结点(Node).
- 几个结点链接成一个链表,当链表中的每个结点只包含一个指针域时,称作单链表。
二、应用实例
1.问题描述
使用带head头的单向链表实现-水浒英雄排行榜管理完成对英雄人物的增删改查操作
1、顺序添加。添加英雄时,直接添加至链表尾部;
2、添加到指定位置;根据排名,将英雄添加到指定位置(若排名已存在,则添加失败)
3、修改结点;
4、删除结点。
2.代码实现
以idea软件为例
1、先创建一个Java文件,命名为SLL,则会自动生成一个名为SLL的类,在该类中写入main函数,在主函数内对以下程序进行测试。
2、创建一个head头结点,作用就是表示单链表的头
class HeroNode{
//data域
public int no;
public String name;
public String nickName;
//next域
public HeroNode next; //指向下一个结点
//构造器
public HeroNode(int no,String name,String nickName){
this.no=no;
this.name=name;
this.nickName=nickName;
}
//为了显示方便,重写toString函数
@override
public String toString(){
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
3、定义一个类,管理英雄类,命名为SingleLinkedList。在该类中实现四个功能:按顺序添加add();添加到指定位置addByOrder();修改update();删除del()。实现链表的显示list()。
class SingleLinkedList{
//先初始化一个结点
private HeroNode head=new HeroNode();
//功能一:按顺序添加add()
public void add(HeroNode heroNode){
//找一个辅助结点
HeroNode temp=head;
//遍历链表,找到最后一个结点
while(true){
if(temp.next==null){//已到链表最后
break;
}
temp=temp.next;
}
temp.next=heroNode;
}
//功能二:将结点添加到指定位置
public addByOrder(HeroNode heroNode){
HeroNode temp=head; //辅助结点
boolean flag=false; //标志添加的编号是否存在
while(true){
if(temp.next==null){//已到链表最后
break;
}
if(temp.next.no>heroNode.no){//位置已找到,就在temp后面加入
break;
}
else if(temp.next.no=heroNode.no){
flag=true;
break;
}
temp=temp.next;
}
//判断flag的值
if(flag==true){
System.out.println("编号"+heroNode.no+"已存在,不能添加");
}else{//添加到链表中temp的后面
heroNode.next=temp.next;
temp.next=heroNode;
}
}
//功能三:根据no编号,修改结点
public update(HeroNode newHeroNode){
//判断是否为空
if(head.next==null){
System.out.println("该链表为空");
}
HeroNode temp=head.next;
boolean flag=false;
while(true){
if(temp==null){
break;
}
if(temp.no==newHeroNode.no){
flag=true;
break;
}
temp=temp.next;
}
//根据flag判断是否找到要修改的结点
if(flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
}else{//没有找到
System.out.printf("没有找到编号"+newHeroNode.no+"的结点,不能修改");
}
//功能四:删除结点
public void del(int no){
HeroNode temp=head.next;
boolean flag=false;
while(true){
if(temp==null){
break;
}
if(temp.no==no){
flag=true;
break;
}
temp=temp.next;
}
if(flag==true){
temp.next=temp.next.next;
}else{
System.out.println("该结点不存在");
}
}
//显示链表,遍历
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.next;
}
}
}
4、在SLL类中的主函数里。进行测试
public class SLL {
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);
System.out.println("添加后显示情况");
singlelinkedlist.list();
//测试固定位置添加结点的代码
singlelinkedlist.addByOrder(hero1);
singlelinkedlist.addByOrder(hero4);
singlelinkedlist.addByOrder(hero2);
singlelinkedlist.addByOrder(hero3);
System.out.println("添加后显示情况");
singlelinkedlist.list();
//测试修改结点的代码
HeroNode newHeroNode=new HeroNode(2,"小卢","小尾巴");
singlelinkedlist.update(newHeroNode);
System.out.println("修改后显示情况");
singlelinkedlist.list();
//测试删除一个结点的代码
singlelinkedlist.del(1);
System.out.println("删除后显示情况");
singlelinkedlist.list();
}
}
总结
程序的熟练使用是要经过不断练习的。加油吧,代码人!