链表剖析及自己手撸“单链表“实现基本操作(初始化、增、删、改等)
一. 基础
1. 前言
链式存储结构，又叫链表，逻辑上相邻，但是物理位置可以不相邻，因此对链表进行插入和删除时不需要移动数据元素，但是存取数据的效率却很低，分为三类：
(1).单(向)链表：存储数据元素时，除了存储数据元素本身的信息外，还有一个指针，指向他的后继节点，最后一个元素的指针不指向任何元素。
【C#中的代表：ListDictionary，基本上已经被弃用了，官方称建议存10个元素以下，很鸡肋】
(2).双(向)链表：在单链表的基础上加一个前驱指针，指向前一个元素，是链表可以双向查找，这种结构成为双链表。
【C#中的代表：LinkedList
(3).循环链表：将链表最后一个节点的指针指向第一个节点，这样就形成了一个环，这种数据结构叫做单向循环列表.另外还有双向循环列表.
PS：循环链表结构中从表的任一节点出发均可以找到表中的其他节点如果从表头节点出发，访问链表的最后一个节点，必须扫描表中所有节点。若循环链表的头指 针改用尾指针代替，则从尾指针出发不仅可以立即访问到最后一个节点，而且十分方便的找到第一个节点。
2. LinkedList核心分析
首先LinkedList是一个双向链表!!,节点的存储类型为LinkedListNode
(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 list1 = new LinkedList();3 list1.AddFirst(1);4 list1.AddLast(10);5 //找到节点6 LinkedListNode 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多个高级知识点。
C/C++Linux服务器开发高级架构师/C++后台开发架构师免费学习地址
【文章福利】另外还整理一些C++后台开发架构师 相关学习资料，面试题，教学视频，以及学习路线图，免费分享有需要的可以点击领取
二. 提高
1.手撸单链表
(1).首先要有一个节点类Node,需要能记录该节点的值Data,并且根据该节点能获取下一个节点Next.实例化的时候可以传值,也可以不传值
(2).要有一个头结点作为基础、节点的个数;实例化的时候可以传值,也可以不传值.
(3).先要编写一个方法GetNodeByIndex，根据索引来获取节点，实质上只能遍历，其它方法基本上都要基于它.
(4).然后实现Add、Insert、RemoveAt、this[int index]、ToString等方法,需要注意的是越界问题、index=0问题、头结点为空的问题.
最终达到：获取一个节点，可以通过Data获取节点值，通过Next获取下一个节点,然后可以增删改查.
PS：单链表也好，双链表也罢，只要不是循环列表，尾节点的指针都是指向null.
Node节点代码
/// /// 节点类/// public class Node{public T _data; // 存放节点数据public Node _next; //存放下一个节点public Node(){}public Node(T data){_data = data;}/// /// 数据的输出/// /// Next{get{return _next;}set{_next = value;}}} 单链表代码
1 /// 2 /// 手写单链表3 /// 4 public class MySingleLinkedList5 {6 private Node _header; //头结点7 private int _count; //元素个数8 public MySingleLinkedList()9 {10 11 }12 public MySingleLinkedList(T data)13 {14 _header = new Node(data);15 _count++;16 }17 //只能读18 public int Count19 {20 get21 {22 return _count;23 } 24 }25 /// 26 /// 根据索引获取元素27 /// 28 /// 29 /// GetNodeByIndex(int index)31 {32 if (index < 0 || index>=_count)33 {34 throw new ArgumentOutOfRangeException("索引越界");35 }36 Node 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 get49 {50 return GetNodeByIndex(index).Data;51 }52 set53 {54 GetNodeByIndex(index).Data = value;55 }56 }57 58 /// 59 /// 添加元素(最后)60 /// 61 /// 62 public void Add(T data)63 {64 Node newNode = new Node(data);65 if (_header==null) //表示添加的是第一个节点66 {67 _header = newNode;68 }69 else70 {71 var lastNode = GetNodeByIndex(_count - 1);72 lastNode.Next = newNode;73 } 74 _count++;75 }76 77 /// 78 /// 插入元素79 /// 80 /// 索引81 /// 数据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(data); //新节点89 if (index==0)90 {91 //头结点为空，直接插入头结点即可92 if (_header==null)93 {94 _header = newNode;95 }96 //头结点有元素，需要把头结点的位置让出来97 else98 {99 newNode.Next = _header;
100 _header = newNode;
101 }
102 }
103 else
104 {
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 ///
114 /// 根据索引删除元素
115 ///
116 /// 索引
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 else
132 {
133 var preNode = GetNodeByIndex(index - 1); //删除节点的前驱节点
134 if (preNode.Next==null)
135 {
136 throw new ArgumentOutOfRangeException("索引越界");
137 }
138 preNode.Next = preNode.Next.Next; //如果删除的是最后一个节点，那么它的前一个节点指向null
139 }
140 _count--;
141 }
142 ///
143 /// 元素输出
144 ///
145 /// 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 mlist = new MySingleLinkedList();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 - 博客园