陈留阳
0%

数据结构——链表

发表于 更新于 分类于

数据结构是一个早就有所耳闻的东西，但是一直没有潜下心学习过，对数据结构的了解也仅限于 C++里的 STL，趁寒假有空闲，去听了浙江大学陈越老师的数据结构课程。当然，计算机领域的各种知识，只有亲自尝试了才能算是真的学得懂，因此，打算开个专题，将各个类型的数据结构都亲自实现一遍，并记录下来。

链表

以下内容摘自维基百科

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到 O(1)的复杂度，但是查找一个节点或者访问特定编号的节点则需要 O(n)的时间。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

实现

本次实现是拿 C 语言实现的，但是因为个人编程习惯的原因，将 int 包装成了 bool 类型并使用。多数函数采用 bool 作为返回值，用于检查是否执行成功。

节点

链表的一个很重要的特点是其结构由一些节点连接起来，各个节点是组成链表的最小单位。

一个节点由数据域和指针域组成，考虑用结构来表示。为表示方便，包装一个链表的数据类型。

1
2
3
4
5
6
typedef struct Node
{
    ElementType data;
    struct Node *next;
} Node;
typedef Node *LinkList;

创建

创建链表有两种基本的方式，分别是有头结点的链表和没有头结点的链表，在实际实现过程中，有头结点的链表实现起来更安全，也更加容易，因此采用有头结点的链表。

所以创建链表实际上就是建立了一个头结点，数据域不重要，指针域指向 NULL。

1
2
3
4
5
6
7
LinkList CreateLink()
{
    //新建一个链表
    LinkList link = (LinkList)malloc(sizeof(Node));
    link->next = NULL;
    return link;
}

插入节点

在索引为index的位置插入值为data的节点。

假设在索引为 (index-1) 的位置有节点node1，索引为 (index) 的位置有节点node2,则node1指向node2。

实现的思路是先新建一个节点node3,先让node3指向node2,然后让node1指向node3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool InsertData(const LinkList linkList, unsigned const int index, const ElementType data)
{
    //在对应索引的位置插入节点
    Node *iterator = linkList->next;
    int i = 0;
    for (; iterator; i++, iterator = iterator->next)
    {
        if (i == index - 1)
        {
            Node *node = (Node *)malloc(sizeof(Node));
            if (node)
            {
                node->data = data;
                node->next = iterator->next;
                iterator->next = node;
                return true;
            }
            return false;
        }
    }
    return false;
}

删除节点

删除索引为index的节点。

假设有连续三个节点node1，node2，node3，想要删除node2节点，只需要让node1的指针域指向node3，然后回收node2节点的内存即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool DeleteDataByIndex(const LinkList linkList, unsigned const int index)
{
    //删除对应索引的的节点
    Node *beforeIterator = linkList;
    Node *deleteIterator = linkList->next;
    int i = 0;
    for (; deleteIterator; i++, beforeIterator = deleteIterator, deleteIterator = deleteIterator->next)
    {
        if (i == index)
        {
            beforeIterator->next = deleteIterator->next;
            free(deleteIterator);
            return true;
        }
    }
    return false;
}

修改节点

修改索引为index的节点值为data。

基本思路来就是定位到索引的位置，然后修改具体的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool ChangeDataByIndex(const LinkList linkList, unsigned const int index, const ElementType data)
{
    //修改索引对应的节点
    Node *iterator = linkList->next;
    int i = 0;
    for (; iterator; i++, iterator = iterator->next)
    {
        if (i == index)
        {
            iterator->data = data;
            return true;
        }
    }
    return false;
}

反转

反转整条链表。

最开始我以为实现这个的做法改成双向链表，然后做标记，但后来才了解到,的确是一条单向链表的反转,而且实现过程相当巧妙。

基本思路是：

  1. 用三个指针记录下连续的三个节点地址
  2. 修改第二个节点的next使其指向第一个节点
  3. 三个指针后移
  4. 如果没有到达末尾，返回1
  5. 修改头指针和第一个节点的next
  6. 反转结束

