C#学习单向链表和接口 IList&T&
作者：乌龙哈里
平台：Window7 64bit,Visual Studio Community 2015
单向链表元素
定义单向链表操作接口
逐步实现单向链表
前面学习了 IEnumerable&T&、IComparable&T&、ICollection&T& 三个接口，就是为了学习数据结构编程使用。
一、单向链表元素
根据单向链表（Single Linked List）的定义，我们知道链表中的元素 Node 由 数据 和 下一个元素 NextNode 两部分组成。构建如下：
//=====单向链表元素=====
class Node&T&
&&&&public T V
&&&&public Node&T& NextN
该元素的创立应该有不带参数（）和带参数（T value） 两种形式，我们继续补全代码如下：
//=====单向链表元素=====
class Node&T&
&&&&public T V
&&&&public Node&T& NextN
&&&&public Node():this(default(T)){ }
&&&&public Node(T value)
&&&&&&&&Value =
&&&&&&&&NextNode =
不带参数的创立里面有 default(T)，参见 。
二、定义单向链表操作接口
有了元素 Node&T&后，我们要操作它，设想中的操作有 增加、删除、修改、清空、遍历、索引器等，我们看看接口 IColloction&T& 和
IList&T& 的约定，就知道我们要实现
IList&T&。
//======参考 IList&T&===
public interface IList&T& : ICollection&T&
&&&&T this[int index] {}
&&&&int IndexOf(T item);
&&&&void Insert(int index, T item);
&&&&void RemoveAt(int index);
//======参考 ICollection&T&===
public interface ICollection&T& : IEnumerable&T&
&&&& int Count { }
&&&& bool IsReadOnly { }
&&&& void Add(T item);
&&&& void Clear();
&&&& bool Contains(T item);
&&&& void CopyTo(T[] array, int arrayIndex);
&&&& bool Remove(T item);
三、逐步实现单向链表
定义一个单向链表类：
//=====单向链表=====
public class SinglyLinkedList&T& : IList&T&
接下来在VS2015 IDE 的小黄灯泡提示内选实现，让 IDE 帮我们出填空题吧。好长一大串^_^!，共14个方法或属性需要填（以我小菜鸟的经历来看，绝对是我填过最长的一个类）。下来我们只好逐步来实现这个类。
1、加入头元素。先要引入 元素类 Node&T&,把它命名为 head（书本上是这样起名的，本来我想起名叫 root的），按 C# 6.0 的新写法，我们可以直接把它缺省值 =null。刚开始创建链表里面是空的，所以头元素为 null。
//=====单向链表=====
public class SinglyLinkedList&T& : IList&T&
&&&&private Node&T& head =
2、填写 Add(T item) 方法和 int Count{} 属性。由于这是个链表，元素只能直线流动，所以要添加元素只能一个一个遍历到链表最尾端，我们这里加一个计数字段 int _count 。
//=====单向链表=====
public class SinglyLinkedList&T& : IList&T&
&&&&private Node&T& head =
&&&&private int _count = 0;
&&&&//---添加元素并计数
&&&&public void Add(T item)
&&&&&&&&if (head == null)
&&&&&&&&&&&&head = new Node&T&(item);
&&&&&&&&&&&&_count++;
&&&&&&&&else
&&&&&&&&&&&&Node&T& node =
&&&&&&&&&&&&while (node.NextNode != null)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&node = node.NextN
&&&&&&&&&&&&&&&&_count++;
&&&&&&&&&&&&}
&&&&&&&&&&&&node.NextNode = new Node&T&(item);
&&&&//---计数---
&&&&public int Count
&&&&&&&&get { return _ }
好了，终于可以添加元素并开始计数了，实验调用一下，看看是否正确：
static void Main(string[] args)
&&&&SinglyLinkedList&int& slist = new SinglyLinkedList&int&();
&&&&Console.WriteLine($"count: {slist.Count}");
&&&&slist.Add(1);
&&&&slist.Add(2);
&&&&slist.Add(3);
&&&&slist.Add(4);
&&&&Console.WriteLine($"count: {slist.Count}");
//输出结果：
//count: 0
//count: 4
3、实现枚举器，使得可以遍历。能够 Add(T item)后，虽然能加入元素，但我们无法显示出来里面元素的值是多少，这时就要实现 IEnumerable&T& 接口，让它能够遍历显示里面的元素值。
//---实现可枚举
public IEnumerator&T& GetEnumerator()
&&&&Node&T& node =
&&&&Node&T& result = new Node&T&();
&&&&while (node != null)
&&&&&&&&result =
&&&&&&&&node = node.NextN
&&&&&&&&yield return result.V
//---不用填写，只调用上面的
IEnumerator IEnumerable.GetEnumerator()
&&&&throw new NotImplementedException();
接下来调用看看：
Console.Write("elements: ");
foreach (var s in slist) { Console.Write($"{s} "); }
//elements: 1 2 3 4
4、实现清空。只要把 head 设置成null ，并把 计数器归零即可。这里我这个小菜鸟不禁想到没有垃圾收集器的语言，那剩下的元素所占内存怎么释放，难道要先遍历逐个释放？或者数据不放在堆上？算了，我水平太次，不思考超出能力范围的事。
//---清空---
public void Clear()
&&&&head =
&&&&_count = 0;
5、实现规定的 Insert(int index,T item)。意思是在 index 位置上插入一个元素。由于是链表，插入一个新值会破坏掉整个链的连接，我们需要在插入新值前保护现场，即把上个元素和当前元素保存起来，然后把在前个元素的 NextNode 里填写新元素，在新元素的 NextNode 里填写当前元素，这样整个链表又完整了。
//---插入值---
public void Insert(int index, T item)
&&&&if (index &= 0 && index & _count)
&&&&&&&&Node&T& node =
&&&&&&&&Node&T& prev =
&&&&&&&&Node&T& next =
&&&&&&&&//头元素永远是head，所以要专门弄个index=0的特殊
&&&&&&&&if (index == 0)
&&&&&&&&&&&&next =
&&&&&&&&&&&&head = new Node&T&(item);
&&&&&&&&&&&&head.NextNode =
&&&&&&&&else
&&&&&&&&&&&&for (int i = 0; i & i++)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&prev =
&&&&&&&&&&&&&&&&node = node.NextN
&&&&&&&&&&&&}
&&&&&&&&&&&&next =
&&&&&&&&&&&&node = new Node&T&(item);
&&&&&&&&&&&&node.NextNode =
&&&&&&&&&&&&prev.NextNode =
&&&&&&&&_count++;
&&&&else throw new Exception("Out of Range !");
调用检查正确否：
SinglyLinkedList&int& slist = new SinglyLinkedList&int&();
Console.WriteLine($"count: {slist.Count}");
slist.Add(1);
slist.Add(2);
slist.Add(3);
slist.Add(4);
Console.WriteLine($"count: {slist.Count}");
Console.Write("elements: ");
foreach (var s in slist) { Console.Write($"{s} "); }
Console.WriteLine();
slist.Insert(0, 5);
Console.Write("elements: ");
foreach (var s in slist) { Console.Write($"{s} "); }
Console.WriteLine();
Console.WriteLine($"count: {slist.Count}");
Console.ReadKey();
elements: 1 2 3 4
elements: 5 1 2 3 4
如果连 index=0 都能插入值，那我们之前的 Add(T item) 可以视作是 Insert(0,T item)，但是在 Insert 里面有个index 越界的检查，当链表为空的时候， Count=0，会抛出错误。针对这个，我们在 Add(T item) 前先把 Count +1，Insert 后再 Count -1 回去。Add 改造如下：
//---添加元素并计数
public void Add(T item)
&&&&_count++;
&&&&Insert(_count - 1, item);
&&&&_count--;
6、填写 int IndexOf(T item) 方法。后面的方法有 int IndexOf(T item)、bool Remove(T item)、void RemoveAt(int index) 、bool Contains(T item) 和一个索引器，这些都和查找元素有关，而
int IndexOf(T item) 无疑就是一个查找元素位置的方法，所以我们先要实现它。
还有一个问题就是，要查找 T item ，T 必须是可比较类型，所以我们在 SinglyLinkedList 类上加个 T 的约束是符合 IComparable&T& 接口的。
//=====单向链表=====
public class SinglyLinkedList&T& : IList&T& where T : IComparable&T&
//---查找---
public int IndexOf(T item)
&&&&int result = -1;
&&&&Node&T& node =
&&&&for(int i = 0; i & _ i++)
&&&&&&&&if (node.Value.Equals(item))
&&&&&&&&&&&&result =
&&&&&&&&&&&&
&&&&&&&&node = node.NextN
有了 int IndexOf(T item) 这个利器，下来的一些方法填空就简单了。
//---包含---
public bool Contains(T item)
&&&&return IndexOf(item) & -1 ? true :
//---删除---
public void RemoveAt(int index)
&&&&if (index &= 0 && index & _count)
&&&&&&&&Node&T& prev =
&&&&&&&&Node&T& node =
&&&&&&&&if (index == 0)
&&&&&&&&&&&&head = head.NextN
&&&&&&&&else
&&&&&&&&&&&&for (int i = 0; i & i++)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&prev =
&&&&&&&&&&&&&&&&node = node.NextN
&&&&&&&&&&&&}
&&&&&&&&&&&&prev.NextNode = node.NextN
&&&&&&&&_count--;
&&&&else throw new Exception("Out of Range !");
//---删除---
public bool Remove(T item)
&&&&int n = IndexOf(item);
&&&&if (n & 0) { }
&&&&RemoveAt(n);
7、完成索引器。索引器见参考。下来具体实现：
//---索引器
public T this[int index]
&&&&&&&&if (index &= 0 && index & _count)
&&&&&&&&&&&&Node&T& node =
&&&&&&&&&&&&for(int i = 0; i &i++)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&node = node.NextN
&&&&&&&&&&&&}
&&&&&&&&&&&&return node.V
&&&&&&&&else throw new Exception("Out of Range !");
&&&&&&&&Insert(index,value);
8、实现拷贝功能:
public void CopyTo(T[] array, int arrayIndex)
&&&&Node&T& node =
&&&&for(int i = 0; i & _ i++)
&&&&&&&&array[arrayIndex + i] = node.V
&&&&&&&&node = node.NextN
至此，整个单向链表和 IList&T& 接口就学习好了。附完成源程序：
//=====单向链表=====
public class SinglyLinkedList&T& : IList&T& where T : IComparable&T&
&&&&private Node&T& head =
&&&&private int _count = 0;
&&&&//---添加元素并计数---
&&&&public void Add(T item)
&&&&&&&&_count++;
&&&&&&&&Insert(_count - 1, item);
&&&&&&&&_count--;
&&&&//---计数---
&&&&public int Count
&&&&&&&&get { return _ }
&&&&//---实现可枚举
&&&&public IEnumerator&T& GetEnumerator()
&&&&&&&&Node&T& node =
&&&&&&&&Node&T& result = new Node&T&();
&&&&&&&&while (node != null)
&&&&&&&&&&&&result =
&&&&&&&&&&&&node = node.NextN
&&&&&&&&&&&&yield return result.V
&&&&//---不用填写，只调用上面的
&&&&IEnumerator IEnumerable.GetEnumerator()
&&&&&&&&throw new NotImplementedException();
&&&&//---清空---
&&&&public void Clear()
&&&&&&&&head =
&&&&&&&&_count = 0;
&&&&//---插入值---
&&&&public void Insert(int index, T item)
&&&&&&&&if (index &= 0 && index & _count)
&&&&&&&&&&&&Node&T& node =
&&&&&&&&&&&&Node&T& prev =
&&&&&&&&&&&&Node&T& next =
&&&&&&&&&&&&//头元素永远是head，所以要专门弄个index=0的特殊
&&&&&&&&&&&&if (index == 0)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&next =
&&&&&&&&&&&&&&&&head = new Node&T&(item);
&&&&&&&&&&&&&&&&head.NextNode =
&&&&&&&&&&&&}
&&&&&&&&&&&&else
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&for (int i = 0; i & i++)
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&prev =
&&&&&&&&&&&&&&&&&&&&node = node.NextN
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&next =
&&&&&&&&&&&&&&&&node = new Node&T&(item);
&&&&&&&&&&&&&&&&node.NextNode =
&&&&&&&&&&&&&&&&prev.NextNode =
&&&&&&&&&&&&}
&&&&&&&&&&&&_count++;
&&&&&&&&else throw new Exception("Out of Range !");
&&&&//---查找---
&&&&public int IndexOf(T item)
&&&&&&&&int result = -1;
&&&&&&&&Node&T& node =
&&&&&&&&for (int i = 0; i & _ i++)
&&&&&&&&&&&&if (node.Value.Equals(item))
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&result =
&&&&&&&&&&&&&&&&
&&&&&&&&&&&&}
&&&&&&&&&&&&node = node.NextN
&&&&//---包含---
&&&&public bool Contains(T item)
&&&&&&&&return IndexOf(item) & -1 ? true :
&&&&//---删除---
&&&&public void RemoveAt(int index)
&&&&&&&&if (index &= 0 && index & _count)
&&&&&&&&&&&&Node&T& prev =
&&&&&&&&&&&&Node&T& node =
&&&&&&&&&&&&if (index == 0)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&head = head.NextN
&&&&&&&&&&&&}
&&&&&&&&&&&&else
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&for (int i = 0; i & i++)
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&prev =
&&&&&&&&&&&&&&&&&&&&node = node.NextN
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&prev.NextNode = node.NextN
&&&&&&&&&&&&}
&&&&&&&&&&&&_count--;
&&&&&&&&else throw new Exception("Out of Range !");
&&&&//---删除---
&&&&public bool Remove(T item)
&&&&&&&&int n = IndexOf(item);
&&&&&&&&if (n & 0) { }
&&&&&&&&RemoveAt(n);
&&&&//---索引器---
&&&&public T this[int index]
&&&&&&&&get
&&&&&&&&&&&&if (index &= 0 && index & _count)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&Node&T& node =
&&&&&&&&&&&&&&&&for (int i = 0; i & i++)
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&node = node.NextN
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&return node.V
&&&&&&&&&&&&}
&&&&&&&&&&&&else throw new Exception("Out of Range !");
&&&&&&&&set
&&&&&&&&&&&&Insert(index, value);
&&&&//---只读？---
&&&&public bool IsReadOnly
&&&&&&&&get { }
&&&&//---拷贝---
&&&&public void CopyTo(T[] array, int arrayIndex)
&&&&&&&&Node&T& node =
&&&&&&&&for (int i = 0; i & _ i++)
&&&&&&&&&&&&array[arrayIndex + i] = node.V
&&&&&&&&&&&&node = node.NextN
//=====单向链表元素=====
class Node&T&
&&&&public T V
&&&&public Node&T& NextN
&&&&public Node() : this(default(T)) { }
&&&&public Node(T value)
&&&&&&&&Value =
&&&&&&&&NextNode =
阅读(...) 评论()利用C#的指针编写都一个简单链表 - 开源中国社区
当前访客身份：游客 [
当前位置：
发布于 日 16时,
初学C#，写都比较粗糙，主要是为理解C#都不安全代码块的特性，编译都时候要在项目属性里允许编译不安全代码
代码片段(1)
1.&[代码][C#]代码&&&&
namespace UnsafeTest
unsafe struct link
public link*
class Program
static unsafe void Main(string[] args)
link* head = stackalloc link[sizeof(link)];
for(int i=0;i&=10;i++)
val = i+100;
link* temp = stackalloc link[sizeof(link)];
while(t-&next!=null)
Console.WriteLine(t-&x );
开源中国-程序员在线工具：
相关的代码(448)
错误 1 不安全代码只会在使用 /unsafe 编译的情况下出现&
开源从代码分享开始
南沙县令的其它代码> 博客详情
摘要: 一个最简单的链表类
一、关于C#链表
C#链表可用类LinkedList来存放。本文中的类MyLinkedList只是实现了该类的最基本的功能。C#中没有指针，但因为C#中类在赋值时传递的是地址，因此仍然可以利用这点制作一个链表。
二、结点类Node和链表类MyLinkedList代码
/// &summary&
/// 链表结点
/// &/summary&
class Node
//结点数据，前后结点
public object D
public Node PreviousN
public Node NextN
//构造函数
public Node(object data = null)
PreviousNode =
NextNode =
//输出结点信息
public override string ToString()
return Data.ToString();
/// &summary&
/// 链表类
/// &/summary&
class MyLinkedList
//首结点、尾结点
public Node F
public Node L
//下一个结点、上一个结点
public Node NextNode(Node n) { return n.NextN }
public Node PreviousNode(Node n) { return n.PreviousN }
//结点总数
public int C
//构造函数
public MyLinkedList()
this.First =
this.Last =
Count = 0;
/// &summary&
/// 在结点node1之后增加结点node2，如果没有该结点则在最后增加
/// &/summary&
/// &param name="node1"&结点1&/param&
/// &param name="node2"&结点2&/param&
public void AddAfter(Node node1, Node node2)
//链表为空的情况
if (First == null)
Console.WriteLine("Linked-list is null! Can not find node1(" + node1 + ")");
Node temp = F
if (temp.Data.Equals(node1.Data))
//如果node1是尾结点
if (node1.NextNode == null)
node2.NextNode =
node2.PreviousNode = node1;
node1.NextNode = node2;
else //如果node1不是尾结点
node2.NextNode = node1.NextN
node2.PreviousNode = node1;
node2.NextNode.PreviousNode = node2;
node1.NextNode = node2; ;
Console.WriteLine("Node(" + node2 + "): Add Complete!");
temp = temp.NextN
while (temp != null);
Console.WriteLine("Can not find node(" + node1 + "), Misson defeat");
/// &summary&
/// 在链表尾部增加结点
/// &/summary&
public void AddLast(Node node)
//链表为空的情况
if (this.First == null)
node.NextNode =
node.PreviousNode =
this.First =
this.Last =
else //链表不为空的情况
Node temp = F
while(temp.NextNode != null)
temp = temp.NextN
temp.NextNode =
node.PreviousNode =
Console.WriteLine("Node(" + node + "): Add Complete!");
/// &summary&
/// 删除指定结点
/// &/summary&
/// &param name="node"&被删除结点&/param&
public void Delete(Node node)
if (Count == 0)
Console.WriteLine("Can not find node(" + node + ")");
Node temp = F
//如果数据部分匹配，则删去该结点
if (temp.Data.Equals(node.Data))
//temp是尾结点
if (temp.NextNode == null)
temp.PreviousNode.NextNode =
else //temp不是尾结点
temp.PreviousNode.NextNode = temp.NextN
temp.NextNode.PreviousNode = temp.PreviousN
Console.WriteLine("Node(" + node + "): Delete Complete!");
temp = temp.NextN
while (temp != null);
Console.WriteLine("Can not find node(" + node + "), Misson defeat");
/// &summary&
/// 修改结点值
/// &/summary&
/// &param name="node"&被修改结点&/param&
/// &param name="value"&结点值&/param&
public void Modify(Node node, object value)
if (Count == 0)
Console.WriteLine("Can not find node(" + node + ")");
Node temp = F
if (temp.Data.Equals(node.Data))
Console.WriteLine("Node: " + temp.Data + " → " + value.ToString());
temp.Data =
temp = temp.NextN
while (temp != null);
/// &summary&
/// 打印链表
/// &/summary&
public void Print()
if (First == null)
Console.WriteLine("No nodes in this linked-list.");
Console.WriteLine("Print the linked-list...");
Node temp = F
Console.WriteLine(temp.ToString());
temp = temp.NextN
while (temp != null);
Console.WriteLine("Mission Complete!");
三、Main函数的调用示例
static void Main(string[] args)
MyLinkedList ll = new MyLinkedList();
//添加三个结点 1 2（在1后） 3（在2后）
Node n1 = new Node("node1");
Node n2 = new Node("node2");
Node n3 = new Node("node3");
ll.AddLast(n1);
ll.AddLast(n2);
ll.AddLast(n3);
//添加三个结点 1.5（在1后） 2.5（在2后） 3.5（在3后）
Node n1dot5 = new Node("node1dot5");
Node n2dot5 = new Node("node2dot5");
Node n3dot5 = new Node("node3dot5");
ll.AddAfter(n1, n1dot5);
ll.AddAfter(n2, n2dot5);
ll.AddAfter(n3, n3dot5);
Console.WriteLine("========================");
//打印链表
ll.Print();
Console.WriteLine("========================");
//删除结点 2 和 3，将结点 2.5 的值改为 "ThisNodeIsModified!"
ll.Delete(n2);
ll.Delete(n3);
ll.Modify(n2dot5, "ThisNodeIsModified!");
Console.WriteLine("========================");
//打印链表
ll.Print();
Console.ReadLine();
四、运行结果
人打赏支持
开源项目作者
领取时间：
作为一个开源项目作者，是时候站出来拯救世界了！
领取条件：开源项目被开源中国收录的开发者可领取
参与源创会
领取时间：
“”在线下联结了各位 OSCer，推广开源项目和理念，很荣幸有你的参与~
领取条件：参与过开源中国“源创会”的 OSCer 可以领取
码字总数 451390
支付宝支付
微信扫码支付
打赏金额: ￥
已支付成功
打赏金额: ￥}