链表的介绍、实现（C语言）及应用_c语言链表常用在什么场景

链表

注：会持续更新

首先我们先来看看链表的几个特点：离散的内存分布、快速插入/删除

最直观的就是将其和线性数据结构列表对比：

可见，链表的内存分布是离散的，想要知道其中一个目标结点的地址，首先要知道其前驱结点，根据前驱结点的指针来找到目标结点。

至于快速插入和删除的特点，先别急，我们先看下链表的分类。

常见种类：单向链表、双向链表、循环链表、双向循环链表

单向链表：

单链表即只能朝着一个方向去遍历，根据结点的next指针来找到目标结点，尾结点指向空指针NULL

双向链表：[java中的 LinkedHashMap就用的这个容器]

双向链表即只能朝着前后个方向去遍历，要想找到目标结点，需要先找到其前驱结点或后继结点根据next或pre指针找到目标结点，尾结点的next指向空指针，pre指针指向前一个结点。

循环链表：

循环链表就是尾结点的后继指针指向的是头节点，这样从链尾到链头就很方便。很适合解决“问题中带有循环提示的问题”

双向循环链表：

到这里，就算不给你双向链表的结构图你应该也能猜到了，是的，就是向双向链表一样每个结点加上前驱指针，头结点的前驱指针指向了最后的尾结点。

常见应用场景：

• LRU缓存淘汰算法
• CPU缓存、数据库缓存、浏览器缓存

为什么要有缓存淘汰算法？

因为缓存的大小有限，当缓存被用满时，应该决定哪些数据被清理出去，哪些应该被保留。

常见的有三种：

• 先进先出策略FIFO First in First out
• 最少使用策略LFU Least Frequently Used
• 最近最少使用策略LRU Least Recently Used

如何采用链表实现LRU：

• 维护一个有序单链表，越靠近链表尾部的结点是越早之前[即长时间没有访问了]访问的结点。
• 当有数据被访问时，从链表头开始顺序遍历链表。
  • 如果此数据已经被缓存在链表中了，则将其从链表中删除，然后插入至链表头部。
  • 如果没有在缓存链表中。
    • 如果缓存未满，直接插入链表头部。
    • 如果缓存已经满了，则先删除尾结点，再将数据插入链表头部。

链表Vs数组

数组使用的是连续的内存空间，可以借助CPU缓存机制，预读数组中的数据，访问效率高；链表不是连续存储的，不能够直接访问，必须进行遍历才能找到目标结点，因此访问效率低。

这里的CPU缓存机制指的是什么？？

• CPU在从内存读取数据的时候，会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取那个特定要访问的地址，而是读取一个数据块并保存到CPU缓存中，然后下次访问内存数据的时候就会先从CPU缓存开始查找，如果找到就不需要再从内存中取。这样就实现了比内存访问速度更快的机制。因为数组存储空间是连续的，所以在加载的时候可以把以后的几个下标元素同时加载到CPU缓存，这样执行速度会快于存储空间不连续的链表存储。这就是所谓的“局部性原理”

数组的缺点是大小固定，如果你想要申请的内存过大，可能系统没有那么大的连续内存空间给你，那么就会报错。同时，当你申请的数组不够用了，需要重新申请一个新的更大的数组，此时就需要将原本的数据全部拷贝过去，显然就很浪费时间和效率。

同时，你可能也注意到了，链表每个结点不仅需要保存值，还要有一个指针来指向后继结点，这样链表存储信息的利用率可能就没有数组那么高[因为需要分出一部分内存存储指针]。因此，如果在对内存要求很苛刻的情况下，最好选择数组。

链表操作的注意事项：

• 警惕指针丢失和内存泄露。

  比如在插入结点时候一定要先将待插入结点指针指向被插入结点的下一个结点，然后修改被插入结点next指向待插入结点，防止指针丢失

• 留意特殊情况。

  • 链表为空，程序能否正常工作？

    通常就是特殊判断

  • 链表只包含一个结点或两个结点，程序有没有Bug？

  • 处理头结点和尾结点时，程序能够正常工作？

    通常加入哨兵结点或者if条件判断解决

• 利用画图来辅助自己。

相关代码实现：
包含了单向链表、双向链表、循环链表的C语言实现代码：
link.h

