一. 基础
1. 前言
链式存储结构，又叫链表，逻辑上相邻，但是物理位置可以不相邻，因此对链表进行插入和删除时不需要移动数据元素，但是存取数据的效率却很低，分为三类：
**(1).单(向)链表：**存储数据元素时，除了存储数据元素本身的信息外，还有一个指针，指向他的后继节点，最后一个元素的指针不指向任何元素。
【C#中的代表：ListDictionary，基本上已经被弃用了，官方称建议存 10 个元素以下，很鸡肋】
(2).双(向)链表：在单链表的基础上加一个前驱指针，指向前一个元素，是链表可以双向查找，这种结构成为双链表。
【C#中的代表：LinkedList<T>】
(3).循环链表：将链表最后一个节点的指针指向第一个节点，这样就形成了一个环，这种数据结构叫做单向循环列表.另外还有双向循环列表.
PS：循环链表结构中从表的任一节点出发均可以找到表中的其他节点如果从表头节点出发，访问链表的最后一个节点，必须扫描表中所有节点。若循环链表的头指 针改用尾指针代替，则从尾指针出发不仅可以立即访问到最后一个节点，而且十分方便的找到第一个节点。
2. LinkedList<T>核心分析
首先 LinkedList 是一个双向链表!!,节点的存储类型为 LinkedListNode<T>,可以通过 node.Next 和 node.Previous 获取下一个节点或前一个节点，添加节点的时候主要是基于 一个节点往前加或者往后加（AddBefore，AddAfter）.
(1).增加：AddFirst、AddLast、AddBefore、AddAfter
(2).删除：Remove、RemoveFirst、RemoveLast; 其中 Remove 是根据值反删节点(内部循环,慢啊)，也可以查出节点进行删除
(3).修改： node.Value = xxx;
(4).查询：
A. 获取第 1 个/最后一个节点：First 、Last (.Value 就获取值了)
B. 根据值反查节点： Find、FindLast (内部遍历，慢啊,链表的通病,查询慢)
C. 获取下一个节点: node.Next (node.Next.Value; 获取值了)
D. 获取前一个节点: node.Previous (node.Previous.Value; 获取值了)
E. 输出所有值: Foreach
(5).其它：Contains、Count
代码分享：
1 { 2 LinkedList<int> list1 = new LinkedList<int>(); 3 list1.AddFirst(1); 4 list1.AddLast(10); 5 //找到节点 6 LinkedListNode<int> node1 = list1.Find(10); 7 Console.WriteLine($"node1的节点的值为:{node1.Value}"); 8 list1.AddBefore(node1, 9); 9 list1.AddAfter(node1, 11);10 11 //此时在获取node1的前一个节点和后一个节点12 var node1Pre = node1.Previous;13 Console.WriteLine($"node1的前一个节点的值为:{node1Pre.Value}");14 var node1Next = node1.Next;15 Console.WriteLine($"node1的的后一个节点的值为:{node1Next.Value}");16 17 //修改节点的值18 node1Next.Value = 111;19 20 //继续增加21 list1.AddLast(14);22 list1.AddLast(15);23 list1.AddLast(16);24 list1.AddLast(17);25 list1.AddLast(18);26 27 //删除节点28 list1.Remove(16);29 var dNode = list1.Find(17);30 list1.Remove(dNode);31 //删除最后一个节点32 list1.RemoveLast();33 34 Console.WriteLine("全部输出");35 foreach (var item in list1)36 {37 Console.WriteLine(item);38 }39 }
复制代码
运行结果：
更多 C++后台开发技术点知识内容包括 C/C++，Linux，Nginx，ZeroMQ，MySQL，Redis，MongoDB，ZK，流媒体，音视频开发，Linux 内核，TCP/IP，协程，DPDK 多个高级知识点。
二. 提高
1.手撸单链表
(1).首先要有一个节点类 Node,需要能记录该节点的值 Data,并且根据该节点能获取下一个节点 Next.实例化的时候可以传值,也可以不传值
(2).要有一个头结点作为基础、节点的个数;实例化的时候可以传值,也可以不传值.
(3).先要编写一个方法 GetNodeByIndex，根据索引来获取节点，实质上只能遍历，其它方法基本上都要基于它.
(4).然后实现 Add、Insert、RemoveAt、this[int index]、ToString 等方法,需要注意的是越界问题、index=0 问题、头结点为空的问题.
最终达到：获取一个节点，可以通过 Data 获取节点值，通过 Next 获取下一个节点,然后可以增删改查.
PS：单链表也好，双链表也罢，只要不是循环列表，尾节点的指针都是指向 null.
Node 节点代码
/// <summary> /// 节点类 /// </summary> public class Node<T> { public T _data; // 存放节点数据 public Node<T> _next; //存放下一个节点
public Node() {
} public Node(T data) { _data = data; }
/// <summary> /// 数据的输出 /// </summary> /// <returns></returns> public override string ToString() { return _data.ToString(); }
//当前节点的数据 public T Data { get { return _data; } set { _data = value; } } //下一个节点 public Node<T> Next { get { return _next; } set { _next = value; } } }
复制代码
单链表代码
1 /// <summary> 2 /// 手写单链表 3 /// </summary> 4 public class MySingleLinkedList<T> 5 { 6 private Node<T> _header; //头结点 7 private int _count; //元素个数 8 public MySingleLinkedList() 9 { 10 11 } 12 public MySingleLinkedList(T data) 13 { 14 _header = new Node<T>(data); 15 _count++; 16 } 17 //只能读 18 public int Count 19 { 20 get 21 { 22 return _count; 23 } 24 } 25 /// <summary> 26 /// 根据索引获取元素 27 /// </summary> 28 /// <param name="index"></param> 29 /// <returns></returns> 30 public Node<T> GetNodeByIndex(int index) 31 { 32 if (index < 0 || index>=_count) 33 { 34 throw new ArgumentOutOfRangeException("索引越界"); 35 } 36 Node<T> tempNode = _header; 37 //当index为0的时候，不进入for循环 38 for (int i = 0; i < index; i++) 39 { 40 tempNode = tempNode.Next; 41 } 42 return tempNode; 43 } 44 45 //索引器获取和设置数据 46 public T this[int index] 47 { 48 get 49 { 50 return GetNodeByIndex(index).Data; 51 } 52 set 53 { 54 GetNodeByIndex(index).Data = value; 55 } 56 } 57 58 /// <summary> 59 /// 添加元素(最后) 60 /// </summary> 61 /// <param name="data"></param> 62 public void Add(T data) 63 { 64 Node<T> newNode = new Node<T>(data); 65 if (_header==null) //表示添加的是第一个节点 66 { 67 _header = newNode; 68 } 69 else 70 { 71 var lastNode = GetNodeByIndex(_count - 1); 72 lastNode.Next = newNode; 73 } 74 _count++; 75 } 76 77 /// <summary> 78 /// 插入元素 79 /// </summary> 80 /// <param name="index">索引</param> 81 /// <param name="data">数据</param> 82 public void Insert(int index,T data) 83 { 84 if (index < 0||index>_count) 85 { 86 throw new ArgumentOutOfRangeException("索引越界"); 87 } 88 var newNode = new Node<T>(data); //新节点 89 if (index==0) 90 { 91 //头结点为空，直接插入头结点即可 92 if (_header==null) 93 { 94 _header = newNode; 95 } 96 //头结点有元素，需要把头结点的位置让出来 97 else 98 { 99 newNode.Next = _header;100 _header = newNode;101 }102 }103 else104 {105 var preNode = GetNodeByIndex(index-1); //查找插入位置的前驱节点106 var nextNode = preNode.Next; //插入位置的后继节点107 preNode.Next = newNode; //前驱结点的后继节点为新节点108 newNode.Next = nextNode; //新节点的后继节点执行原来前驱的后继109 }110 _count++; 111 }112 113 /// <summary>114 /// 根据索引删除元素115 /// </summary>116 /// <param name="index">索引</param>117 public void RemoveAt(int index)118 {119 if (index < 0 || index >= _count)120 {121 throw new ArgumentOutOfRangeException("索引越界");122 }123 if (index==0) //删除头结点124 {125 if (_header==null)126 {127 throw new ArgumentOutOfRangeException("索引越界");128 }129 _header = _header.Next;130 }131 else132 {133 var preNode = GetNodeByIndex(index - 1); //删除节点的前驱节点134 if (preNode.Next==null)135 {136 throw new ArgumentOutOfRangeException("索引越界");137 }138 preNode.Next = preNode.Next.Next; //如果删除的是最后一个节点，那么它的前一个节点指向null139 }140 _count--;141 }142 /// <summary>143 /// 元素输出144 /// </summary>145 /// <returns></returns>146 public override string ToString()147 {148 string s = "";149 Node<T> temp = _header;150 while (temp != null)151 {152 s += temp.ToString() + " ";153 temp = temp.Next;154 }155 return s;156 }157 158 }
复制代码
测试代码
1 { 2 Console.WriteLine("--------------------------手撸单链表测试---------------------------"); 3 MySingleLinkedList<int> mlist = new MySingleLinkedList<int>(); 4 mlist.Add(0); 5 mlist.Add(1); 6 mlist.Add(3); 7 mlist.Add(4); 8 mlist.Add(5); 9 mlist.Add(6);10 mlist.Insert(0, 100);11 Console.WriteLine(mlist.ToString());12 mlist.RemoveAt(4);13 mlist[1] = 999;14 Console.WriteLine(mlist.ToString());15 for (int i = 0; i < mlist.Count; i++)16 {17 Console.WriteLine(mlist[i]);18 }19 mlist.Insert(5, 555);20 Console.WriteLine(mlist.ToString());21 mlist.RemoveAt(0);22 Console.WriteLine(mlist.ToString());23 }
复制代码
运行结果
2.链表优缺点
优点
(1).需要空间就申请，不需要就释放，空间有效利用。
(2).插入和删除只需要修改几个指针，方便快捷。
(3).双链表双向搜索，简化算法复杂度。
缺点
(1).算法实现复杂抽象,需要额外内存空间保存节点的逻辑关系。
(2).只能顺序访问，访问速度慢。
(3).可能会把节点存放到托管堆的任意角落，垃圾回收需要更多开销。
原文链接：第五节：链表剖析及自己手撸"单链表"实现基本操作(初始化、增、删、改等) - Yaopengfei - 博客园
评论