单链表增删改查（实现对水浒人物的增删改查操作）

• 前言
• 一、链表（Linked List）介绍
• 二、应用实例
• • 1.问题描述
  • 2.代码实现
• 总结

前言

参考：B站，尚硅谷数据结构与算法 课程

一、链表（Linked List）介绍

1. 用一组任意的存储单元存储线性表的数据元素，这组存储单元可以在内存中未被占用的任意位置。除了存储数据元素信息（data域），还要存储它的后继元素的存储地址（next域），这两部分信息组成了存储映像，称为结点（Node）.
2. 几个结点链接成一个链表，当链表中的每个结点只包含一个指针域时，称作单链表。

二、应用实例

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();
    }
}

总结

程序的熟练使用是要经过不断练习的。加油吧，代码人！