概念介绍：
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。
链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据
由图可知：
- 链表在进行添加/删除时，只需要修改 当前节点和相邻节点 的next，更新效率高
- 遍历数据，需要根据节点按顺序访问，导致查询速度慢，时间复杂度为O(n)
- 每个节点中都保存了下一个节点的指针【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 CodeMyLinkedList:自定义链表
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
没有评论:
发表评论