C#数据结构与算法系列（四）：链表——单链表（Single-LinkedList）
1.介绍：
链表是有序的列表，但是它在内存的存储如下：
链表是以节点的方式来存储，链式存储
每一个节点包含data域，next域：指向下一个节点
链表的各个节点不一定是连续存储
链表分带头节点的链表和不带头节点的链表，根据实际的需求来确定
单链表（带头节点）
2.应用实例
使用带head头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作
第一种方法在添加英雄时，直接添加到链表的尾部
第二种方式在添加英雄时，根据排名将英雄插入到指定位置
(如果有这个排名，则添加失败，并给出提示)
第一种方式思路
第二种思路
删除思路
代码：
public class HeroNode { public HeroNode(int id, string name, string nickName) { this.Id = id; this.Name = name; this.NickName = nickName; } public int Id { get; set; } public string Name { get; set; } public string NickName { get; set; } public HeroNode Next { get; set; } public override string ToString() { return base.ToString(); } }
public class SingleLinkedList { private HeroNode head = null; public SingleLinkedList() { //初始化头节点，头节点不要动，不存放具体的数据 head = new HeroNode(0, "", ""); } /// <summary> /// 添加节点 /// </summary> /// <param name="heroNode"></param> public void Add(HeroNode heroNode) { //因为head节点不能动，因此我们需要一个辅助遍历temp var temp = head; while (true) { //找到链表的最后 if (temp.Next == null) break; temp = temp.Next; } //当退出while循环时，temp就指向了链表的最后 //将最后的这个节点的next指向新的节点 temp.Next = heroNode; } /// <summary> /// 按Id顺序添加节点 /// </summary> /// <param name="heroNode"></param> public void AddById(HeroNode heroNode) { //因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置 //因为是单链表，我们找的temp是位于添加位置的前一个节点，否则插入不了 var temp = head; //定义一个flag，标志添加的Id是否存在，默认为false bool flag = false; while (true) { //说明temp已经在链表的最后 if (temp.Next == null) break; //位置找到，就在temp的后面插入 if (temp.Next.Id > heroNode.Id) break; //说明希望存入的节点已存在 if (temp.Next.Id == heroNode.Id) { //说明Id已经存在 flag = true; break; } //后移，遍历当前链表 temp = temp.Next; } //说明Id已经存在 if (flag) Console.WriteLine($"{heroNode.Id}节点已存在"); else { //把原本存在的节点，存入新的节点后面 heroNode.Next = temp.Next; //把新的节点插入到链表中，temp后面 temp.Next = heroNode; } } /// <summary> /// 更新节点 /// </summary> /// <param name="heroNode"></param> public void Update(HeroNode heroNode) { var temp = head.Next; bool flag = false; //if (temp == null) Console.WriteLine("链表为空"); //else //{ while (true) { if (temp == null) break; //找到节点 if (temp.Id==heroNode.Id) { flag = true; break; } temp = temp.Next; } if (flag) { temp.Name = heroNode.Name; temp.NickName = heroNode.NickName; } else Console.WriteLine($"没有找到Id:{heroNode.Id}的节点"); //} } /// <summary> /// 删除节点 /// </summary> /// <param name="id"></param> public void Delete(int id) { var temp = head; bool flag = false; while (true) { if (temp.Next == null) break; //已经到了链表的最后 //找到待删除节点的前一个节点 if(temp.Next.Id==id) { flag = true; break; } temp = temp.Next; } //将待删除的前一个节点前指向待删除的后一个节点 if (flag) temp.Next = temp.Next.Next; else Console.WriteLine("未找到节点"); } public void GetList() { var temp = head.Next; //if (temp == null) Console.WriteLine("链表为空"); //else //{ while (true) { if (temp == null) break; Console.WriteLine($"id={temp.Id},name={temp.Name},nickName={temp.NickName}"); temp = temp.Next; } //} } public static void Test() { HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨"); HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星"); HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头"); SingleLinkedList singleLinkedList = new SingleLinkedList(); //singleLinkedList.Add(heroNode1); //singleLinkedList.Add(heroNode2); //singleLinkedList.Add(heroNode3); //singleLinkedList.Add(heroNode4); singleLinkedList.AddById(heroNode1); singleLinkedList.AddById(heroNode4); singleLinkedList.AddById(heroNode3); singleLinkedList.AddById(heroNode2); singleLinkedList.Delete(3); singleLinkedList.Update(new HeroNode(2, "李逵", "黑旋风")); singleLinkedList.GetList(); } }
版权声明：本文为vic-tory原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。