03单链表

、# 单链表

单链表是一种链式存储的数据结构，用一组地址任意的存储单元存放线性表中的数据元素³。单链表中的每个结点包含一个数据域和一个指针域，数据域存放数据元素，指针域存放下一个结点的地址²³。单链表的第一个结点称为头结点，最后一个结点称为尾结点，尾结点的指针域为空¹²。单链表可以用来实现栈、队列等抽象数据类型，它的优点是插入和删除操作方便，但是缺点是访问任意元素需要从头开始遍历¹²。

源: ， 2023/3/6(1) 单链表_百度百科. https://baike.baidu.com/item/%E5%8D%95%E9%93%BE%E8%A1%A8/3228368 访问时间 2023/3/6.
(2) 数据结构1 | 单链表其实真的很简单。 - 知乎. https://zhuanlan.zhihu.com/p/52989925 访问时间 2023/3/6.
(3) 一口气搞懂「链表」，就靠这20+张图了 - 知乎. https://bing.com/search?q=%e4%bb%80%e4%b9%88%e6%98%af%e5%8d%95%e9%93%be%e8%a1%a8 访问时间 2023/3/6.
(4) 什么是单链表，链式存储结构详解. http://c.biancheng.net/view/3336.html 访问时间 2023/3/6.
(5) 区块链技术与数据库的区别 你知道几个？. https://www.163.com/dy/article/HU6HCNUD05561SVZ.html 访问时间 2023/3/6.

练习

自定义一个IList

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;namespace _01_LinearList
{interface IListDS<T>{int GetLength();void Clear();bool IsEmpty();void Add(T item);void Insert(T item, int index);T Delete(int index);T this[int index] { get; }//取表的元素T GetEle(int index);//定义一个索引器，获取元素int Locate(T value);//按值查找}
}

自定义节点

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;namespace _01_LinearList
{/// <summary>/// 单链表的节点/// </summary>/// <typeparam name="T"></typeparam>class Node<T>{private T data;//存储数据private Node<T> next;//指针 用来指向下一个元素public Node(){data = default(T);next = null;}public Node(T value){data = value;next = null;}public Node(T value,Node<T> next){this.data = value;this.next = next;}public Node(Node<T> next){this.next = next;}public T Data{get { return data; }set { data = value; }}public Node<T> Next{get { return next; }set { next = value; }}}
}

自定义单链表类

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;namespace _01_LinearList
{class LinkList<T> : IListDS<T>{//存储头结点private Node<T> head;//LinkList构造函数public LinkList(){head = null;}/// <summary>/// 当前值/// </summary>/// <param name="index"></param>/// <returns></returns>public T this[int index]{get {Node<T> temp = head;for (int i = 1; i <= index; i++){temp = temp.Next;}return temp.Data;}}/// <summary>/// 添加一个节点/// </summary>/// <param name="item"></param>public void Add(T item){Node<T> newNode = new Node<T>(item);//根据新的数据创建一个新的节点;//如果头节点为空，那么这个新的节点就是头节点if(head ==null){head = newNode;}else{//把新来的结点放到链表的尾部//要访问到链表的尾结点Node<T> temp = head;while (true){//如果temp.Next不为空，一直找下一个节点if (temp.Next!=null){temp = temp.Next;}else{break;}}temp.Next = newNode;//把新来的结点放到链表的尾部}}/// <summary>/// 清空/// </summary>public void Clear(){head = null;}/// <summary>/// 删除一个元素/// </summary>/// <param name="index"></param>/// <returns></returns>public T Delete(int index){T data = default(T);if (index==0)//删除头结点{  //让头结点用一个data装着data = head.Data;//让第二节点成为头结点head = head.Next;}//删除中间元素else{ //把头结点用temp装着Node<T> temp = head;//一直找到index-1的元素for (int i = 1; i < index-1; i++){//把节点往后移动一位temp = temp.Next;}Node<T> preNode = temp;Node<T> currentNode = temp.Next;data = currentNode.Data;Node<T> nextNode = temp.Next.Next;preNode.Next = nextNode;}return data;}/// <summary>/// 获取当前元素/// </summary>/// <param name="index"></param>/// <returns></returns>public T GetEle(int index){return this[index];}/// <summary>/// 获取长度/// </summary>/// <returns></returns>public int GetLength(){if (head==null){return 0;}Node<T> temp = head;int count = 1;while (true){if (temp.Next != null){count++;temp = temp.Next;}else{break;}}return count;}/// <summary>/// 插入一个元素/// </summary>/// <param name="item"></param>/// <param name="index"></param>public void Insert(T item, int index){Node<T> newNode = new Node<T>(item);if (index == 0)//插入到头结点{newNode.Next = head;head = newNode;}else{Node<T> temp = head;for (int i = 1; i <=index-1; i++){//让节点往后移动1个位置temp = temp.Next;}Node<T> preNode = temp;Node<T> currentNode = temp.Next;preNode.Next = newNode;newNode.Next = currentNode;}}/// <summary>/// 判断是否为空/// </summary>/// <returns></returns>public bool IsEmpty(){return head == null;}/// <summary>/// 定位value所在位置/// </summary>/// <param name="value"></param>/// <returns></returns>public int Locate(T value){Node<T> temp = head;if (temp==null){return -1;}else{int index = 0;while (true){if (temp.Data.Equals(value)){return index;}else{if (temp.Next!=null){temp = temp.Next;}else{break;}}}return -1;}}}
}

指针介绍

C#中的指针是一种变量，它存储了另一种类型的内存地址​^{[1](https://www.php.cn/csharp-article-453529.html)}​。C#中的指针需要使用unsafe关键字来声明，因为它们是不安全的代码，也就是说CLR无法验证它们的安全性​^{[2](https://blog.csdn.net/u013716859/article/details/122392387)}​。C#中可以定义为指针的类型有sbyte, byte, short, ushort, int, uint, long, ulong, char, float, double, decimal和bool​^{[3](https://www.cnblogs.com/imlions/p/3203427.html)}​。指针可以用于调用API函数，提高程序的执行速度，或者操作复杂的数据结构​^{[3](https://www.cnblogs.com/imlions/p/3203427.html)}​^{[4](https://blog.csdn.net/qq_34059233/article/details/105809946)}。

‍