单向链表队列问题

单向链表队列问题

链表（Linked List）是一种常见的数据结构，它以节点（Node）的方式来保存数据，并用指针将它们连接在一起，形成一条链。每个节点包括两个部分：data，保存数据的区域，和next，指向下一个节点的指针。

相对于数组，链表有以下优势：

1. 插入和删除元素方便，只需要修改相邻节点的指针即可，不需要移动其他元素。

2. 由于链表不需要连续的内存空间，因此比数组更灵活。

但是，链表在以下情况下劣于数组：

1. 访问链表的某个元素，需要从头节点开始遍历，因此访问元素的时间复杂度为O(n)。

2. 链表需要额外的内存空间来存储指针，比起数组需要更多的空间开销。

常见的链表包括单向链表（每个节点只有一个next指针）、双向链表（每个节点有一个prev指针和一个next指针），还有循环链表等。链表广泛应用于操作系统、编译器、数据库等领域。

假设我们想用链表来管理梁山好汉的数据，可以定义一个名为`HSNode`的节点结构体，如下所示：

struct HSNode {int id;std::string name;HSNode* next;
};

这个结构体定义了每个梁山好汉节点所需要的数据信息：`id`代表编号，`name`代表姓名，`next`是一个指向下一个节点的指针。我们可以根据需要添加更多的字段，比如年龄、技能等。

然后，我们需要定义链表的操作。一个链表包含一个头节点，头节点也是一个HSNode节点，但是它不存储梁山好汉的具体数据信息。其作用是只是用于标识这个链表的开头。我们可以定义一个名为`HSList`的链表类来进行操作：

class HSList {
public:HSList();  // 构造函数void addHS(int id, std::string name);  // 添加一个梁山好汉void removeHS(int id);  // 删除一个梁山好汉void showAllHS();  // 显示所有梁山好汉信息HSNode* findHS(int id);  // 查找指定编号的梁山好汉节点，并返回其指针
private:HSNode* head;  // 头节点指针
};

在这个定义中，`addHS`函数用于在链表的末尾添加一个梁山好汉节点；`removeHS`函数用于删除指定编号的梁山好汉节点；`showAllHS`函数用于显示所有梁山好汉节点的信息；`findHS`函数用于查找指定编号的梁山好汉节点，并返回其指针。

在`HSList`的成员函数中，我们需要维护链表的头指针和尾指针。以`addHS`函数为例，该函数需要为链表添加一个新的梁山好汉节点，我们需要做以下工作：

1. 判断头指针是否为空。如果为空，则将新节点作为头节点，否则跳到2。

2. 找到链表的尾节点，将新节点接在尾节点的next处。

在`removeHS`函数中，我们需要遍历链表找到指定编号的梁山好汉节点，并将其从链表中删除。在`showAllHS`函数中，我们需要遍历整个链表，并将每个节点的信息打印出来。在`findHS`函数中，我们也需要遍历链表，找到指定编号的梁山好汉节点，并返回其指针。

上面，我们使用C语言做了一个大概的描述和介绍！

下面，我们使用Java程序对于该代码做一个非常仔细的实现

