任务
实现泛型单向链表队列
实现目标：（1）实现基础单向链表；
（2）在单项链表的基础上修改为队列；
实现过程：（1）单向链表的实现；
（2）构建单项链表队列；
链表队列实现代码：
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6
7 namespace DataStructrue
8 {
9 class LinkList1Queue<E> : IQueue<E>
10 {
11 LinkedList1<E> l;
12 public LinkList1Queue()
13 {
14 l = new LinkedList1<E>();
15 }
16 public int Count => l.Count;
17
18 public bool IsEmpty => l.IsEmpty;
19
20 public E DeQueue()
21 {
22 return l.RemoveFirst();
23 }
24
25 public void EnQueue(E e)
26 {
27 l.AddLast(e);
28 }
29
30 public E Peek()
31 {
32 return l.GetFirst();
33 }
34 }
35 }
View Code
链表队列优势：不优化的队列没啥优势，跟普通链表没啥区别
优化泛型链表队列
实现目标：（1）能快速找到首尾元素并进行操作
实现过程：（1）添加一个尾结点字段，头结点添加结点是单向链表天然的优势
实现代码：
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6
7 namespace DataStructrue
8 {
9 class LinkedList2<E>
10 {
11 /// <summary>
12 /// 内部类，作为链表的结点使用
13 /// </summary>
14 private class Node
15 {
16 //定义一个泛型的字段存储数据
17 public E e;
18 //定义链表的下一个结点指针
19 public Node next;
20 /// <summary>
21 /// 可以传入数据和一个结点指针的构造函数
22 /// </summary>
23 /// <param name="e"></param>
24 /// <param name="next"></param>
25 public Node(E e, Node next)
26 {
27 this.e = e;
28 this.next = next;
29 }
30 /// <summary>
31 /// 可以创建作为尾部的结点的构造函数
32 /// </summary>
33 /// <param name="e"></param>
34 public Node(E e)
35 {
36 this.e = e;
37 this.next = null;
38 }
39 /// <summary>
40 /// 打印该结点则返回该结点的E型数据
41 /// </summary>
42 /// <returns></returns>
43 public override string ToString()
44 {
45 return e.ToString();
46 }
47 }
48 //头结点
49 private Node head;
50 //尾结点
51 private Node tail;
52 //结点个数;
53 private int N;
54 /// <summary>
55 /// 无参构造函数
56 /// </summary>
57 public LinkedList2()
58 {
59 head = null;
60 N = 0;
61 }
62 //链表长度
63 public int Count { get { return N; } }
64 //链表是否为空
65 public bool IsEmpty { get { return N == 0; } }
66 /// <summary>
67 /// 添加结点
68 /// </summary>
69 /// <param name="index"></param>
70 /// <param name="e"></param>
71 public void Add(int index, E e)
72 {
73 if (index < 0 || index > N)
74 {
75 throw new ArgumentException("非法索引");
76 }
77 if (index == 0)
78 {
79 ////为什么不直接赋值null而是赋值head;
80 //Node node = new(e);
81 //node.next = head;
82 //head = node;
83 ////等价于↓
84 head = new(e, head);
85 }
86 else if (index < N)
87 {
88 Node pre = head;
89 //按照0为起点开始数，并非从1开始数
90 for (int i = 0; i < index - 1; i++)
91 {
92 pre = pre.next;
93 }
94 //Node node = new(e);
95 //node.next = pre.next;
96 //pre.next = node;
97 ////等价于↓
98 pre.next = new(e, pre.next);
99 }
100 else
101 {
102 tail.next = new(e, tail.next);
103 }
104 if (N == 0)
105 {
106 tail = head;
107 }
108 else if (index == N)
109 {
110 tail = tail.next;
111 }
112 N++;
113 }
114 //头部添加结点
115 public void AddFirst(E e)
116 {
117 Add(0, e);
118 }
119 //尾部添加结点
120 public void AddLast(E e)
121 {
122 Add(N, e);
123 }
124 /// <summary>
125 /// 按照下标删除结点
126 /// </summary>
127 /// <param name="index"></param>
128 /// <returns></returns>
129 public E RemoveAt(int index)
130 {
131 if (index < 0 || index >= N)
132 {
133 throw new ArgumentException("非法索引");
134 }
135 Node pre = head;
136 if (index == 0)
137 {
138 //如果移除的是头结点，则新的头结点为pre的下一个结点
139 head = pre.next;
140 N--;
141 return pre.e;
142 }
143 for (int i = 0; i < index - 1; i++)
144 {
145 //
146 pre = pre.next;
147 }
148 Node rm = new(pre.next.e, null);
149 pre.next = pre.next.next;
150 if (index == N - 1)
151 {
152 tail = pre;
153 }
154 N--;
155 return rm.e;
156 }
157 /// <summary>
158 /// 按照元素删除结点
159 /// </summary>
160 /// <param name="e"></param>
161 public void Remove(E e)
162 {
163 if (head == null)
164 {
165 return;
166 }
167 Node cur = head;
168 Node pre = null;
169 while (cur != null)
170 {
171 if (cur.e.Equals(e))
172 {
173 break;
174 }
175 pre = cur;
176 cur = cur.next;
177 }
178 if (pre == null)
179 {
180 head = head.next;
181 N--;
182 }
183 else if (cur != null)
184 {
185 pre.next = cur.next;
186 N--;
187 }
188 ////也可这样实现↓
189 //Node cur = head.next;
190 //Node pre = head;
191 //for (int i = 0; i < N-1; i++)
192 //{
193 // if (pre.e.Equals(e))
194 // {
195 // head = head.next;
196 // break;
197 // }
198 // else if(cur.e.Equals(e))
199 // {
200 // pre.next = cur.next;
201 // break;
202 // }
203 // pre = cur;
204 // cur = cur.next;
205 //}
206 }
207 public E RemoveFirst()
208 {
209 return RemoveAt(0);
210 }
211 public E RemoveLast()
212 {
213 return RemoveAt(N - 1);
214 }
215 /// <summary>
216 /// 修改结点数据
217 /// </summary>
218 /// <param name="index"></param>
219 /// <param name="e"></param>
220 public void Set(int index, E e)
221 {
222 if (index < 0 || index >= N)
223 {
224 throw new ArgumentException("非法索引");
225 }
226 Node cur = head;
227 for (int i = 0; i < index; i++)
228 {
229 cur = cur.next;
230 }
231 cur.e = e;
232 }
233 /// <summary>
234 /// 获取结点数据
235 /// </summary>
236 /// <param name="index"></param>
237 /// <returns></returns>
238 public E Get(int index)
239 {
240 if (index < 0 || index >= N)
241 {
242 throw new ArgumentException("非法索引");
243 }
244 Node cur = head;
245 for (int i = 0; i < index; i++)
246 {
247 cur = cur.next;
248 }
249 return cur.e;
250 }
251 /// <summary>
252 /// 获取第一个数据
253 /// </summary>
254 /// <returns></returns>
255 public E GetFirst()
256 {
257 return Get(0);
258 }
259 /// <summary>
260 /// 获取最后一个数据
261 /// </summary>
262 /// <returns></returns>
263 public E GetLast()
264 {
265 return tail.e;
266 }
267 /// <summary>
268 /// 打印输出结点，也可以直接重写ToString方法实现
269 /// </summary>
270 public void Print()
271 {
272 Node pri = head;
273 for (int i = 0; i < N; i++)
274 {
275 Console.Write(pri + " ");
276 pri = pri.next;
277 }
278 Console.WriteLine();
279 }
280 /// <summary>
281 /// 重写ToString方法，打印输出链表
282 /// </summary>
283 /// <returns></returns>
284 public override string ToString()
285 {
286 StringBuilder res = new();
287 Node cur = head;
288 while (cur != null)
289 {
290 res.Append(cur + "->");
291 cur = cur.next;
292 }
293 res.Append("Null Tail:" + GetLast() + "\n");
294 return res.ToString();
295 }
296 }
297 }
View Code
普通数组队列、循环数组队列、单向链表队列、优化单向链表队列运行性能比较
（1）普通数组队列与单向链表队列的性能是差不多的，其本质都是需要遍历整个数组/链表；
（2）优化的单向链表队列与循环数组队列，相比优化前每次操作少了一次遍历，性能大幅提升；
~以下分别为链表队列、数组队列、优化链表队列、循环数组队列进行添加元素与取出元素10w次的运行时间。
~优化链表队列、循环数组队列进行添加元素与取出元素500w次的运行时间
提问：为什么数组比链表性能更好？