一、链表
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 /// <summary>
9 /// ListNode类定义
10 /// </summary>
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 /// <summary>
47 /// List类定义
48 /// </summary>
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 /// <summary>
70 /// 在列表前端插入元素,如果链表是空的,firstNode和lastNoede指向同一个节点。否则,firstNode指向新节点
71 /// </summary>
72 /// <param name="insertItem"></param>
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 /// <summary>
89 /// 在链表尾端插入元素,如果链表是空的,firstNode和lastNoede指向同一个节点。否则,lastNoede指向新节点
90 /// </summary>
91 /// <param name="insertItem"></param>
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 /// <summary>
108 /// 删除链表的第一个节点
109 /// </summary>
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 /// <summary>
136 /// 删除链表中的最后一个节点
137 /// </summary>
138 /// <returns></returns>
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 /// <summary>
175 /// 判断链表是否为空,即判断首节点是否为空
176 /// </summary>
177 /// <returns></returns>
178 public bool IsEmpty()
179 {
180 lock (this)
181 {
182 return firstNode == null;
183 }
184 }
185
186 /// <summary>
187 /// 输出链表内容
188 /// </summary>
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 /// <summary>
216 /// 链表异常类
217 /// </summary>
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();
}
}
}