不过要注意的是，节点数较少时要做特殊处理。

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
void ReverseLink(const LinkList linkList)
{
    //反转链表
    Node *first = linkList->next;
    if (!first || !first->next)
    {
        return;
    }
    Node *second = first->next;
    if (!second->next)
    {
        linkList->next = second;
        second->next = first;
        first->next = NULL;
        return;
    }
    Node *third = second->next;

    while (true)
    {
        second->next = first;
        first = second;
        second = third;
        if (!third)
        {
            break;
        }
        third = third->next;
    }
    linkList->next->next = NULL;
    linkList->next = first;
}

排序

将整条链排序

emm…，学习过之后才发现链表竟然如此神奇，本来我以为链表只能访问相邻的元素顶多就冒泡排序了。

结果，至少可以冒泡、选择、插入、快排、归并、希尔、堆排序等等……

十大排序

都可以用得上눈_눈

先贴上一位大佬的文章，本次排序的实现正是基于此篇文章。

点击前往大佬的文章

采取的是归并排序，这应该是最适合链表的排序方式了。

归并排序的第一步是将整个链表从中间分开，我当时还在想怎么可能定位到正中间，然后就被惊艳了。

定位的方法是快慢指针法，简单地说，使用两根指针同时从头出发，慢指针每次前进一个节点，快指针每次前进两个节点，这样，当快指针到达末尾的时候，慢指针差不多到达了一半的位置。

当定位到中点后，将一条链表劈成两半，分别递归排序两端链表(为了排序方便，使用没有头结点的链表)。

如果链表只有一个节点则自然有序

最后，将两条排好序的链表归并连接起来。相较于数组的归并排序，链表结构的独特性使得完全不用开辟额外空间。

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
void SortLink(const LinkList linkList)
{
    //排序链表
    //预处理成没有头结点的链表
    linkList->next = MergeSort(linkList->next);
}