#ifndef LINK_H_
#define LINK_H_
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<math.h>
#include<string.h>

typedef char elemtype;

#define ERROR 0
#define OK    1

//单向链表//
typedef struct Node{
    elemtype data;
    struct Node * next;
}SNode,*SLinklist;
//单链表函数//
bool Init_SLinkList(SLinklist *L);
bool Creat_SLinkList_Tail(SLinklist *L);
bool Creat_SLinkList_Head(SLinklist *L);
SNode *Find_SLinkNode_Pos(SLinklist L,int i);
SNode *Find_SLinkNode_Val(SLinklist L,elemtype key);
int Get_SLink_Len(SLinklist L);
void Print_SLink(SLinklist L);
void Print_Node(SNode *node);
int InsertSLinkList(SLinklist *L,int n,elemtype data);
int Delete_DatainList(SLinklist *L,int n);
//*********//

//双向链表//
typedef struct DNode{
    elemtype data;
    struct DNode * pre;
    struct DNode * next;
}DNode,*DLinklist;
//双向链表函数//
bool Init_DLinklist(DLinklist *L);
bool Creat_DLinklist_Tail(DLinklist *L);
bool Print_DLinkist(DLinklist L);
//********//

//单向循环链表//
typedef struct SCNode{
    elemtype data;
    struct SCNode * next;
}SCNode,*SCLinklist;
//单向循环链表函数//
bool Init_SCLinklist(SCLinklist *L);
bool Creat_SCLinklist_Tail(SCLinklist *L);
bool Print_SCLinkist(SCLinklist L);
//********//
#endif
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

link.c

//单向链表//

//初始化单链表
bool Init_SLinkList(SLinklist *L)
{
    (*L) = (SLinklist)malloc(sizeof(SNode));
    if(!(*L))
    {
        printf("malloc error!");
        return ERROR;
    }
    (*L)->next =NULL;
    return OK;
}
//尾插法建立单链表
bool Creat_SLinkList_Tail(SLinklist *L)
{
    elemtype e;
    SLinklist Node_L,Node_new;
    Node_L = (*L);
    printf("Input data... :");
    scanf("%c",&e);
    while ('#' != e)
    {
        Node_new = (SLinklist)malloc(sizeof(SNode));
        if(!Node_new)
        {
            printf("malloc error!");
            return ERROR;
        }
        Node_new->data = e;
        Node_new->next = Node_L->next;
        Node_L->next = Node_new;
        Node_L = Node_new;
        scanf("%c",&e);
    }
    getchar();
    return OK;
}

//头插发建立单链表
bool Creat_SLinkList_Head(SLinklist *L)
{
    elemtype e;
    SLinklist Node_L,Node_new;
    Node_L = (*L);
    printf("Input data... :");
    scanf("%c",&e);
    while ('#' != e)
    {
        Node_new = (SLinklist)malloc(sizeof(SNode));
        if(!Node_new)
        {
            printf("malloc error!");
            return ERROR;
        }
        Node_new->data = e;
        Node_new->next = Node_L->next;
        Node_L->next = Node_new;
        scanf("%c",&e);
    }
    getchar();
    return OK;
}
//查找单链表中第i个结点,按照位置查找
SNode *Find_SLinkNode_Pos(SLinklist L,int i)
{
    int count=0;
    SLinklist Node_find;
    Node_find = L;
    while(Node_find != NULL)
    {
        Node_find = Node_find->next;
        count ++;
        if(count == i)
        {
            return Node_find;
        }
    }
    printf("What you put n is error!\r\n");
    return NULL;
}

//按照值查找单链表
SNode *Find_SLinkNode_Val(SLinklist L,elemtype key)
{   
    SLinklist Node_find;
    Node_find = L;
    while (Node_find != NULL)
    {
        Node_find = Node_find->next;
        if (Node_find->data == key)
        {
            return Node_find;
        }
    }
    printf("No find what you want node!\r\n");
    return NULL;

}
//计算单链表长度
int Get_SLink_Len(SLinklist L)
{
    int len=0;
    SLinklist Node_L;
    Node_L = L->next;
    while (Node_L != NULL)
    {
        len++;
        Node_L=Node_L->next;

    }
    printf("The Link's len is %d\r\n",len);
    return len;
}

