【C#】实现链表
任务
链表的实现任务
实现目标：（1）实现一个链表
（2）链表可以增，删，改，查；
（3）可以输出信息；
实现过程：
（1）创建一个新的类，包含一个内部类作为链表的结点框架；
（2）创建构造函数，分别是一个参数的构造函数与无参数的构造函数；
（3）实现增功能，允许按照下标添加；
（4）实现查询功能，按照下标查询，按照给出元素查询；
（5）实现删除功能，按照下标删除某个元素，按照给出元素删除，删除所有元素；
（7）实现修改功能，按照下标修改，按照给出元素修改；
（8）实现输出函数；
重点：
（1）内部类的构建
1 ///
（2）当添加第一个node结点作为头结点时为什么不直接赋值node.next=null,而是node.next=head;
//Node node = new(e); ////↓node为头结点为什么next不直接赋值null而是赋值head; //node.next = head; //head = node; ////等价于↓ head = new(e, head); //因为使用头插法（即插入一个新的头结点）时会断开后面所有结点的链接, //head仅是保存目标是头结点的结点
（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 LinkedList110 { 11 /// 12 /// 内部类，作为链表的结点使用 13 /// 14 private class Node 15 { 16 //定义一个泛型的字段存储数据 17 public E e; 18 //定义链表的下一个结点指针 19 public Node next; 20 /// 21 /// 可以传入数据和一个结点指针的构造函数 22 /// 23 /// 24 /// 25 public Node(E e,Node next) 26 { 27 this.e = e; 28 this.next = next; 29 } 30 /// 31 /// 可以创建作为尾部的结点的构造函数 32 /// 33 /// 34 public Node(E e) 35 { 36 this.e = e; 37 this.next = null; 38 } 39 /// 40 /// 打印该结点则返回该结点的E型数据 41 /// 42 /// 43 public override string ToString() 44 { 45 return e.ToString(); 46 } 47 } 48 //头结点 49 private Node head; 50 //结点个数; 51 private int N; 52 /// 53 /// 无参构造函数 54 /// 55 public LinkedList1() 56 { 57 head = null; 58 N = 0; 59 } 60 //链表长度 61 public int Count { get { return N; } } 62 //链表是否为空 63 public bool IsEmpty { get { return N==0; } } 64 /// 65 /// 添加结点 66 /// 67 /// 68 /// 69 public void Add(int index,E e) 70 { 71 if (index<0 || index>N) 72 { 73 throw new ArgumentException("非法索引"); 74 } 75 if (index == 0) 76 { 77 ////为什么不直接赋值null而是赋值head; 78 //Node node = new(e); 79 //node.next = head; 80 //head = node; 81 ////等价于↓ 82 head = new(e, head); 83 } 84 else 85 { 86 Node pre = head; 87 //按照0为起点开始数，并非从1开始数 88 for (int i = 0; i < index - 1; i++) 89 { 90 pre = pre.next; 91 } 92 //Node node = new(e); 93 //node.next = pre.next; 94 //pre.next = node; 95 ////等价于↓ 96 pre.next = new(e, pre.next); 97 } 98 N++; 99 } 100 //头部添加结点 101 public void AddFirst(E e) 102 { 103 Add(0, e); 104 } 105 //尾部添加结点 106 public void AddLast(E e) 107 { 108 Add(N,e); 109 } 110 /// 111 /// 按照下标删除结点 112 /// 113 /// 114 /// 115 public E RemoveAt(int index) 116 { 117 if (index < 0 || index >= N) 118 { 119 throw new ArgumentException("非法索引"); 120 } 121 Node pre = head; 122 if (index ==0) 123 { 124 head = pre.next; 125 N--; 126 return pre.e; 127 } 128 for (int i = 0; i < index-1; i++) 129 { 130 pre = pre.next; 131 } 132 Node rm = new(pre.next.e,null); 133 pre.next = pre.next.next; 134 N--; 135 return rm.e; 136 } 137 /// 138 /// 按照元素删除结点 139 /// 140 /// 141 public void Remove(E e) 142 { 143 if (head ==null) 144 { 145 return; 146 } 147 Node cur = head; 148 Node pre = null; 149 while (cur!=null) 150 { 151 if (cur.e.Equals(e)) 152 { 153 break; 154 } 155 pre = cur; 156 cur = cur.next; 157 } 158 if (pre==null) 159 { 160 head = head.next; 161 N--; 162 } 163 else if(cur!=null) 164 { 165 pre.next = cur.next; 166 N--; 167 } 168 ////也可这样实现↓ 169 //Node cur = head.next; 170 //Node pre = head; 171 //for (int i = 0; i < N-1; i++) 172 //{ 173 // if (pre.e.Equals(e)) 174 // { 175 // head = head.next; 176 // break; 177 // } 178 // else if(cur.e.Equals(e)) 179 // { 180 // pre.next = cur.next; 181 // break; 182 // } 183 // pre = cur; 184 // cur = cur.next; 185 //} 186 } 187 public E RemoveFirst() 188 { 189 return RemoveAt(0); 190 } 191 public E RemoveLast() 192 { 193 return RemoveAt(N-1); 194 } 195 /// 196 /// 修改结点数据 197 /// 198 /// 199 /// 200 public void Set(int index,E e) 201 { 202 if (index < 0 || index >= N) 203 { 204 throw new ArgumentException("非法索引"); 205 } 206 Node cur = head; 207 for (int i = 0; i < index; i++) 208 { 209 cur = cur.next; 210 } 211 cur.e = e; 212 } 213 /// 214 /// 获取结点数据 215 /// 216 /// 217 /// 218 public E Get(int index) 219 { 220 if (index < 0 || index >= N) 221 { 222 throw new ArgumentException("非法索引"); 223 } 224 Node cur = head; 225 for (int i = 0; i < index; i++) 226 { 227 cur = cur.next; 228 } 229 return cur.e; 230 } 231 /// 232 /// 获取第一个数据 233 /// 234 /// 235 public E GetFirst() 236 { 237 return Get(0); 238 } 239 /// 240 /// 获取最后一个数据 241 /// 242 /// 243 public E GetLast() 244 { 245 return Get(N-1); 246 } 247 /// 248 /// 打印输出结点，也可以直接重写ToString方法实现 249 /// 250 public void Print() 251 { 252 Node pri = head; 253 for (int i = 0; i < N; i++) 254 { 255 Console.Write(pri+" "); 256 pri = pri.next; 257 } 258 Console.WriteLine(); 259 } 260 /// 261 /// 重写ToString方法，打印输出链表 262 /// 263 /// 264 public override string ToString() 265 { 266 StringBuilder res = new(); 267 Node cur = head; 268 while (cur !=null) 269 { 270 res.Append(cur + "->"); 271 cur = cur.next; 272 } 273 res.Append("Null\n"); 274 return res.ToString(); 275 } 276 } 277 }