重温数据结构系列随笔：单链表（c#模拟实现）
上一节我们讲述了数据结构的基本概念，这一节让我们来讨论下单链表的概念和实现
我从书中简单摘录下单链表概念
简单而言单链表的是通过许多节点构成，每个节点包含2个重要元素：该节点数据（数据域）和指向下个节点的地址（指针域）
这样说太枯燥了，让我们直接用c# 来一步步实现
既然一个节点是由（数据域）和（指针域）构成，那我们简单DIY一个LinkNode类
////// 单链表的节点 /// public class LinkNode { //节点数据域 public object LinkNodeData { get; set; } //自己节点的地址 public Guid SelfAddress { get; set; } //下个节点的地址指针（存储位置） public Guid NextAddress { get; set; } }
继续来了解概念了，既然节点准备好了，那我们要了解节点是怎么通过指针域连接在一起的，看图
图中节点就是一个小矩形，数据域是姓名，指针域就是那个箭头所表示的指向它的后继，头节点h->zhao->Qian->....Wang
这样连接起来就是一个完整的单链表，头结点的数据域可以是任何信息，尾节点的地址域是空（他没有后继节点了）
好，代码中我们只有node 没有LinkTable,那我们就按照上图来建立一个LinkTable类
public class LinkTable { //定义一个LinkNode集合 List list = new List (); public LinkTable() { } /// /// 进行单向链表初始化 /// public void InitialList() { //添加5个节点拥有唯一的guid作为自身地址，后继节点地址为guid.empty for (int i = 0; i < 5; i++) { list.Add ( new LinkNode { LinkNodeData = string.Format("第{0}个节点", i + 1), SelfAddress = Guid.NewGuid(), NextAddress = Guid.Empty } ); } s var j = 0; //将节点的 指针域指向下一个节点的地址 list.ForEach ( (linkNode) => { if (j < list.Count - 1) { linkNode.NextAddress = list.Skip(++j).FirstOrDefault().SelfAddress; } } ); } } 肯定会有朋友问我，那么你怎么在单链表中插入数据或删除数据呢？
非常棒的问题，看图：
图中可以看出a节点的后继是b节点，a节点的指针域指向b节点，那如果在a节点和b节点中添加一个新的节点那情况又如何？
其实图中已经表达出来了，将a的指针域指向新节点，然后将新节点的指针域指向b节点
马上看代码理解
既然是添加节点那我们在LinkTable类中添加方法就行
////// 添加一个新节点 /// /// 节点 /// 在index处添加节点 public void AddNode(LinkNode node, int addIndex) { if (this.list == null || node == null) { // 如果链表为空则初始链表并且添加节点 this.InitialList(); } if (addIndex < 0 || addIndex > list.Count) { throw new IndexOutOfRangeException("removeIndex超出范围"); } var listCount = list.Count; //注意，得到新插入节点的前一个索引位置 var prev = addIndex - 1 <= 0 || listCount <= 0 ? 0 : addIndex - 1; //注意，得到新插入节点的后一个索引位置 var after = listCount <= 0 ? 0 : addIndex > listCount - 1 ? listCount - 1 : addIndex; //插入后前一个节点 var prevNode = list[prev]; //插入后后一个节点 var afterNode = list[after]; //将前一个节点的指针域指向新节点 node.NextAddress = afterNode.SelfAddress; //将新节点的指针域指向后一个节点 prevNode.NextAddress = node.SelfAddress; //判断是否插入到最后一个位置 if (addIndex == list.Count) { node.NextAddress = Guid.Empty; list.Add(node); } else { // 插入新节点 list.Insert(addIndex, node); } }
代码注释能够帮助你了解下添加节点的具体过程，请大家仔细消化下
最后是删除一个节点的情况：
和添加节点正好逆向思维，当我们删除b节点时,我们要将a节点的指针域指向c节点保证我们的单链表不被破坏
删除方法同样写在LinkTable类中
////// 通过索引删除 /// /// ///public void Remove(int removeIndex) { if (this.list == null) { // 如果链表为空则初始链表并且添加节点 this.InitialList(); } if (removeIndex > this.list.Count - 1 || removeIndex < 0) { throw new IndexOutOfRangeException("removeIndex超出范围"); } var preIndex = removeIndex - 1; var afterIndex = removeIndex + 1; var preNode = list[preIndex]; var afterNode = list[afterIndex]; //将被删除节点前后的指针域进行整理 preNode.NextAddress = afterNode.SelfAddress; //删除该节点 list.Remove(list[removeIndex]); }
ok,这就是单链表的一个简单理解，请大家务必牢记，因为后章的循环列表将更复杂，单链表只是一个链表的基础（一以下是完整代码及输出情况）
View Code class Program { static void Main(string[] args) { LinkTable table = new LinkTable(); //初始化 table.InitialList(); //尝试添加一个新节点 table.AddNode ( new LinkNode { LinkNodeData="新节点",NextAddress=Guid.Empty, SelfAddress=Guid.NewGuid()}, 4 ); //删除一个节点 table.Remove(1); var i = 0; //循环显示 table.list.ForEach ( (linkNode) => { if (i ==table.list.Count - 1) { Console.Write("{0} ->{1}", linkNode.LinkNodeData, "Null"); } else { Console.Write("{0} ->", linkNode.LinkNodeData); } i++; } ); Console.ReadLine(); } } /// /// 单链表的节点 /// public class LinkNode { //节点数据域 public object LinkNodeData { get; set; } //自己节点的地址 public Guid SelfAddress { get; set; } //下个节点的地址指针（存储位置） public Guid NextAddress { get; set; } } /// /// 单链表 /// public class LinkTable { //定义一个LinkNode集合 public List list = new List (); public LinkTable() { } /// /// 进行单向链表初始化 /// public void InitialList() { //添加10个节点拥有唯一的guid作为自身地址，后继节点地址为guid.empty for (int i = 0; i < 5; i++) { list.Add ( new LinkNode { LinkNodeData = string.Format("第{0}个节点", i + 1), SelfAddress = Guid.NewGuid(), NextAddress = Guid.Empty } ); } var j = 0; //将节点的 指针域指向下一个节点的地址 list.ForEach ( (linkNode) => { if (j < list.Count - 1) { linkNode.NextAddress = list.Skip(++j).FirstOrDefault().SelfAddress; } } ); } /// /// 添加一个新节点 /// /// 节点 /// 在index处添加节点 public void AddNode(LinkNode node, int addIndex) { if (this.list == null || node == null) { // 如果链表为空则初始链表并且添加节点 this.InitialList(); } if (addIndex < 0 || addIndex > list.Count) { throw new IndexOutOfRangeException("removeIndex超出范围"); } var listCount = list.Count; //注意，得到新插入节点的前一个索引位置 var prev = addIndex - 1 <= 0 || listCount <= 0 ? 0 : addIndex - 1; //注意，得到新插入节点的后一个索引位置 var after = listCount <= 0 ? 0 : addIndex > listCount - 1 ? listCount - 1 : addIndex; //插入后前一个节点 var prevNode = list[prev]; //插入后后一个节点 var afterNode = list[after]; //将前一个节点的指针域指向新节点 node.NextAddress = afterNode.SelfAddress; //将新节点的指针域指向后一个节点 prevNode.NextAddress = node.SelfAddress; //判断是否插入到最后一个位置 if (addIndex == list.Count) { node.NextAddress = Guid.Empty; list.Add(node); } else { // 插入新节点 list.Insert(addIndex, node); } } /// /// 通过索引删除 /// /// /// 输出：
希望大家对单链表有比较深的理解，其实在效率性能上这样的单链表不及数组，因为数组更本没有那么繁琐，
大家在实际项目还是用数组比较好，下章会和大家先补充下c#中的LinkList类和Array类的区别（*数组和链表的区别(很重要)），
然后简单说下循环链表。
敬请期待 ！