线性链表

线性链表的基本操作，代码如下：
  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace ConsoleApp7
  8 {
  9     class Program
 10     {
 11         static void Main(string[] args)
 12         {
 13 
 14 
 15             {
 16                 LinearList list = new LinearList(10);
 17                 ILinearList line = list;
 18                 line.Add(0, 12);
 19                 line.Add(1, 20);
 20                 line.Add(2, 4);
 21                 line.Add(3, 9);
 22                 Console.WriteLine("数组大小size: {0}", line.Size());
 23                 Console.WriteLine("数组长度length: {0}", list.sList.Length);
 24                 Console.WriteLine(line.Get(0));
 25                 Console.WriteLine(line.Get(1));
 26                 Console.WriteLine(line.Get(2));
 27                 Console.WriteLine(line.Get(3));
 28 
 29                 Console.WriteLine("排序后的数组为:");
 30                 for (int i = 0; i < line.Size(); i++)
 31                 {
 32                     Sort(line, i);
 33                 }
 34                 foreach (var item in list.sList)
 35                 {
 36                     Console.Write(item + "  ");
 37                 }
 38             }
 39            
 40             Console.Read();
 41         }
 42 
 43         static ILinearList Sort(ILinearList ST, int placeNum)
 44         {
 45             if (placeNum < 0 || placeNum >= ST.Size())
 46             {
 47                 return ST;
 48             }
 49             int j = (int)ST.Get(placeNum);   //一轮排序中找到的最小元素
 50             int element = (int)ST.Get(placeNum); //要排序元素
 51             int elemplace = placeNum;     //要排序元素最终要放置的位置
 52             //12,20,4,9
 53             for (int i = placeNum + 1; i < ST.Size(); i++)
 54             {
 55                 if (j > (int)ST.Get(i))
 56                 {
 57                     j = (int)ST.Get(i);
 58                     elemplace = i;
 59                 }
 60             }
 61             if (elemplace != 0)
 62             {
 63                 ST.Set(placeNum, j);
 64                 ST.Set(elemplace, element);
 65             }
 66             return ST;
 67         }
 68     }
 69 
 70 
 71 
 72     interface ILinearList
 73     {
 74         /// <summary>
 75         /// 是否为空
 76         /// </summary>
 77         /// <returns></returns>
 78         bool IsEmpty();
 79         /// <summary>
 80         /// 大小
 81         /// </summary>
 82         /// <returns></returns>
 83         int Size();
 84         /// <summary>
 85         /// 获取元素
 86         /// </summary>
 87         /// <param name="index">待获取的索引</param>
 88         /// <returns></returns>
 89         object Get(int index);
 90         /// <summary>
 91         /// 设置元素
 92         /// </summary>
 93         /// <param name="index">待获取的索引</param>
 94         /// <param name="elem">待设置的元素</param>
 95         /// <returns></returns>
 96         object Set(int index, object elem);
 97         /// <summary>
 98         /// 添加元素
 99         /// </summary>
100         /// <param name="index">待添加的位置</param>
101         /// <param name="elem">待添加的元素</param>
102         /// <returns></returns>
103         bool Add(int index, object elem);
104         /// <summary>
105         /// 移除元素
106         /// </summary>
107         /// <param name="index">待移除的索引</param>
108         /// <returns></returns>
109         Object Remove(int index);
110         /// <summary>
111         /// 清除所有元素
112         /// </summary>
113         void Clear();
114     }
115 
116     internal class LinearList : ILinearList
117     {
118         public object[] sList = null;
119         private const int defaultCapacity = 10;       // 数组容量
120         private int size = 0;         //数组实际存储大小
121         public LinearList(int capacity)
122         {
123             if (capacity <= 0)
124             {
125                 sList = new object[defaultCapacity];
126             }
127             else
128             {
129                 sList = new object[capacity];
130             }
131 
132             this.size = 0;
133         }
134         public bool Add(int index, object elem)
135         {
136 
137             //索引大于数组的长度，还是数组的容量
138             //元素后移，插入
139             if (index < 0 || index > size)
140             {
141                 throw new Exception("插入位置有误");
142             }
143             //从新分配空间
144             if (size == sList.Length)
145             {
146                 object[] temp = sList;
147                 sList = new object[size * 2];
148                 for (int i = 0; i < temp.Length; i++)
149                 {
150                     sList[i] = temp[i];
151                 }
152             }
153             //分析：1,2,3,4,5    长度为5的数组 , size = 5，  待插入数值为10 插入索引index = 2  插入后的值为   1，2，10，3，4,5     
154             //首先移动index = size - 1 最后一位，以此从最后一位到index这个位置 
155             for (int j = size - 1; j >= index; j--)
156             {
157                 sList[j + 1] = sList[j];
158             }
159             sList[index] = elem;
160             size++;
161             return true;
162 
163         }
164 
165         public void Clear()
166         {
167             for (int i = 0; i < sList.Length; i++)
168             {
169                 sList[i] = null;
170             }
171             size = 0;
172         }
173 
174         public object Get(int index)
175         {
176             ThrowExe(index);
177             return sList[index];
178         }
179 
180 
181         public bool IsEmpty()
182         {
183             return size == 0;
184         }
185 
186         public object Remove(int index)
187         {
188             //1,2,3,4,5    index = 2   移除值为3的元素，后面的元素 4，5前移
189             ThrowExe(index);
190             object removeNumber = sList[index];
191 
192             for (int i = index; i < sList.Length - 1; i++)
193             {
194                 sList[i] = sList[i + 1];
195             }
196             sList[size - 1] = null;
197             size--;
198             return removeNumber;
199         }
200 
201         public object Set(int index, object elem)
202         {
203             ThrowExe(index);
204 
205             var old = sList[index];
206             sList[index] = elem;
207             return old;
208         }
209 
210         public int Size()
211         {
212             return size;
213         }
214 
215         public bool RangeCheck(int index)
216         {
217             if (index < 0 || index >= size)
218             {
219                 return false;
220             }
221             return true;
222         }
223 
224         private void ThrowExe(int index)
225         {
226             if (!RangeCheck(index))
227             {
228                 throw new Exception("参数不合法");
229             }
230         }
231 
232     }
233 
234 
235     /// <summary>
236     /// 结点类
237     /// </summary>
238     class Node
239     {
240         public object nodeValue;
241         public Node next;
242         public Node()
243         {
244             nodeValue = null;
245             next = null;
246         }
247 
248         public Node(object nodeValue)
249         {
250             this.nodeValue = nodeValue;
251             next = null;
252         }
253         public Node(object nodeValue, Node next)
254         {
255             this.nodeValue = nodeValue;
256             this.next = next;
257         }
258     }
259 
260     class SingleLinkedList:ILinearList
261     {
262         public Node Head { get; set; }       //单链表
263         public SingleLinkedList() { 
264         
265         }
266 
267         public SingleLinkedList(Node head)
268         {
269             this.Head = head;
270         }
271 
272         public bool IsEmpty()
273         {
274             return Head == null;
275         }
276 
277         public int Size()
278         {
279             int size = 0;
280             Node p = Head;
281             while (p != null)
282             {
283                 size++;
284                 p = p.next;
285             }
286             return size;
287         }
288 
289         public object Get(int index)
290         {
291             ILinearList list = this;
292             if(index < 0 || index > list.Size() - 1)
293             {
294                 throw new IndexOutOfRangeException("索引越界!");
295             }
296             Node p = Head;
297             for (int i = 0; i < index; i++)
298             {
299                 p = p.next;
300             }
301             return p.nodeValue;
302         }
303 
304         public object Set(int index, object elem)
305         {
306             ILinearList list = this;
307             if (index < 0 || index > list.Size() - 1)
308             {
309                 throw new IndexOutOfRangeException("索引越界!");
310             }
311             Node p = Head;
312             for (int i = 0; i < index; i++)
313             {
314                 p = p.next;
315             }
316             object oldValue = p.nodeValue;
317             p.nodeValue = elem;
318             return oldValue;
319         }
320 
321         public bool Add(int index, object elem)
322         {
323             ILinearList list = this;
324             if (index < 0 || index > list.Size())
325             {
326                 throw new IndexOutOfRangeException("索引越界!");
327             }
328 
329             if(Head == null)
330             {
331                 Head = new Node(elem);
332             }
333             else
334             {
335                 Node p = Head;
336                 for (int i = 0; i < index - 1; i++)
337                 {
338                     p = p.next;
339                 }
340                 p.next = new Node(elem,p.next);
341             }
342             return true;
343         }
344 
345         public object Remove(int index)
346         {
347             object oldValue = null;
348             if(index >=0 && Head != null)
349             {
350                 if(index == 0)
351                 {
352                     oldValue = Head.nodeValue;
353                     Head = Head.next;
354                 }
355                 else
356                 {
357                     Node p = Head;
358                     for (int i = 0; i < index - 1 && p.next != null; i++)
359                     {
360                         p = p.next;
361                     }
362                     if (p.next != null)
363                     {
364                         oldValue = p.next.nodeValue;
365                         p.next = p.next.next;
366                     }
367                 }
368                 
369             }
370             return oldValue;
371         }
372 
373         public void Clear()
374         {
375             Head = null;
376         }
377     }
378 }