【 C# 】（一） ------------- 泛型带头节点的单链表，双向链表实现

在编程领域，数据结构与算法向来都是提升编程能力的重点。而一般常见的数据结构是链表，栈，队列，树等。事实上C#也已经封装好了这些数据结构，在头文件 System.Collections.Generic 中，直接创建并调用其成员方法就行。不过我们学习当然要知其然，亦知其所以然。

本文实现的是链表中的单链表和双向链表，并且实现了一些基本方法

一. 定义一个链表接口 MyList

接口里声明了我们要实现的方法：

 interface MyList<T> { int GetLength(); //获取链表长度 void Clear(); //清空链表 bool IsEmpty(); //判断链表是否为空 void Add(T item); //在链表尾部添加新节点 void AddPre(T item,int index); //在指定节点前添加新节点 void AddPost(T item,int index); //在指定节点后添加新节点 T Delete(int index); //按索引删除节点 T Delete(T item,bool isSecond = true); //按内容删除节点，如果有多个内容相同点，则删除第一个 T this[int index] { get; } //实现下标访问 T GetElem(int index); //根据索引返回元素 int GetPos(T item); //根据元素返回索引地址 void Print(); //打印 }

 

二. 实现单链表

 

2.1 节点类

先定义一个单链表所用的节点类，Node。而且我们要实现泛型

先定义一个数据域和下一节点（“Next”），并进行封装，然后给出数个重载构造器。这一步比较简单，这里直接给出代码

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 线性表 { /// <summary> /// 单向链表节点 /// </summary> /// <typeparam name="T"></typeparam> class Node<T> { private T data; //内容域 private Node<T> next; //下一节点 public Node() { this.data = default(T); this.next = null; } public Node(T value) { this.data = value; this.next = null; } public Node(T value,Node<T> next) { this.data = value; this.next = next; } public T Data { get { return data; } set { data = value; } } public Node<T> Next { get { return next; } set { next = value; } } } } 

 

2.2 链表类

创建一个链表类，命名为 LinkList 并继承 MyList。 

​

 先定义一个头结点，尾节点和一个 count；

​ 

其中，head 表示该链表的头部，不包含数据；

           tail 表示尾节点，指向该链表最后一个节点，当链表中只有 head 时，tail 指向 head。定义 tail 会方便接下来的操作

           count 用来表示该链表中除了 head 以外的节点个数

 

构造函数：

 /// <summary> /// 构造器 /// </summary> public LinkList() { head = new Node<T>(); tail = head; count = 0; }

在我们实现成员函数之前，先实现两个特别的方法，因为在许多的成员方法中都要做两个操作：

• 判断索引 index 是否合法，即是否小于0或者大于当前链表的节点个数
• 寻找到 index 所代表的节点

 

①. 判断索引是否合法，然后可以根据其返回的数值进行判断操作

 ​

 

②. 寻找节点。

​ 

定义这两个方法主要是它们的重复使用率高，所以把它们的代码抽出来。

 相对于数组，链表的插入与删除更方便，而查找却更加费时，一般都是从头结点开始遍历链表，时间复杂度为 O(n) ，而跳跃链表则会对查询进行优化，当然这会在下一篇中详述。现在继续来实现成员方法。

 

1. 获取链表长度

​ 

 这个方法实际上是比较简单的，因为 count 会随着添加，删除等操作自动增减，所以直接返回 count 就相当于 链表长度。

需要注意的是，本文中的 count 是不计算空头结点的，即 head 不会计算入内

 

2. 清空链表

​

这里要注意对 tail 的操作，而 head.Next 原本所指的节点不再被引用后，会被GC自动回收

 

3. 判断链表是否为空

因为本文实现的链表是带空头结点的，所以这里认为，当除了头结点外没有别的节点时，则为空链表

 ​

 

4. 在链表尾部添加节点

在链表尾添加节点一般考虑两种情况：

• 当前除了头结点没有别的节点，此时相当于创建第一个节点
• 寻找到最后一个节点

对于带空头结点的链表来说，这两种情况有着一样的操作，只不过第一种情况要多做一步：让 head 指向新创建的节点

​ 

定义了 tail 节点省去了 遍历寻找最后节点的步骤，如果此时是空链表的话，tail 则指向 head

 

5. 在指定索引的前或后添加节点

这两个方法的思路实际上相差无几的

 ​

如图，当 index 为 F 时：

• AddPost： ① 找到 F 节点 ②创建 NEW 节点；③ NEW 节点指向 G；④ F 指向 NEW 节点
• AddPre   :  ① 找到 E 节点 ②创建 NEW 节点；③ NEW 节点指向 F ；④ E 指向 NEW 节点

 AddPre 相当于 index - 1 处的 AddPost；AddPost 相当于 index + 1 处的 AddPre（当然，这是在 index -1 与 index + 1 合法的情况下）

​ 

  ​

 

6. 两种删除节点方法

• 按索引删除：找到索引所指节点，删除
• 按元素删除：找元素所在的索引；当找不到该元素时表明链表中不存在应该删除的节点，不执行删除操作；当链表中存在多个相同的元素时，找到并删除第一个

​

 

两种删除方法操作都是相似的，只是搜索节点的方法不同，删除时要严格注意节点间指向的，即注意书写代码时的顺序

 

​ 

 ​

 

 7. 实现下标访问

这是个比较有趣的实现。前文说过对比于数组，链表胜于增减，弱于访问。对链表实现下标式访问，虽然它的内核依然是遍历链表，然后返回节点，但在使用上会方便许多，如同使用数组一般。

​

 

8. 根据索引返回元素

这个和 GetNode 方法一致

​

 

9. 根据元素返回索引地址

​ 

这个方法也是比较简单的，只是需要注意的一点是：while循环条件中 && 号两端的条件不能调换位置。因为如果调换位置后，当链表遍历到最后一个节点仍没找到元素时，pstr 会被赋值下一节点（此时为NULL），然后循环继续执行，执行到 ！pstr.Data.Equals(item) 这一句时会报空指针，因为此时 pstr 就是空指针；还有因为这是泛型，所以判断两个值是否相等不能用 == 号，除非你重载 == 号。

 

10.打印链表

​

 

至此，所以的成员方法都实现了，先来测试一下。

1

.​

 ​

 ​

​ 

 

其它功能读者可以自行测试，完整代码：

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 线性表 { class LinkList<T> : MyList<T> { private Node<T> head; //头结点 private Node<T> tail; //尾节点 private int count; //节点个数 /// <summary> /// 构造器 /// </summary> public LinkList() { head = new Node<T>(); tail = head; count = 0; } /// <summary> /// 实现下标访问法 /// </summary> /// <param name="index"></param> /// <returns></returns> public T this[int index] { get { int i = IsIndexVaild(index); if(i == -1) return default(T); int k = 0; Node<T> pstr = head; while (k++ < index ) { pstr = pstr.Next; } return pstr.Data; } } /// <summary> /// 在链表最末端添加新节点 /// </summary> /// <param name="item"></param> public void Add(T item) { Node<T> tailNode = new Node<T>(item); tail.Next = tailNode; tail = tailNode; if (count == 0) head.Next = tailNode; count++; } /// <summary> /// 在第 index 号元素后插入一个节点 /// <param name="item"></param> /// <param name="index"></param> public void AddPost(T item, int index) { int i = IsIndexVaild(index); if (i == -1) return; //找到索引元素 Node<T> pstr = GetNode(index); //链接新节点 Node<T> node = new Node<T>(item); node.Next = pstr.Next; pstr.Next = node; if (index == count) tail = node; count++; pstr = null; } /// <summary> /// 在第 index 号元素前插入一个节点 /// </summary> /// <param name="item"></param> /// <param name="index"></param> public void AddPre(T item, int index) { int i = IsIndexVaild(index); if (i == -1) return; //找到索引的前一位元素 Node<T> pstr = GetNode(index - 1); //链接新节点 Node<T> node = new Node<T>(item); node.Next = pstr.Next; pstr.Next = node; count++; pstr = null; } /// <summary> /// 清空链表 /// </summary> public void Clear() { head.Next = null; tail = head; } /// <summary> /// 删除指定位置的元素 /// </summary> /// <param name="index"></param> /// <returns></returns> public T Delete(int index) { int i = IsIndexVaild(index); if (i == -1) return default(T); //找到索引的前一位元素 Node<T> pstr = GetNode(index - 1); if (pstr.Next == null) return default(T); Node<T> qstr = pstr.Next; pstr.Next = qstr.Next; T t = qstr.Data; pstr = null; qstr.Next = null; qstr = null; count--; return t; } /// <summary> /// 按内容删除 /// </summary> /// <param name="item"></param> /// <param name="isSecond"></param> /// <returns></returns> public T Delete(T item,bool isSecond = true) { int k = GetPos(item); if (k == -1) return default(T); int i = 0; Node<T> pstr = head; while (i++ < k -1) { pstr = pstr.Next; } Node<T> qstr = pstr.Next; pstr.Next = qstr.Next; T t = qstr.Data; pstr = null; qstr.Next = null; qstr = null; count--; return t; } /// <summary> /// 返回指定索引的元素 /// </summary> /// <param name="index"></param> /// <returns></returns> public T GetElem(int index) { int i = IsIndexVaild(index); if (i == -1) return default(T); return GetNode(index).Data; } /// <summary> /// 返回链表长度 /// </summary> /// <returns></returns> public int GetLength() { return count; } /// <summary> /// 根据元素返回其索引值 /// </summary> /// <param name="item"></param> /// <returns></returns> public int GetPos(T item) { int k = 0; Node<T> pstr = head.Next; while (pstr != null && item != null && !pstr.Data.Equals(item)) { pstr = pstr.Next; k++; } if (pstr == null) { Console.WriteLine("所查找元素不存在"); return -1; } return k ; } /// <summary> /// 判断链表是否为空 /// </summary> /// <returns></returns> public bool IsEmpty() { if (head == null || head.Next == null) return true; return false; } /// <summary> /// 打印 /// </summary> public void Print() { Node<T> pstr = head.Next; int i = 1; while(pstr != null) { Console.WriteLine("第 " + i++ + "个元素是： " + pstr.Data); pstr = pstr.Next; } } /// <summary> /// 判断索引是否错误 /// </summary> /// <param name="index"></param> /// <returns></returns> public int IsIndexVaild(int index) { //判断索引是否越界 if (index < 0 || index > count) { Console.WriteLine("索引越界，不存在该元素"); return -1; } return 0; } /// <summary> /// 根据索引找到元素 /// </summary> /// <param name="index"></param> /// <returns></returns> public Node<T> GetNode(int index) { int k = 0; Node<T> pstr = head; while (k++ < index) { pstr = pstr.Next; } return pstr; } } } 

 

 

三. 双向链表

双向链表在思路上和单链表差不多，只是多了一个指向上一个节点的 Prev，所以代码上要更小心地处理。具体就不多赘述了，直接给出代码吧

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 线性表 { class DBNode<T> { private T data; private DBNode<T> next; private DBNode<T> prev; public DBNode() { this.data = default(T); this.next = null; this.prev = null; } public DBNode(T value) { this.data = value; this.next = null; this.prev = null; } public DBNode(T value, DBNode<T> next) { this.data = value; this.next = next; this.prev = null; } public T Data { get { return data; } set { data = value; } } public DBNode<T> Next { get { return next; } set { next = value; } } public DBNode<T> Prev { get { return prev; } set { prev = value; } } } } 

 

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 线性表 { class DBLinkList<T> : MyList<T> { private DBNode<T> head; private DBNode<T> tail; private int count; /// <summary> /// 构造器 /// </summary> public DBLinkList() { head = new DBNode<T>(); tail = head; count = 0; } /// <summary> /// 实现下标访问法 /// </summary> /// <param name="index"></param> /// <returns></returns> public T this[int index] { get { int i = IsIndexVaild(index); if (i == -1) return default(T); int k = 0; DBNode<T> pstr = head; while (k++ < index) { pstr = pstr.Next; } return pstr.Data; } } /// <summary> /// 在链表最末端添加新节点 /// </summary> /// <param name="item"></param> public void Add(T item) { if (count == 0) { DBNode<T> DbNode = new DBNode<T>(item); DbNode.Prev = head; head.Next = DbNode; tail = DbNode; count++; return; } DBNode<T> tailDBNode = new DBNode<T>(item); tailDBNode.Prev = tail; tail.Next = tailDBNode; tail = tailDBNode; count++; } /// <summary> /// 在第 index 号元素后插入一个节点，index 为 1，2，3，4..... /// </summary> /// <param name="item"></param> /// <param name="index"></param> public void AddPost(T item, int index) { //判断索引是否越界 int i = IsIndexVaild(index); if (i == -1) return; //找到索引元素 DBNode<T> pstr = GetNode(index); //链接新节点 DBNode<T> newNode = new DBNode<T>(item); newNode.Next = pstr.Next; newNode.Prev = pstr; if(pstr.Next != null) pstr.Next.Prev = newNode; pstr.Next = newNode; //如果是在最后节点添加 if (index == count) tail = newNode; count++; pstr = null; } /// <summary> /// 在第 index 号元素前插入一个节点，index 为 1，2，3，4..... /// </summary> /// <param name="item"></param> /// <param name="index"></param> public void AddPre(T item, int index) { //判断索引是否越界 int i = IsIndexVaild(index); if (i == -1) return; //找到索引的前一位元素 DBNode<T> pstr = GetNode(index - 1); //链接新节点 DBNode<T> newNode = new DBNode<T>(item); newNode.Next = pstr.Next; newNode.Prev = pstr; pstr.Next.Prev = newNode; pstr.Next = newNode; count++; pstr = null; //在 index 处AddPre相当于在 index - 1 处 AddPost，不过并不需要判断尾节点 } /// <summary> /// 清空链表 /// </summary> public void Clear() { head.Next = null; tail = head; } /// <summary> /// 删除指定位置的元素 /// </summary> /// <param name="index"></param> /// <returns></returns> public T Delete(int index) { //判断索引是否越界 int i = IsIndexVaild(index); if (i == -1) return default(T); //找到索引的前一位元素 DBNode<T> pstr = head; int k = 0; while (k++ < index - 1 && pstr != null) { pstr = pstr.Next; } if (pstr.Next == null) return default(T); DBNode<T> qstr = pstr.Next; T t = qstr.Data; pstr.Next = qstr.Next; qstr.Next.Prev = pstr; pstr = null; qstr.Next = null; qstr = null; count--; return t; } /// <summary> /// 按内容删除 /// </summary> /// <param name="item"></param> /// <param name="isSecond"></param> /// <returns></returns> public T Delete(T item,bool isSecond = true) { int k = GetPos(item); if (k == -1) return default(T); int i = 0; DBNode<T> pstr = head; while (i++ < k - 1) { pstr = pstr.Next; } DBNode<T> qstr = pstr.Next; T t = qstr.Data; pstr.Next = qstr.Next; if(qstr.Next != null) qstr.Next.Prev = pstr; pstr = null; qstr.Next = null; qstr = null; count--; return t; } /// <summary> /// 返回指定索引的元素 /// </summary> /// <param name="index"></param> /// <returns></returns> public T GetElem(int index) { int i = IsIndexVaild(index); if (i == -1) return default(T); int k = 0; DBNode<T> pstr = head; while (k++ < index) { pstr = pstr.Next; } return pstr.Data; } /// <summary> /// 返回链表长度 /// </summary> /// <returns></returns> public int GetLength() { return count; } /// <summary> /// 根据元素返回其索引值 /// </summary> /// <param name="item"></param> /// <returns></returns> public int GetPos(T item) { int k = 0; DBNode<T> pstr = head.Next; while (pstr != null && item != null && !pstr.Data.Equals(item)) { pstr = pstr.Next; k++; } if (pstr == null) { Console.WriteLine("所查找元素不存在"); return -1; } return k; } /// <summary> /// 判断链表是否为空 /// </summary> /// <returns></returns> public bool IsEmpty() { if (head == null || head.Next == null) return true; return false; } /// <summary> /// 打印 /// </summary> public void Print() { DBNode<T> pstr = head.Next; while (pstr != null) { Console.WriteLine(pstr.Data); pstr = pstr.Next; } } /// <summary> /// 判断索引是否错误 /// </summary> /// <param name="index"></param> /// <returns></returns> public int IsIndexVaild(int index) { //判断索引是否越界 if (index < 0 || index > count) { Console.WriteLine("索引越界，不存在该元素"); return -1; } return 0; } /// <summary> /// 根据索引找到元素 /// </summary> /// <param name="index"></param> /// <returns></returns> public DBNode<T> GetNode(int index) { int k = 0; DBNode<T> pstr = head; while (k++ < index) { pstr = pstr.Next; } return pstr; } } } 

 

总结

事实上，链表是一种比较简单且常用的数据结构。实现起来并不困难，只是要小心谨慎。下一篇会说到跳跃链表，跳跃链表的效率更高。好了，希望本文能对大家有所帮助

​