NET 数据结构

概念介绍：

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据

 

 由图可知：

1. 链表在进行添加/删除时，只需要修改 当前节点和相邻节点 的next，更新效率高
2. 遍历数据，需要根据节点按顺序访问，导致查询速度慢，时间复杂度为O(n)
3. 每个节点中都保存了下一个节点的指针【Next，最后一个节点的next为null】，所以长度是动态变化的，且不是连续内存空间

相关代码：

MyLinkedListNode:自定义链表节点类

 1  /// <summary> 2  /// 自定义链表节点类： 单链表 3  /// </summary> 4  public class MyLinkedListNode<T> 5  { 6   /// <summary> 7   /// 当前节点 8   /// </summary> 9   public T Node { get; set; }10 11   /// <summary>12   /// 下一个节点13   /// </summary>14   public MyLinkedListNode<T> Next { get; set; }15 16   /// <summary>17   /// 构造函数： 无参构造函数18   /// </summary>19   /// <param name="Node"></param>20   public MyLinkedListNode()21   {22    this.Node = default;23    this.Next = null;24   }25 26   /// <summary>27   /// 构造函数： 指定当前节点，常用于 新增根节点和最后一个节点28   /// </summary>29   /// <param name="node"></param>30   public MyLinkedListNode(T node)31   {32    this.Node = node;33    this.Next = null;34   }35 36   /// <summary>37   /// 构造函数： 指定当前节点和下一节点，常用于 新增内部节点/确定下一节点 的情况38   /// </summary>39   /// <param name="next"></param>40   /// <param name="Next"></param>41   public MyLinkedListNode(T node, MyLinkedListNode<T> next)42   {43    this.Node = node;44    this.Next = next;45   }46  }

View Code

MyLinkedList:自定义链表

 1  /// <summary> 2  /// 自定义链表 3  /// 功能： 4  ///  1.添加： 添加到集合最后面 5  ///  2.添加： 添加到集合最前面 6  ///  3.添加： 添加索引后面 7  ///  4.添加： 添加索引前面 8  ///  5.删除： 删除T 9  ///  6.删除： 删除指定索引 10  ///  7.删除： 删除第一个 11  ///  8.删除： 删除最后一个 12  ///  9.删除： 删除所有 13  /// </summary> 14  public class MyLinkedList<T> 15  { 16   /// <summary> 17   /// 存储链表集合-根节点：  18   /// 框架自带了双向链表 System.Collections.Generic.LinkedList，链表集合保存在 MyLinkedListNode 中 19   /// 考虑到存在clear方法，链表默认值为null更方便 20   /// </summary> 21   private MyLinkedListNode<T> _rootNode = null; // { get; set; } 22  23   /// <summary> 24   /// 索引索引器，从0开始，根据索引返回指定索引节点信息 25   /// </summary> 26   /// <param name="index"></param> 27   /// <returns></returns> 28   public T this[int index] 29   { 30    get 31    { 32     var node = GetNodeAt(index).Node; 33     Console.WriteLine($"this[int {index}] = {node}\r\n"); 34     return node; 35    } 36   } 37  38   #region 查询方法 39  40   /// <summary> 41   /// 根据索引返回指定索引节点信息 42   /// </summary> 43   /// <param name="index">索引，从0开始</param> 44   /// <returns></returns> 45   private MyLinkedListNode<T> GetNodeAt(int index) => GetNodeTupleAt(index)?.Item1; 46  47   /// <summary> 48   /// 根据索引返回指定索引：节点元组 49   /// </summary> 50   /// <param name="index">索引，从0开始</param> 51   /// <returns>item1:当前节点;item2:上一节点;item3:下一节点;</returns> 52   private Tuple<MyLinkedListNode<T>, MyLinkedListNode<T>, MyLinkedListNode<T>> GetNodeTupleAt(int index) 53   { 54    if (index < 0) return null; 55    if (_rootNode == null) throw new Exception("自定义链表为空！"); 56  57    var num = 0; 58    // 当前节点 59    MyLinkedListNode<T> currentNode = _rootNode; 60    // 上一节点 61    MyLinkedListNode<T> prevNode = _rootNode; 62    // while循环会在 currentNode == 倒数第二个节点时就会停止循环，所以while后面需要再做一次判断 63    while (currentNode.Next != null) 64    { 65     // 如果当前索引 和 查找索引相同，则返回担负起节点 66     if (num == index) return GetValidNodeTuple(index, currentNode, prevNode); 67     // 重置：上一节点 68     prevNode = currentNode; 69     // 重置：当前节点 70     currentNode = currentNode.Next; 71     num++; 72    } 73    if (num < index) throw new Exception("索引超过链表长度！"); 74    return num == index ? GetValidNodeTuple(index, currentNode, prevNode) : null; 75   } 76  77   /// <summary> 78   /// 获取有效的节点元组 79   /// </summary> 80   /// <param name="index">索引</param> 81   /// <param name="currentNode">当前节点</param> 82   /// <param name="prevNode">上一节点【如果索引 == 0 ？ null ：上一节点 】</param> 83   /// <returns>item1:当前节点;item2:上一节点;item3:下一节点;</returns> 84   private Tuple<MyLinkedListNode<T>, MyLinkedListNode<T>, MyLinkedListNode<T>> GetValidNodeTuple(int index, MyLinkedListNode<T> currentNode, MyLinkedListNode<T> prevNode) 85   { 86    return new Tuple<MyLinkedListNode<T>, MyLinkedListNode<T>, MyLinkedListNode<T>>(currentNode, index == 0 ? null : prevNode, currentNode.Next); 87   } 88  89