Node *MergeSort(Node *begin)
{
    //归并排序
    Node *fast = begin, *slow = begin;
    if (begin == NULL || begin->next == NULL)
    {
        return begin;
    }
    while (fast->next && fast->next->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow;
    fast->next = NULL;
    slow = slow->next;
    fast = MergeSort(begin);
    slow = MergeSort(slow);
    return Merge(fast, slow);
}

Node *Merge(Node *first, Node *second)
{
    //合并两链表
    Node *ret = NULL;
    Node *iterator = ret;
    while (first && second)
    {
        if (first->data < second->data)
        {
            if (iterator)
            {
                iterator->next = first;
                iterator = iterator->next;
                first = first->next;
            }
            else
            {
                ret = first;
                iterator = first;
                first = first->next;
            }
        }
        else
        {
            if (iterator)
            {
                iterator->next = second;
                iterator = iterator->next;
                second = second->next;
            }
            else
            {
                ret = second;
                iterator = second;
                second = second->next;
            }
        }
    }
    if (first)
    {
        iterator->next = first;
    }
    else
    {
        iterator->next = second;
    }
    return ret;
}

代码

除此之外，再加一些简单的函数，全部代码如下：

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
#include <stdio.h>
#include <stdlib.h>

#define ElementType int
#define Out "%d"

#define bool int
#define true 1
#define false 0

typedef struct Node
{
    ElementType data;
    struct Node *next;
} Node;
typedef Node *LinkList;

LinkList CreateLink()
{
    //新建一个链表
    LinkList link = (LinkList)malloc(sizeof(Node));
    link->next = NULL;
    return link;
}

bool AddDataAtLast(const LinkList linkList, const ElementType data)
{
    //在链表末尾增加一个节点
    Node *last = linkList;
    while (last->next)
    {
        last = last->next;
    }
    last->next = (LinkList)malloc(sizeof(Node));
    if ((last = last->next))
    {
        last->data = data;
        last->next = NULL;
        return true;
    }
    return false;
}

bool AddDataAtBegin(const LinkList linkList, const ElementType data)
{
    //在链表起始增加一个节点
    Node *begin = linkList;
    Node *node = (Node *)malloc(sizeof(Node));
    if (node)
    {
        node->data = data;
        node->next = begin->next;
        begin->next = node;
        return true;
    }
    return false;
}

bool InsertData(const LinkList linkList, unsigned const int index, const ElementType data)
{
    //在对应索引的位置插入节点
    Node *iterator = linkList->next;
    int i = 0;
    for (; iterator; i++, iterator = iterator->next)
    {
        if (i == index - 1)
        {
            Node *node = (Node *)malloc(sizeof(Node));
            if (node)
            {
                node->data = data;
                node->next = iterator->next;
                iterator->next = node;
                return true;
            }
            return false;
        }
    }
    return false;
}

bool DeleteDataByIndex(const LinkList linkList, unsigned const int index)
{
    //删除对应索引的的节点
    Node *beforeIterator = linkList;
    Node *deleteIterator = linkList->next;
    int i = 0;
    for (; deleteIterator; i++, beforeIterator = deleteIterator, deleteIterator = deleteIterator->next)
    {
        if (i == index)
        {
            beforeIterator->next = deleteIterator->next;
            free(deleteIterator);
            return true;
        }
    }
    return false;
}

bool DeleteDataByValue(const LinkList linkList, const ElementType data)
{
    //删除该值第一次出现的结点
    Node *beforeIterator = linkList;
    Node *deleteIterator = linkList->next;
    for (; deleteIterator; beforeIterator = deleteIterator, deleteIterator = deleteIterator->next)
    {
        if (deleteIterator->data == data)
        {
            beforeIterator->next = deleteIterator->next;
            free(deleteIterator);
            return true;
        }
    }
    return false;
}

bool ChangeDataByIndex(const LinkList linkList, unsigned const int index, const ElementType data)
{
    //修改索引对应的节点
    Node *iterator = linkList->next;
    int i = 0;
    for (; iterator; i++, iterator = iterator->next)
    {
        if (i == index)
        {
            iterator->data = data;
            return true;
        }
    }
    return false;
}

bool TryFindDataByValue(const LinkList linkList, const ElementType data, int *index)
{
    //查找该值第一次出现的节点的索引
    Node *iterator = linkList->next;
    for ((*index) = 0; linkList; (*index)++, iterator = iterator->next)
    {
        if (iterator->data == data)
        {
            return true;
        }
    }
    (*index) = -1;
    return false;
}

bool TryFindDataByIndex(const LinkList linkList, unsigned const int index, ElementType *data)
{
    //根据索引查找对应的值
    Node *iterator = linkList->next;
    int i = 0;
    for (; iterator; i++, iterator = iterator->next)
    {
        if (i == index)
        {
            (*data) = iterator->data;
            return true;
        }
    }
    return false;
}

void ReverseLink(const LinkList linkList)
{
    //反转链表
    Node *first = linkList->next;
    if (!first || !first->next)
    {
        return;
    }
    Node *second = first->next;
    if (!second->next)
    {
        linkList->next = second;
        second->next = first;
        first->next = NULL;
        return;
    }
    Node *third = second->next;

    while (true)
    {
        second->next = first;
        first = second;
        second = third;
        if (!third)
        {
            break;
        }
        third = third->next;
    }
    linkList->next->next = NULL;
    linkList->next = first;
}

void SortLink(const LinkList linkList)
{
    //排序链表
    //预处理成没有头结点的链表
    linkList->next = MergeSort(linkList->next);
}

Node *MergeSort(Node *begin)
{
    //归并排序
    Node *fast = begin, *slow = begin;
    if (begin == NULL || begin->next == NULL)
    {
        return begin;
    }
    while (fast->next && fast->next->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow;
    slow = slow->next;
    fast->next = NULL;
    fast = MergeSort(begin);
    slow = MergeSort(slow);
    return Merge(fast, slow);
}

Node *Merge(Node *first, Node *second)
{
    //合并两链表
    Node *ret = NULL;
    Node *iterator = ret;
    while (first && second)
    {
        if (first->data < second->data)
        {
            if (iterator)
            {
                iterator->next = first;
                iterator = iterator->next;
                first = first->next;
            }
            else
            {
                ret = first;
                iterator = first;
                first = first->next;
            }
        }
        else
        {
            if (iterator)
            {
                iterator->next = second;
                iterator = iterator->next;
                second = second->next;
            }
            else
            {
                ret = second;
                iterator = second;
                second = second->next;
            }
        }
    }
    if (first)
    {
        iterator->next = first;
    }
    else
    {
        iterator->next = second;
    }
    return ret;
}

unsigned int LinkLength(const LinkList linkList)
{
    //返回链表的长度
    Node *iterator = linkList->next;
    unsigned int i = 0;
    for (; iterator; i++, iterator = iterator->next)
        ;
    return i;
}

void ShowLink(const LinkList linkList)
{
    //展示链表
    Node *iterator = linkList->next;
    printf("Head => ");
    while (iterator)
    {
        printf(Out " => ", iterator->data);
        iterator = iterator->next;
    }
    printf("NULL\n");
}

void ClearLink(const LinkList linkList)
{
    //清空链表
    if (linkList->next)
    {
        ClearLink(linkList->next);
        free(linkList->next);
        linkList->next = NULL;
    }
    return;
}

留个空白，之后拿 C++封装成类再实现一遍。😁

模板类实现

2019 年 2 月 15 日更新

模仿STL 里的 List写的方法，为了实现一些功能硬是把单链表写成了双向链表，加上了头尾指针，心累 o(T ヘ To)，一些琐碎的细节折磨了很久(才没有去刷知乎(,,• ₃ •,,))，一天终于实现了，代码如下。(虽然还是有不安全的问题吧……

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
template <class T>
class Node
{
  public:
    Node();
    Node(T data, Node *prev = nullptr, Node *next = nullptr);
    T data;
    Node *next, *prev;
};

template <class T>
Node<T>::Node()
{
    this->next = nullptr;
    this->prev = nullptr;
}

template <class T>
Node<T>::Node(T data, Node *prev, Node *next)
{
    this->data = data;
    this->prev = prev;
    this->next = next;
}

template <class T>
class LinkList
{
  public:
    LinkList();

    T front();
    T back();

    bool empty();
    unsigned int size();

    void clear();
    void insert(int index, T data);
    void erase(int index);
    void push_front(T data);
    void push_back(T data);
    void pop_front();
    void pop_back();
    void reverse();
    void sort();

  private:
    Node<T> *head, *tail;
    unsigned int length;
    Node<T> *MergeSort(Node<T> *begin);
    Node<T> *Merge(Node<T> *first, Node<T> *second);
};

template <class T>
LinkList<T>::LinkList()
{
    this->head = new Node<T>();
    this->tail = new Node<T>();
    this->head->next = tail;
    this->tail->prev = head;
    this->length = 0;
}

template <class T>
T LinkList<T>::front()
{
    return this->head->next->data;
}

template <class T>
T LinkList<T>::back()
{
    return this->tail->prev->data;
}

template <class T>
bool LinkList<T>::empty()
{
    return this->head->next == tail;
}

template <class T>
unsigned int LinkList<T>::size()
{
    return this->length;
}

template <class T>
void LinkList<T>::clear()
{
    Node<T> *temp = nullptr;
    for (Node<T> *iterator = this->head->next; iterator != this->tail;)
    {
        temp = iterator;
        iterator = iterator->next;
        delete temp;
    }
    this->head->next = this->tail;
    this->tail->prev = this->head;
}

template <class T>
void LinkList<T>::insert(int index, T data)
{
    Node<T> *iterator = this->head->next;
    for (int i = 0; iterator != this->tail; i++, iterator = iterator->next)
    {
        if (i == index - 1)
        {
            Node<T> *prev = iterator;
            Node<T> *next = iterator->next;
            Node<T> *temp = new Node<T>(data, prev, next);
            prev->next = temp;
            next->prev = temp;
            this->length++;
            return;
        }
    }
}

template <class T>
void LinkList<T>::erase(int index)
{
    Node<T> *iterator = this->head->next;
    for (int i = 0; iterator != this->tail; i++, iterator = iterator->next)
    {
        if (i == index)
        {
            Node<T> *prev = iterator->prev;
            Node<T> *next = iterator->next;
            prev->next = next;
            next->prev = prev;
            delete iterator;
            this->length--;
            return;
        }
    }
}

template <class T>
void LinkList<T>::push_front(T data)
{
    Node<T> *temp = new Node<T>(data, this->head, this->head->next);
    temp->prev->next = temp;
    temp->next->prev = temp;
    this->length++;
}

template <class T>
void LinkList<T>::push_back(T data)
{
    Node<T> *temp = new Node<T>(data, this->tail->prev, this->tail);
    temp->prev->next = temp;
    temp->next->prev = temp;
    this->length++;
}

template <class T>
void LinkList<T>::pop_front()
{
    Node<T> *temp = this->head->next;
    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;
    delete temp;
    this->length--;
}

template <class T>
void LinkList<T>::pop_back()
{
    Node<T> *temp = this->tail->prev;
    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;
    delete temp;
    this->length--;
}

template <class T>
void LinkList<T>::reverse()
{
    if (this->length == 0 || this->length == 1)
    {
        return;
    }
    else if (this->length == 2)
    {
        T temp = this->head->next->data;
        this->head->next->data = this->tail->prev->data;
        this->tail->prev->data = temp;
        return;
    }
    Node<T> *first = head->next;
    Node<T> *second = first->next;
    Node<T> *third = second->next;
    while (true)
    {
        second->next = first;
        first->prev = second;
        first = second;
        second = third;
        if (third == this->tail)
        {
            break;
        }
        third = third->next;
    }
    this->head->next->next = this->tail;
    this->tail->prev = this->head->next;
    this->head->next = first;
    first->prev = this->head;
}

template <class T>
void LinkList<T>::sort()
{
    this->head->next = MergeSort(head->next);
    for (Node<T> *iterator = this->head; iterator->next; iterator = iterator->next)
    {
        iterator->next->prev = iterator;
    }
}

template <class T>
Node<T> *LinkList<T>::MergeSort(Node<T> *begin)
{
    Node<T> *fast = begin, *slow = begin;
    if (begin == this->tail || begin->next == this->tail)
    {
        return begin;
    }
    while (fast->next != this->tail && fast->next->next != this->tail)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow;
    slow = slow->next;
    fast->next = this->tail;
    fast = MergeSort(begin);
    slow = MergeSort(slow);
    return Merge(fast, slow);
}

template <class T>
Node<T> *LinkList<T>::Merge(Node<T> *first, Node<T> *second)
{
    Node<T> *ret = nullptr;
    Node<T> *iterator = ret;
    while (first != this->tail && second != this->tail)
    {
        if (first->data < second->data)
        {
            if (iterator)
            {
                iterator->next = first;
                iterator = iterator->next;
                first = first->next;
            }
            else
            {
                ret = first;
                iterator = first;
                first = first->next;
            }
        }
        else
        {
            if (iterator)
            {
                iterator->next = second;
                iterator = iterator->next;
                second = second->next;
            }
            else
            {
                ret = second;
                iterator = second;
                second = second->next;
            }
        }
    }
    if (first != this->tail)
    {
        iterator->next = first;
    }
    else
    {
        iterator->next = second;
    }
    return ret;
}