任务

实现泛型单向链表队列

实现目标：（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 }

链表队列优势：不优化的队列没啥优势，跟普通链表没啥区别

优化泛型链表队列

实现目标：（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 }

普通数组队列、循环数组队列、单向链表队列、优化单向链表队列运行性能比较

　　（1）普通数组队列与单向链表队列的性能是差不多的，其本质都是需要遍历整个数组/链表；

　　（2）优化的单向链表队列与循环数组队列，相比优化前每次操作少了一次遍历，性能大幅提升；

~以下分别为链表队列、数组队列、优化链表队列、循环数组队列进行添加元素与取出元素10w次的运行时间。

~优化链表队列、循环数组队列进行添加元素与取出元素500w次的运行时间

 提问：为什么数组比链表性能更好？