package com.success.day02;import org.junit.Test;/*** @Description 单链表代码实现小案例*/
public class SingleLinkedListDemo {/*** @Description 测试主函数* 不按照序号*/@Testpublic void singleLinkedList() {//创建节点，初始化数据填充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.addHero(hero1);singleLinkedList.addHero(hero2);singleLinkedList.addHero(hero3);singleLinkedList.addHero(hero4);System.out.println("无序输出——原链表");System.out.println("=======================================================");singleLinkedList.list();System.out.println("=======================================================");//添加新的数据HeroNode newHero = new HeroNode(4, "林冲", "豹子头");singleLinkedList.addHero(newHero);System.out.println("无序输出——新链表");System.out.println("=======================================================");singleLinkedList.list();System.out.println("=======================================================");//测试修改节点的代码HeroNode newHero2 = new HeroNode(1, "宋江-宋押司", "及时雨");singleLinkedList.update(newHero2);System.out.println("无序输出——修改链表");System.out.println("=======================================================");singleLinkedList.list();System.out.println("=======================================================");}/*** @Description 测试主函数* 按照序号*/@Testpublic void singleLinkedListOrder() {//创建节点，初始化数据填充HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");HeroNode hero3 = new HeroNode(3, "吴用", "智多星");HeroNode hero4 = new HeroNode(8, "杨志", "青面兽");SingleLinkedList singleLinkedListOrder = new SingleLinkedList();singleLinkedListOrder.addHero(hero1);singleLinkedListOrder.addHero(hero2);singleLinkedListOrder.addHero(hero3);singleLinkedListOrder.addHero(hero4);System.out.println("有序输出——原链表");System.out.println("=======================================================");singleLinkedListOrder.list();System.out.println("=======================================================");//添加新的节点HeroNode newHero = new HeroNode(4, "林冲", "豹子头");singleLinkedListOrder.addHeroByOrder(newHero);System.out.println("有序输出——新链表");System.out.println("=======================================================");singleLinkedListOrder.list();System.out.println("=======================================================");//测试修改节点的代码HeroNode newHero2 = new HeroNode(1, "宋江-宋押司", "及时雨");singleLinkedListOrder.update(newHero2);System.out.println("无序输出——修改链表");System.out.println("=======================================================");singleLinkedListOrder.list();System.out.println("=======================================================");}}/*** @Description 定义链表*/
class HeroNode {public int no; //英雄编号public String name; //英雄名字public String nickName; //英雄昵称public HeroNode next;   //指向像一个节点public int getNo() {return no;}public void setNo(int no) { = no;}public String getName() {return name;}public void setName(String name) {this.name = name;}public String getNickName() {return nickName;}public void setNickName(String nickName) {this.nickName = nickName;}public HeroNode(int no, String name, String nickName) { = no;this.name = name;this.nickName = nickName;}@Overridepublic String toString() {return "HeroNode{" + "no=" + no + ", name='" + name + ''' + ", nickName='" + nickName + ''' + '}';}
}/*** @Description 链表管理器*/
class SingleLinkedList {//初始化一个头节点，头节点不动，不存放具体数据private HeroNode head = new HeroNode(0, "", "");/*** @param heroNode 英雄节点* @Description 添加节点到链表 (无需考虑编号顺序)* 思路：* 不考虑编号顺序，直接找到最后一个节点，直接加入就可以*/public void addHero(HeroNode heroNode) {//head节点不能动，借用遍历到达最后一个节点，然后加入数据HeroNode temp = head;//遍历列表，找到最后一个节点while (true) {//找到链表的最后if ( == null) {break;}//如果节点不为空，就寻找下一个节点，找到最后一个空节点停止temp = ;}//当退出while循环的时候，temp就指向了那个空的节点,然后把数据填入 = heroNode;}/*** @param heroNode 英雄节点* @Description 添加节点到链表 (需考虑编号顺序)* 思路：* 1.考虑编号顺序，遍历找到节点编号大于插入节点编号的数据* 2.然后指针前移，将此数据插入，原节点数据后移*/public void addHeroByOrder(HeroNode heroNode) {//头节点不动，定义一个临时变量进行遍历// 此方法明显区别于之前的添加方法，之前的方法只是负责插入，不进行排序，此方法考虑顺序插入HeroNode temp = head;boolean flag = false; //此变量用来判断编号是否已经存在，默认不存在while (true) {//已经到达最后一个链表，说明两种情况//1.链表为空//2.该编号数据就是最后一个if ( == null) {break;}//找到了插入点//注意，此刻的temp到底存放的是什么，不要把自己搞混了if ( > ) {break;} else if ( == ) {//说明编号已经存在，就不能插入flag = true;break;}temp = ; //后移，遍历当前链表}if (flag) {System.out.println("对不起，插入数据编号重复，请确认数据正确性！！！");} else {//将数据添加到链表 = ; = heroNode;}}/*** @Description 修改节点信息，根据 no 编号来修改* 注意：* 以no编号作为检索条件，所以，此编号不能修改*/public void update(HeroNode newHero) {//判断是否为空if ( == null) {System.out.println("链表为空~");return;}//找到需要修改的节点，根据no编号,此处仍然定义一个辅助变量进行遍历HeroNode temp = ;boolean flag = false;while (true) {//判断是否遍历完毕，遍历完毕就退出if (temp == null) {break;}if ( == ) {//找到节点flag = true;break;}temp = ;}//根据flag判断是不是找到了要修改的节点if (flag) {temp.name = newHero.name;temp.nickName = newHero.nickName;} else {//没有找到System.out.println("对不起，该编号的英雄不存在！！！");}}/*** @Description 删除节点* 依旧和上面的一样，head不动，定义一个辅助变量去进行迭代* 找到符合要求的节点进行数据更替*/public void del(int no) {HeroNode temp = head;//标志是否找到待删除节点boolean flag = false;while (true) {//已经到达链表最后if ( == null) {break;}if ( == no) {//找到待删除节点的前一个节点tempflag = true;break;}//后移，继续进行遍历temp = ;}//判断是不是找到·需要修改的节点if (flag) {//直接越过了找到的节点数据，将其进行更替 = ;} else {System.out.println("需要删除的节点数据不存在！！！");}}/*** @Description 显示列表数据*/public void list() {//判断列表是否为空if ( == null) {System.out.println("链表为空！！！");return;}//遍历列表数据，进行输出HeroNode temp = ;while (true) {if (temp == null) {break;}System.out.println(temp);temp = ;}}
}

最后，再次感谢尚硅谷，受益匪浅，此处属于迁移学习！！！