概述：

 由于顺序表插入和删除元素需要移动大量数据，导致运行效率下降。因此引入了另一种数据结构 —— 链表。链表又分为单链表和双链表。单链表结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

---

一. 单链表的定义

 单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。

构成：

 单链表由一系列节点组成，每个节点包含两个部分：数据域（存储数据元素）和指针域（存储下一个节点地址）。

typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType date;//数据域
struct SListNode* next;//指针域
}SLTNode;
1
2
3
4
5
6

特点：

1. 单链表的节点是离散分布在内存中的，通过指针将它们串联起来。
2. 单链表可以动态地分配内存空间，可以根据需要灵活地插入、删除节点。
   

---

二. 单链表的创建

typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType date;//数据域
struct SListNode* next;指针域
}SLTNode;
1
2
3
4
5
6

首先创建一个结构体struct SListNode用来存储数据和指针。
考虑到后续数据类型修改的方便性，我们将struct SListNode 用typedef重命名为SLNode。
同时为方便以后调用接口实现不同数据类型链接，我们将数据域的类型int重命名为SLDateType。(后续存储不停数据只需修改此处即可)

---

三、单链表各种接口实现

1. 动态申请一个结点

 后续要插入新节点时，首先要创建一个节点来存储相关信息，在连接到单链表合适位置。

代码实现：

SLTNode* BuySListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->date = x;
newnode->next = NULL;
return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

---

2. 单链表打印

打印单链表，我们只需记录头节点，然后遍历访问，依次打印即可。

代码实现：

void SLTPrint(SLTNode* phead)
{ 
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->date);
cur = cur->next;
}
printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10

---

3. 尾插

尾插分两种情况：没有节点和有节点。
①：没有节点：创建一个新节点，然后头指针指向新节点。
②：有节点：遍历找到最后一个节点，然后将其下一个节点指向新节点

代码实现：

//由于尾插第一种情况需要改变结构体指针，所以我们要传结构体二级指针
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)//没有节点
{
*pphead = newnode;
}
else
{
    //有节点
SLTNode* tail = *pphead;
while (tail->next)//遍历找到最后一个节点
{
tail = tail->next;
}
//尾插
tail->next = newnode;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

4. 头插

头插就相对简单。不管原链表有无节点，只需插入新节点即可。

代码实现：

//由于头插会改变头指针，所以我们传二级指针
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);//新节点
//头插
newnode->next = *pphead;
*pphead = newnode;
}
1
2
3
4
5
6
7
8
9

---

5. 尾删

尾删分3中情况：
①：首先要判断链表中是否还有节点可删。
②：链表中只有一个节点。一个节点比较简单，将头指针置空，然后释放头节点即可。
③：链表中有多个节点。多个节点，首先要遍历找到尾节点的前一个节点。然后将其指针域置空，并释放尾节点。

代码实现：

void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
//1.空
assert(*pphead);

if ((*pphead)->next == NULL)//2.一个节点
{
(*pphead)->next = NULL;
}
else
{
//3.多个节点
SLTNode* tail = *pphead;
遍历找到尾节点的前一个节点
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

6. 头删

头删分两种情况：
①：首先判断链表中是否还有节点可删。
②：链表还有节点可删。首先保存第二个节点，在释放头节点。并将头指针指向第二个节点。

代码实现：

void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
//空
assert(*pphead);
//非空
SLTNode* newnode = (*pphead)->next;//保存第二个节点
free(*pphead);//释放头节点
*pphead = newnode;
}
1
2
3
4
5
6
7
8
9
10

---

7、查找

查找和打印一样，直接遍历访问即可。找到了返回地址，没有找打返回空指针。

代码实现：

SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->date == x)
return cur;
cur = cur->next;
}
return NULL;
}
1
2
3
4
5
6
7
8
9
10
11

---

8、在pos之前插入x

链表中，不管是单链表还是双链表在某处插入新节点，一般默认前插。
前插分两种情况：
①：pos位置为第一个节点。可以复用前面头插接口实现。
②: 遍历访问链表找到pos前一个节点prev，然后将pos、prev、新节点连接起来。

代码实现：

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pphead);
assert(*pphead);
if (*pphead == pos)
{
SLTPushFront(pphead, x);//头插
}
else
{
SLTNode* prev = *pphead;
//遍历找到pos前一个节点
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
//prev,newnode,pos三个节点链接
prev->next = newnode;
newnode->next = pos;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

9、在pos后插入x

在pos之前插入x，相对来所比较复杂。所以如果没有特殊要求，可以采用pos后插。所以我们在这提供pos后插接口。

代码实现：

void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
assert(pos);

SLTNode* newnode = BuySListNode(x);
//后插
newnode->next = pos->next;
pos->next = newnode;
}
1
2
3
4
5
6
7
8
9

---

10、删除pos位置的值

删除pos位置的值一样分两种情况：
①：如果pos为头节点，复用头删接口。
②：遍历找到pos前一个节点prev。然后将pos前一个节点和后一个节点链接起来，并释放pos即可。

代码实现：

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);

if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}

prev->next = pos->next;
//free(pos);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

11、删除pos位置之后的值

要删除pos位置之后的值，我们首先将pos和pos后两个节点指针链接起来，并释放pos后一个节点即可。（要判断pos是否为尾节点）

代码实现：

void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
//检查pos是否为尾节点
assert(pos->next);

SLTNode* posNext = pos->next;
pos->next = posNext->next;

free(posNext);
posNext = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

---

12、销毁

代码实现：

void SLTDestory(SLTNode** pphead)
{
assert(pphead);

SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

四、所有代码展示

List.h:

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType date;
struct SListNode* next;
}SLTNode;


void SLTPrint(SLTNode* phead);

SLTNode* BuySListNode(SLTDateType x);

void SLTPushBack(SLTNode** pphead, SLTDateType x);
void SLTPushFront(SLTNode** pphead, SLTDateType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

SLTNode* SLTFind(SLTNode* phead, SLTDateType x);

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDateType x);
//删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos);

//销毁
void SLTDestory(SLTNode** pphead)
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

List.h:

include "SList.h"


void SLTPrint(SLTNode* phead)
{ 
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->date);
cur = cur->next;
}
printf("NULL\n");
}


SLTNode* BuySListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->date = x;
newnode->next = NULL;
return newnode;
}


void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}


void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}


void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
//1.空
assert(*pphead);

//2.一个节点
//3.多个节点
if ((*pphead)->next == NULL)
{
(*pphead)->next = NULL;
}
else
{
SLTNode* tail = *pphead;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}

}


void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
//空
assert(*pphead);
//非空
SLTNode* newnode = (*pphead)->next;
free(*pphead);
*pphead = newnode;
}

SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->date == x)
return cur;
cur = cur->next;
}
return NULL;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pphead);
assert(*pphead);
if (*pphead == pos)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}



void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
assert(pos);

SLTNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);

if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}

prev->next = pos->next;
//free(pos);
}
}


void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
//检查pos是否为尾节点
assert(pos->next);

SLTNode* posNext = pos->next;
pos->next = posNext->next;

free(posNext);
posNext = NULL;
}

void SLTDestory(SLTNode** pphead)
{
assert(pphead);

SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
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