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

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

2018-09-23 555

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

总结

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

微信关注我们

原文链接：https://yq.aliyun.com/articles/658735

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

js的基础知识笔记

目录一、基本数据类型二、函数三、面向对象一、基本数据类型 1、使用var声明变量、使用;结尾、使用{}表示代码块、使用驼峰式命名 2、变量是弱类型的，即并不严格要求声明变量的类型，一个变量可以在运行期间动态的指向不同类型的数据 3、变量声明后可以不定义(或叫赋值、初始化)，此时它的值是undefined 4、符号$可以作为命名开头的特殊字母，jQuery使用它作为jquery函数的别名 5、数据分为两大类：原始数据和引用数据，所以一个变量中保存的值自然也有两类原始数据：直接存放在栈中, 变量中保存着此数据的直接值引用数据：存放在堆中，并把内存地址存放在栈中，即变量中存放着此对象的指针 6、原始类型：undefined、boolean、number、string、null 7、引用类型：即对象object，其他array、function等对象都是在object基础上进一步封装的对象二、函数 1、函数也是一个对象，构造函数在功能上还类似于一个类 2、函数如果没有显式说明返回值，则默认return undefined 3、函数对输入参数的要求并不严格(数量、类型)，可以使用a...

2018-09-24

532

原文: c# throw和throw ex c# throw和throw ex 我们在日常开发当中，经常会用到exception异常，并且我们会在exception中的catch块中throw exception，例如： static void M3() { try { //你的业务代码 } catch (Exception ex) { throw ex; } } 但是大家是否清楚在catch块中 throw和throw ex的区别呢？在一次电话面试中，面试官就问到这个问题了，当时没有答上来，事后经过测试才知道两者的区别，其实只要自己测试一下，就知道两者之间的区别了,测试代码： 1. throw ex 测试 using System; namespace MuzizMH.Test { class Program { static void Main(string[] args) { M2(); } static void M1() { throw new Exception("M1 Exception"); } static void M2() { try { M1(); } c...

2018-09-25

514

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。