//打印单链表//
void Print_SLink(SLinklist L)
{
    SLinklist Node_L;
    Node_L = L->next;
    while (Node_L)
    {
        printf("%c ",Node_L->data);
        Node_L = Node_L->next;
    }
    printf("\r\n");
}

void Print_Node(SNode *node)
{
    printf("The Node data is %c\r\n",node->data);
}
//向单链表中第n个结点前（第n-1个结点后)插入一个结点//
int InsertSLinkList(SLinklist *L,int n,elemtype data)
{
    int i,j;
    SLinklist node_L,node_new;
    node_L=(*L)->next;   
    //找到第n-1个结点
    
    n=n-2;
    while(n)
    {
        if(node_L == NULL)
        {
            break;
        }
        node_L=node_L->next;
        n--;
    }
    if(n)
    {
        printf("Input 'n' is error!");
        return ERROR;
    }
    node_new=(SLinklist)malloc(sizeof(SNode));
    node_new->next=node_L->next;
    node_L->next=node_new;
    node_new->data=data;

    return OK;
}

//删除单链表中第n个元素//
int Delete_DatainList(SLinklist *L,int n)
{
    int i,j;
    SLinklist node_L,node_delete;
    node_L=(*L)->next;   
    //找到第n-1个结点
    
    n=n-2;
    while(n)
    {
        if(node_L == NULL)
        {
            break;
        }
        node_L=node_L->next;
        n--;
    }
    if(n)
    {
        printf("Input 'n' is error!");
        return ERROR;
    }    
    node_delete=node_L->next;
    node_L->next=node_delete->next;
    free(node_delete);

    return OK;
}


//双向链表//
bool Init_DLinklist(DLinklist *L)
{
    (*L) = (DLinklist)malloc(sizeof(DNode));
    if(!(*L))
    {
        printf("malloc error!\n");
        return ERROR;
    }
    (*L)->next = NULL;
    (*L)->pre = NULL;
    return OK;
}
bool Creat_DLinklist_Tail(DLinklist *L)
{
    elemtype e;
    DLinklist Node_L,Node_new;
    Node_L = (*L);
    printf("Input data... :");
    scanf("%c",&e);
    while ('#' != e)
    {
        Node_new = (DLinklist)malloc(sizeof(SNode));
        if(!Node_new)
        {
            printf("malloc error!");
            return ERROR;
        }
        Node_new->data = e;

        Node_new->next = Node_L->next;
        Node_new->pre = Node_L;
        Node_L->next = Node_new;
        Node_L = Node_new;
        scanf("%c",&e);
    }
    getchar();
    return OK;
}
//打印双向链表
bool Print_DLinkist(DLinklist L)
{
    DLinklist Node_L;
    Node_L = L->next;
    while (Node_L)
    {
        printf("%c ",Node_L->data);
        Node_L = Node_L->next;
    }
    printf("\r\n");
}

//单向循环链表//
bool Init_SCLinklist(SCLinklist *L)
{
    (*L) = (SCLinklist)malloc(sizeof(SCNode));
    if(!(*L))
    {
        printf("malloc error!");
        return ERROR;
    }
    (*L)->next =(*L);
    return OK;
}
//尾插法创建循环链表
bool Creat_SCLinklist_Tail(SCLinklist *L)
{
    elemtype e;
    SCLinklist Node_L,Node_new;
    Node_L = (*L);
    printf("Input data... :");
    scanf("%c",&e);
    while ('#' != e)
    {
        Node_new = (SCLinklist)malloc(sizeof(SCNode));
        if(!Node_new)
        {
            printf("malloc error!");
            return ERROR;
        }
        Node_new->data = e;

        Node_new->next = Node_L->next;
        Node_L->next = Node_new;
        Node_L = Node_new;
        scanf("%c",&e);
    }
    getchar();
    return OK;
}
//打印循环链表
bool Print_SCLinkist(SCLinklist L)
{
    SCLinklist Node_L;
    Node_L = L->next;
    while (Node_L != L)
    {
        printf("%c ",Node_L->data);
        Node_L = Node_L->next;
    }
    printf("\r\n");
}
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