前言
参考：B站，尚硅谷数据结构与算法 课程
一、链表（Linked List）介绍
- 用一组任意的存储单元存储线性表的数据元素，这组存储单元可以在内存中未被占用的任意位置。除了存储数据元素信息（data域），还要存储它的后继元素的存储地址（next域），这两部分信息组成了存储映像，称为结点（Node）.
- 几个结点链接成一个链表，当链表中的每个结点只包含一个指针域时，称作单链表。
二、应用实例
1.问题描述
使用带head头的单向链表实现-水浒英雄排行榜管理完成对英雄人物的增删改查操作
1、顺序添加。添加英雄时，直接添加至链表尾部；
2、添加到指定位置；根据排名，将英雄添加到指定位置（若排名已存在，则添加失败）
3、修改结点；
4、删除结点。
2.代码实现
以idea软件为例
1、先创建一个Java文件，命名为SLL,则会自动生成一个名为SLL的类，在该类中写入main函数，在主函数内对以下程序进行测试。
2、创建一个head头结点，作用就是表示单链表的头
//定义一个heronode,每个heronode对象就是一个结点
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()。
//定义SingleLinkedListDemo 管理我们的英雄
class SingleLinkedList {
//先初始化一个头结点
private HeroNode head = new HeroNode(0, "", "");
//功能一：添加结点到单向链表末尾
//1.找到当前链表的最后结点；2、将这个最后结点的next指向新结点
public void add(HeroNode heroNode) {
//找一个辅助结点temp
HeroNode temp = head;
//遍历链表
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = heroNode;
}
//功能二：根据排名将英雄添加到指定位置
//如果有这个编号，则添加失败，给出提示
public void addByOrder(HeroNode heroNode){
//因为头结点不能动，所以需要一个辅助结点来帮助找到需要添加的位置
//因为是单链表，所以我们要找的temp是位于添加位置的前一个结点
HeroNode temp=head;
boolean flag=false; //标志添加的编号是否存在，默认为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("已存在的编号，不能重复添加\n"+heroNode.no);
}else{
//插入到链表中temp的后面
heroNode.next=temp.next;
temp.next=heroNode;
}
}
//功能三：修改结点的信息，根据no编号
public void update(HeroNode newHeroNode){
//判断是否为空
if(head.next==null){
System.out.println("链表为空");
return;
}
//根据no编号，找到需要修改的结点
//定义一个辅助结点
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+"的结点，不能修改");
}
}
//功能四：删除结点
//1、找到需要输出的结点的前一个结点temp；
//2、temp.next=temp.next.next
//3、被删除的结点将不会有其他引用指向，会被垃圾回收机制回收；
public void del(int no){
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.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();
}
}
总结
程序的熟练使用是要经过不断练习的。加油吧，代码人！