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