数据结构之单向链表

单向链表：

学习目标：

• 掌握什么是单向链表
• 单向链表的实际运用
• C#中如何实现单向链表

---

学习内容：

1. 了解何为单向链表
2. 了解单向链表的优缺点
3. 了解单向链表在实际开发中的应用
4. 掌握用C#实现单向链表

---

何为单向链表：

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

---

单向链表的优缺点：

优点：

1. 插入和删除速度快，保留原有的物理顺序，在插入或者删除一个元素的时候，只需要改变指针指向即可。
2. 没有空间限制,存储元素无上限,只与内存空间大小有关。
3. 动态分配内存空间，不用事先开辟内存

缺点：

1. 占用额外的空间以存储指针，比较浪费空间，不连续存储，malloc函数开辟空间碎片比较多
2. 查找速度比较慢，因为在查找时，只能顺序查找，需要循环链表

---

单向链表在实际开发中的应用

例如展示职工信息的时候，按照编号进行递增排序，或者在某些数据进行在后台处理进行排序的时候可以使用链表，例如名次排列，成绩排列等。

C# 实现单向链表：

interface Queue<T>
{
    int getSize();
    bool isEmpty();
    void enqueue(T data);
    T dequeue();
    /// 

    /// 查看栈顶元素
    /// 
    /// 
    T getFront();
}
public class LinkedListQueue<T> : Queue<T>
{
    public class Node
    {
        public T data;
        public Node next;
        public Node(T data, Node next)
        {
            this.data = data;
            this.next = next;
        }
        public Node(T data) : this(data, null)
        {
 
        }
        public Node() : this(default(T), null)
        {
        }
        public override string ToString()
        {
            return data.ToString();
        }
    }
    public Node head, tail;
    private int size;
    public LinkedListQueue()
    {
        head = null;
        tail = null;
        size = 0;
    }
    public T dequeue()
    {
        if (isEmpty())
        {
            throw new System.Exception("size is 0  no dequue");
        }
        Node node = head;
        head = node.next;
        node.next = null;
        if (head == null)
        {
            tail = null;
        }
        size--;
        return node.data;
    }
 
    public void enqueue(T data)
    {
        //如果头是空的情况下 tail 才是空的
        if (tail == null)
        {
            tail = new Node(data);
            head = tail;
        }
        else
        {
            tail.next = new Node(data);
            this.tail = tail.next;
        }
        size++;
    }
 
    public T getFront()
    {
        if (isEmpty())
        {
            throw new System.Exception("size is 0  no dequue");
        }
        return head.data;
    }
 
    public int getSize()
    {
        return size;
    }
 
    public bool isEmpty()
    {
        return size == 0;
    }
    public override string ToString()
    {
        System.Text.StringBuilder stringBuilder = new System.Text.StringBuilder();
        stringBuilder.Append("queue : front");
        Node cur = head;
        while (cur != null)
        {
            stringBuilder.Append(cur + "->");
            cur = cur.next;
 
        }
        stringBuilder.Append("Null tail");
        return stringBuilder.ToString();
    }
}
 
interface Stack<T>
{
    int getSize();
    bool isEmpty();
    void push(T data);
    T pop();
    /// 

    /// 查看栈顶元素
    /// 
    /// 
    T peek();
}
 
 
public class LinkedListStack<T> : Stack<T>
{
    private LinkedList<T> list;
    public LinkedListStack()
    {
        list = new LinkedList<T>();
    }
    public int getSize()
    {
        return list.getSize();
    }
 
    public bool isEmpty()
    {
        return list.getSize() == 0;
    }
 
    public T peek()
    {
        return list.getFirst();
    }
 
    public T pop()
    {
        return list.removeFirst();
    }
 
    public void push(T data)
    {
        list.addFirst(data);
    }
    public override string ToString()
    {
        System.Text.StringBuilder stringBuilder = new System.Text.StringBuilder();
        stringBuilder.Append(" stack :top");
        stringBuilder.Append(list);
        return stringBuilder.ToString();
    }
}
 
 
 
 
public class LinkedList<T>
{
    private class Node
    {
        public T data;
        public Node next;
 
        public Node(T data, Node next)
        {
            this.data = data;
            this.next = next;
        }
        public Node(T data) : this(data, null)
        {
 
        }
        public Node() : this(default(T), null)
        {
        }
        public override string ToString()
        {
            return data.ToString();
        }
    }
    // private Node head = null;
    /// 

    /// 虚拟头结点
    /// 
    private Node dummyHead = null;
    private int size;
    public LinkedList()
    {
        // head = null;
        dummyHead = new Node();
        size = 0;
    }
    public int getSize()
    {
        return size;
    }
    public bool usEmpty()
    {
        return size == 0;
    }
    public void addFirst(T data)
    {
        Add(data, 0);
    }
    public void Add(T data, int index)
    {
        if (index < 0 || index > size)
            throw new System.Exception("add failed,allegal index");
        Node prev = dummyHead;
        for (var i = 0; i < index; i++)
        {
            prev = prev.next;
        }
        // System.Console.WriteLine(data);
        prev.next = new Node(data, prev.next);
        size++;
    }
    public void AddLast(T data)
    {
        Add(data, size);
    }
    public T get(int index)
    {
        if (index < 0 || index >= size)
            throw new System.Exception("get failed illegal index.");
 
        Node curr = dummyHead.next;
        for (var i = 0; i < index; i++)
        {
            curr = curr.next;
        }
        return curr.data;
    }
    public T getFirst()
    {
        return get(0);
    }
    public T getLast()
    {
        return get(size - 1);
    }
    public void Set(int index, T data)
    {
        if (index < 0 || index >= size)
            throw new System.Exception("set failed illegal index.");
        Node curr = dummyHead.next;
        for (var i = 0; i < index; i++)
        {
            curr = curr.next;
        }
        curr.data = data;
    }
    public bool contains(T data)
    {
        Node curr = dummyHead.next;
        while (curr != null)
        {
            if (curr.data.Equals(data))
            {
                return true;
            }
 
        }
        return false;
    }
    public override string ToString()
    {
        System.Text.StringBuilder stringBuilder = new System.Text.StringBuilder();
        Node curr = dummyHead.next;
        while (curr != null)
        {
            stringBuilder.Append(curr + "=>");
            curr = curr.next;
        }
        stringBuilder.Append("NULL");
        return stringBuilder.ToString();
    }
    public T Remove(int index)
    {
        Node prev = dummyHead;
        for (var i = 0; i < index; i++)
        {
            prev = prev.next;
        }
        Node node = prev.next;
        prev.next = node.next;
        node.next = null;
        size--;
        return node.data;
    }
    public T removeFirst()
    {
        return Remove(0);
    }
    public T removeLast()
    {
        return Remove(size - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310