一、链表 1.“连成一行”的、线性的数据项集合——用户可以在链表中的任何位置插入或删除数据。链表是自引用对象的线性集合（即序列）。其中的自引用类对象称为节点，节点之间通过引用（C/C++中叫做指针，高级语言称作引用）来链接，这便是“链表”一词的由来！程序通过首节点引用来访问链表，通过保存在前一个节点中的链接引用成员访问后继节点。习惯上将最后一个节点（即尾节点）的链接引用设为“null”表示链表结束。数据动态保存在链表中，程序员可以根据需要创建节点。节点中可以包含任意类型的数据，甚至是其他类型的对象。 2. 堆栈和队列也是线性数据结构，而且是一种受约束的链表。树却是非线性数据结构。
数组和链表比较：
1. 数组在构造时已确定大小，不能动态的根据需要分配内存。
2. 在链表中插入数据，只需修改两个引用，而数组需要移动N个元素。
3. 查找元素的时候，数组直接通过下标查找，效率会比链表快一些。链表访问元素只能从链表头开始遍历。
下面用C#语言实现单链表的基本操作。
开始写代码。新建一个控制台项目。
然后，新建类文件LinkedListLibrary.cs，写一个LinkList类，用来存放链表的属性和方法。
解释见注释。
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 6 namespace LinkedList 7 { 8 ///
9 /// ListNode类定义 10 /// 11 class ListNode 12 { 13 private object data; 14 private ListNode next; 15 16 public ListNode(object dataValue) 17 : this(dataValue, null) 18 { 19 } 20 21 public ListNode(object dataValue, ListNode nextNodes) 22 { 23 data = dataValue; 24 next = nextNodes; 25 } 26 27 public object Data 28 { 29 get { return data; } 30 } 31 32 public ListNode Next 33 { 34 get 35 { 36 return next; 37 } 38 set 39 { 40 next = value; 41 } 42 43 } 44 } 45 46 ///
47 /// List类定义 48 /// 49 public class List 50 { 51 private ListNode firstNode; 52 private ListNode lastNoede; 53 private string name;//显示字符串用 54 55 public List(string listName) 56 { 57 name = listName; 58 firstNode = lastNoede = null; 59 } 60 61 public List() 62 : this("list") 63 { 64 } 65 66 // 当这些方法用于多线程程序时，要用一个lock块来保证List类的多线程安全 67 // 一个线程修改这些List对象内容时，其它线程不能同时修改这个对象 68 69 ///
70 /// 在列表前端插入元素，如果链表是空的，firstNode和lastNoede指向同一个节点。否则，firstNode指向新节点 71 /// 72 ///
73 public void InsertAtFront(object insertItem) 74 { 75 lock (this) 76 { 77 if (IsEmpty()) 78 { 79 firstNode = lastNoede = new ListNode(insertItem); 80 } 81 else 82 { 83 firstNode = new ListNode(insertItem, firstNode); 84 } 85 } 86 } 87 88 ///
89 /// 在链表尾端插入元素，如果链表是空的，firstNode和lastNoede指向同一个节点。否则，lastNoede指向新节点 90 /// 91 ///
92 public void InsertAtBack(object insertItem) 93 { 94 lock (this) 95 { 96 if (IsEmpty()) 97 { 98 firstNode = lastNoede = new ListNode(insertItem); 99 }
100 else
101 {
102 lastNoede = lastNoede.Next = new ListNode(insertItem);
103 }
104 }
105 }
106 107 ///
108 /// 删除链表的第一个节点
109 ///
110 public object RemoveFromFront()
111 {
112 lock (this)
113 {
114 if (IsEmpty())
115 {
116 throw new EmptyListException(name);
117 }
118 119 object removeItem = firstNode.Data;
120 121 // 重新分配引用
122 if (firstNode == lastNoede)
123 {
124 firstNode = lastNoede = null;
125 }
126 else
127 {
128 firstNode = firstNode.Next;
129 }
130 131 return removeItem;
132 }
133 }
134 135 ///
136 /// 删除链表中的最后一个节点
137 ///
138 ///
139 public object RemoveFromBack()
140 {
141 lock (this)
142 {
143 if (IsEmpty())
144 {
145 throw new EmptyListException(name);
146 }
147 148 object removeItem = lastNoede.Data;
149 150 //重新分配引用
151 if (firstNode == lastNoede)
152 {
153 firstNode = lastNoede = null;
154 }
155 else
156 {
157 ListNode current = firstNode;
158 159 //循环寻找lastNode
160 while (current.Next != lastNoede)
161 {
162 current = current.Next;
163 }
164 165 // current is a new lastNode
166 lastNoede = current;
167 current.Next = null;
168 }
169 170 return removeItem;
171 }
172 }
173 174 ///
175 /// 判断链表是否为空,即判断首节点是否为空
176 ///
177 ///
178 public bool IsEmpty()
179 {
180 lock (this)
181 {
182 return firstNode == null;
183 }
184 }
185 186 ///
187 /// 输出链表内容
188 ///
189 virtual public void Print()
190 {
191 lock (this)
192 {
193 if (IsEmpty())
194 {
195 Console.WriteLine("Empty " + name);
196 return;
197 }
198 199 Console.Write("The " + name + " is: ");
200 201 ListNode current = firstNode;
202 203 //循环遍历链表，输出Data
204 while (current != null)
205 {
206 Console.Write(current.Data + " ");
207 current = current.Next;
208 }
209 210 Console.WriteLine("\n");
211 }
212 }
213 }
214 215 ///
216 /// 链表异常类
217 ///
218 public class EmptyListException : ApplicationException
219 {
220 public EmptyListException(string name)
221 : base("The " + name + " is empty.")
222 {
223 224 }
225 }
226 }// end namespace LinkedList
LinkList类写好以后，我们就可以测试了。注意命名空间的引用。
测试文件：Program.cs
using System;
using LinkedListLibrary;
using StackInheritanceLibrary;
using QueueInheritanceLibrary; namespace ListTest
{ class ListTest { // 测试List static void Main(string[] args) { // 新建一个List List list = new List(); // 新建一些不同类型的测试数据 bool aBoolean = true; char aChar = '$'; int anIntger = 34567; string aString = "hello"; // use List insert methods list.InsertAtFront(aBoolean); list.Print(); list.InsertAtFront(aChar); list.Print(); list.InsertAtFront(anIntger); list.Print(); list.InsertAtFront(aString); list.Print(); // use Lsit remove methods object removedObject; try { removedObject = list.RemoveFromFront(); Console.WriteLine(removedObject + " removed."); list.Print(); removedObject = list.RemoveFromFront(); Console.WriteLine(removedObject + " removed."); list.Print(); removedObject = list.RemoveFromFront(); Console.WriteLine(removedObject + " removed."); list.Print(); removedObject = list.RemoveFromFront(); Console.WriteLine(removedObject + " removed."); list.Print(); } catch (EmptyListException emptyListException) { Console.Error.WriteLine("\n" + emptyListException); } Console.ReadKey(); } }
}
延伸阅读
最新评论