AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2018-09-24 1182
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 在编程领域，数据结构与算法向来都是提升编程能力的重点。而一般常见的数据结构是链表，栈，队列，树等。事实上C#也已经封装好了这些数据结构，在头文件 System.Collections.Generic 中，直接创建并调用其成员方法就行。

在编程领域，数据结构与算法向来都是提升编程能力的重点。而一般常见的数据结构是链表，栈，队列，树等。事实上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;
		}
	}
}

 

总结

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

​

文章标签：
索引
C#
Java
算法
关键词：
单链表链表
节点链表
泛型链表
C#单链表
C#链表
柠檬二哈
目录
相关文章
石小浪♪
|
2月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法，即如何通过使用三个指针（preNode, curNode, curNextNode）来两两交换链表中的节点，并提供了详细的代码实现。
石小浪♪
18 0
LeetCode第二十四题(两两交换链表中的节点)
石小浪♪
|
2月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点，可以通过快慢指针法在一次遍历中实现。
石小浪♪
44 0
Leetcode第十九题(删除链表的倒数第N个节点)
LKIDTI数据
|
2月前
（剑指offer）18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点（2021.12.07）
（剑指offer）18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点（2021.12.07）
LKIDTI数据
49 0
长梦
|
3月前
|
安全 程序员 编译器
C#一分钟浅谈：泛型编程基础
在现代软件开发中，泛型编程是一项关键技能，它使开发者能够编写类型安全且可重用的代码。C# 自 2.0 版本起支持泛型编程，本文将从基础概念入手，逐步深入探讨 C# 中的泛型，并通过具体实例帮助理解常见问题及其解决方法。泛型通过类型参数替代具体类型，提高了代码复用性和类型安全性，减少了运行时性能开销。文章详细介绍了如何定义泛型类和方法，并讨论了常见的易错点及解决方案，帮助读者更好地掌握这一技术。
长梦
80 11
服务端技术栈
|
4月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法，通过使用虚拟节点和前驱节点技巧，实现了链表中相邻节点的交换。
服务端技术栈
41 3
LeetCode第24题两两交换链表中的节点
小徐在进步
|
3月前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作；以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段，展示了每种算法的实现思路与步骤，帮助读者深入理解并掌握这些数据结构的基本操作方法。
小徐在进步
44 2
游客rcxtdbgrolahs
|
3月前
05_删除链表的倒数第N个节点
05_删除链表的倒数第N个节点
游客rcxtdbgrolahs
29 0
游客rcxtdbgrolahs
|
3月前
04_两两交换链表中的节点
04_两两交换链表中的节点
游客rcxtdbgrolahs
29 0
BetterBench
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案，使用双指针法找到并返回链表中倒数第k个节点。
BetterBench
54 5
BetterBench
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案，通过使用双指针法找到并删除链表中值为特定数值的节点，然后返回更新后的链表头节点。
BetterBench
41 4