数据结构从入门到精通——链表

---

前言

链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的一个显著特点是，它不需要在内存中连续存储，因此可以高效地插入和删除节点。这种灵活性使得链表在许多应用中成为理想的选择，尤其是在需要动态调整数据结构大小的场景中。

在链表的实现中，通常会有头节点和尾节点之分。头节点是链表的第一个节点，而尾节点是链表的最后一个节点。通过遍历链表，我们可以访问链表中存储的所有数据。链表还支持在链表头部或尾部快速添加新节点，这些操作的时间复杂度通常为O(1)。

然而，链表也有一些缺点。比如，访问链表中的某个特定节点需要从头节点开始遍历，这导致访问链表中间节点的平均时间复杂度为O(n)。此外，链表需要额外的空间来存储指针，这增加了内存的使用。

链表有多种类型，如单向链表、双向链表和循环链表等。单向链表是最简单的链表类型，每个节点只有一个指向下一个节点的指针。双向链表则允许节点同时指向前一个和下一个节点，这使得双向链表在某些操作上比单向链表更高效。循环链表则是将尾节点的指针指向头节点，形成一个闭环。

在实际应用中，链表常用于实现栈、队列和哈希表等数据结构。例如，链表可以作为栈的底层数据结构，实现元素的先进后出。此外，链表还可以用于实现动态数组，支持元素的动态插入和删除。

总之，链表作为一种重要的数据结构，在编程和数据处理中发挥着重要作用。尽管链表在某些方面存在不足，但其灵活性和高效性使得它在许多场景中仍然是理想的选择。通过深入了解链表的特性和应用，我们可以更好地利用这种数据结构来解决实际问题。

---

一、链表

1.1 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。


现实中 数据结构中

1.2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向或者双向
   
2. 带头或者不带头
   
3. 循环或者非循环
   

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

1.3 链表的实现

// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
 SLTDateType data;
 struct SListNode* next;
}SListNode;
// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);
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

1.4 链表面试题

1. 删除链表中等于给定值 val 的所有结点
2. 反转一个单链表
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则
   返回第二个中间结点
4. 输入一个链表，输出该链表中倒数第k个结点
5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有
   结点组成的
6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结
   点之前
7. 链表的回文结构
8. 输入两个链表，找出它们的第一个公共结点
   
9. 给定一个链表，判断链表中是否有环
   【思路】
   快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。

【扩展问题】

• 为什么快指针每次走两步，慢指针走一步可以？
  假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。
  此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

• 快指针一次走3步，走4步，…n步行吗？
  

10. 给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL

解决像这样的题目，我们可以找等式，通过等式来找出相应的关系

• 结论
  让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
• 证明
  

11. 给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点或空结点。
    要求返回这个链表的深度拷贝
12. 其他 。ps：链表的题当前因为难度及知识面等等原因还不适合我们当前学习，大家可以先把c++学一下，在逐步开始刷题 Leetcode + 牛客

1.5 双向链表的实现

// 2、带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
 LTDataType _data;
 struct ListNode* next;
 struct ListNode* prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void ListErase(ListNode* pos);
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

二、顺序表和链表的区别

备注：缓存利用率参考存储体系结构 以及 局部原理性。

与程序员相关的CPU缓存知识

三、单项链表实现具体代码

text.h

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

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode,*Node;

void SLTPrint(Node phead);
Node SLTBuyNode(SLTDataType x);//开辟空间
//链表的头插、尾插
void SLTPushBack(Node* pphead, SLTDataType x);
void SLTPushFront(Node* pphead, SLTDataType x);

//链表的头删、尾删
void SLTPopBack(Node* pphead);//尾删
void SLTPopFront(Node* pphead);//头删

//查找
Node SLTFind(Node* pphead, SLTDataType x);

//在指定位置之前插入数据
void SLTInsert(Node*  pphead, Node pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(Node pos, SLTDataType x);

//删除pos节点
void SLTErase(Node* pphead, Node pos);
//删除pos之后的节点
void SLTEraseAfter(Node pos);

//销毁链表
void SListDesTroy(Node* 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
38

text.c

#include "text.h"
void SLTPrint(Node phead)
{
	assert(phead);
	Node purt = phead;
	while (purt)
	{
		printf("%d->", purt->data);
		purt = purt->next;
	}
	printf("NULL\n");
}
Node SLTBuyNode(SLTDataType x)
{
	Node str = (Node)malloc(sizeof(SLTNode));
	assert(str);
	str->data = x;
	str->next = NULL;
	return str;
}
void SLTPushBack(Node* pphead, SLTDataType x)
{
	assert(pphead);
	Node newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		Node ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}
void SLTPushFront(Node* pphead, SLTDataType x)
{
	assert(pphead);
	Node newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopBack(Node* pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	Node ptail = *pphead;
	while (ptail->next->next)
	{
		ptail = ptail->next;
	}
	free(ptail->next);
	ptail->next= NULL;
}
void SLTPopFront(Node* pphead)
{
	assert(pphead);
	assert(*pphead);
	Node next = (*pphead)->next;
	free(*pphead);
	(*pphead) = next;
}
Node SLTFind(Node* pphead, SLTDataType x)
{
	assert(pphead);
	assert(*pphead);
	Node next = *pphead;
	while (next)
	{
		if (next->data == x)
		{
			printf("找到了\n");
			return next;
		}
		next = next->next;
	}
	return NULL;
}
void SLTInsert(Node* pphead, Node pos, SLTDataType x) {
	assert(pphead);
	assert(pos);
	//要加上链表不能为空
	assert(*pphead);

	Node newnode = SLTBuyNode(x);
	//pos刚好是头结点
	if (pos == *pphead) {
		//头插
		SLTPushFront(pphead, x);
		return;
	}

	//pos不是头结点的情况
	Node prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev -> newnode -> pos
	prev->next = newnode;
	newnode->next = pos;
}
void SLTInsertAfter(Node pos, SLTDataType x)
{
	assert(pos);
	Node newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SLTErase(Node* pphead, Node pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	Node node = *pphead;
	if (pos == *pphead)
	{
		SLTPopFront(&pos);
	}
	while (node->next != pos)
	{
		node = node->next;
	}
	node->next = pos->next;
	free(pos);
	pos = NULL;
}
void SLTEraseAfter(Node pos)
{
	assert(pos);
	assert(pos->next);
	Node next = pos->next,pre;
	while (next)
	{
		pre = next->next;
		free(next);
		next = pre;
	}
	pos->next = NULL;
}
void SListDesTroy(Node* pphead) {
	assert(pphead);
	assert(*pphead);
	Node pcur = *pphead;
	while (pcur)
	{
		Node next = pcur->next;
		free(pcur);
		pcur = 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

main.c

#include"text.h"

void SlistTest01() {
	//一般不会这样去创建链表，这里只是为了给大家展示链表的打印
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;

	SLTNode* plist = node1;
	SLTPrint(plist);
}
void SlistTest02() {
	Node plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist); //1->2->3->4->NULL

	SLTPushFront(&plist, 5);
	SLTPrint(plist);          //5->1->2->3->4->NULL
	SLTPushFront(&plist, 6);
	SLTPrint(plist);         //6->5->1->2->3->4->NULL
	SLTPushFront(&plist, 7);
	SLTPrint(plist);         //7-6->5->1->2->3->4->NULL

	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
}

void SlistTest03() {
	Node plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist); //1->2->3->4->NULL

	/*SListDesTroy(&plist);*/
	//头删
	SLTPopFront(&plist);
	SLTPrint(plist);    //2->3->4->NULL
	SLTPopFront(&plist);
	SLTPrint(plist);    //3->4->NULL
	SLTPopFront(&plist);
	SLTPrint(plist);    //4->NULL
	//SLTPopFront(&plist);
	//SLTPrint(plist);    //NULL
	SLTPopFront(&plist);
	SLTPrint(plist);    //assert
	
	SLTNode* FindRet = SLTFind(&plist, 3);
	if (FindRet) {
		printf("找到了！\n");
	}
	else {
		printf("未找到！\n");
	}
	//SLTInsert(&plist, FindRet, 100);
	//SLTInsertAfter(FindRet, 100);
	//
	删除指定位置的节点
	//SLTErase(&plist, FindRet);
	//SLTPrint(plist); //1->2->3->NULL
}
int main() {
	//SlistTest01();
	/*SlistTest02();*/
	SlistTest03();
	return 0;
}
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

单链表的打印

void SLTPrint(Node phead)
1

void SLTPrint(Node phead)
{
	assert(phead);
	Node purt = phead;
	while (purt)
	{
		printf("%d->", purt->data);
		purt = purt->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11

单链表的打印是链表操作中的一个基础且重要的环节。链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。而单链表则是链表的一种，它的特点是每个节点只包含一个指向下一个节点的指针。

在打印单链表时，我们通常需要遍历整个链表，依次访问每个节点，并输出节点的数据部分。这个过程可以通过设置一个指针，初始时指向链表的头节点，然后不断将指针移动到下一个节点，直到指针为空，即遍历完整个链表。

为了实现单链表的打印，我们可以定义一个函数，该函数接受链表的头节点作为参数。在函数内部，我们使用一个循环来遍历链表。在每次循环中，我们输出当前节点的数据部分，并将指针移动到下一个节点。当指针为空时，循环结束，打印操作完成。

空间的开辟

Node SLTBuyNode(SLTDataType x);//开辟空间
1

Node SLTBuyNode(SLTDataType x)
{
	Node str = (Node)malloc(sizeof(SLTNode));
	assert(str);
	str->data = x;
	str->next = NULL;
	return str;
}
1
2
3
4
5
6
7
8

链表的头插、尾插

//链表的头插、尾插
void SLTPushBack(Node* pphead, SLTDataType x);
void SLTPushFront(Node* pphead, SLTDataType x);
1
2
3

void SLTPushBack(Node* pphead, SLTDataType x)
{
	assert(pphead);
	Node newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		Node ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}
void SLTPushFront(Node* pphead, SLTDataType x)
{
	assert(pphead);
	Node newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
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

链表的头插、尾插是链表操作中常见的两种插入方式，它们在处理链表数据结构时各有特点，也适用于不同的应用场景。

头插法，顾名思义，是在链表的头部插入新的节点。这种操作的时间复杂度通常为O(1)，因为无论链表长度如何，只需要修改头指针和新节点的指针即可。头插法的优点是插入速度快，但缺点是在某些情况下可能导致链表变得不均衡，特别是在大量连续的头插操作中，链表可能会退化成类似栈的结构，影响后续操作的效率。

尾插法则是在链表的尾部插入新的节点。这种操作的时间复杂度通常为O(n)，因为需要遍历链表找到尾节点。尾插法的优点是能保持链表的相对均衡，减少链表操作中的性能瓶颈。然而，它的缺点是在大量连续的尾插操作中，需要不断遍历链表，相对头插法来说效率较低。

在实际应用中，选择头插还是尾插，需要根据具体的需求和场景来决定。例如，在实现一个基于链表的栈时，头插法是一个很好的选择，因为栈的特性就是后进先出（LIFO），头插法能很好地满足这一需求。而在实现一个基于链表的队列时，尾插法则更为合适，因为队列的特性是先进先出（FIFO），尾插法能保持链表的顺序性，使得出队操作更加高效。

此外，在实际编程中，还需要注意链表操作的边界条件和特殊情况，如空链表的处理、内存分配失败的处理等。

链表的头删、尾删

//链表的头删、尾删
void SLTPopBack(Node* pphead);//尾删
void SLTPopFront(Node* pphead);//头删
1
2
3

void SLTPopBack(Node* pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	Node ptail = *pphead;
	while (ptail->next->next)
	{
		ptail = ptail->next;
	}
	free(ptail->next);
	ptail->next= NULL;
}
void SLTPopFront(Node* pphead)
{
	assert(pphead);
	assert(*pphead);
	Node next = (*pphead)->next;
	free(*pphead);
	(*pphead) = next;
}
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

链表的头删、尾删是链表操作中的基础内容，对于理解链表结构和实现链表功能至关重要。在链表中，头删指的是删除链表中的第一个元素，而尾删则是删除链表中的最后一个元素。这个过程中，需要注意更新头节点的指针，并确保原头节点在删除后能够被正确释放，以避免内存泄漏。

相比之下，尾删操作稍微复杂一些。因为需要找到链表的最后一个节点，并将其前一个节点的指针设置为null。同样，在删除尾节点之前，也需要判断链表是否为空。如果链表只有一个节点，那么头删和尾删是等价的。如果链表有多个节点，则需要遍历链表，找到最后一个节点，并执行删除操作。

除了基本的头删和尾删操作，链表还支持在中间位置插入和删除节点。这些操作同样需要对链表结构有深入的理解，并且能够正确处理各种边界情况。在实际应用中，链表的操作通常与其他数据结构或算法相结合，以实现更复杂的功能。通过熟练掌握链表操作，可以更好地理解和应用链表这一基础数据结构。

链表中元素的查找

//查找
Node SLTFind(Node* pphead, SLTDataType x);
1
2

Node SLTFind(Node* pphead, SLTDataType x)
{
	assert(pphead);
	assert(*pphead);
	Node next = *pphead;
	while (next)
	{
		if (next->data == x)
		{
			printf("找到了\n");
			return next;
		}
		next = next->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

链表中元素的查找是数据结构和算法中的一个基础问题。在链表中查找元素，不同于在数组中的直接索引访问，它通常需要从链表的头部或尾部开始，逐个节点地遍历，直到找到目标元素或者遍历完整个链表。这种查找方式的时间复杂度通常是O(n)，其中n是链表的长度。

链表的查找性能可以通过一些优化手段来提升。例如，如果链表是有序的，那么可以使用二分查找等更高效的算法来减少查找时间。然而，这种优化通常要求链表在插入和删除元素时保持有序状态，这会增加这些操作的复杂度。

在实现链表查找时，我们通常会使用一个循环来遍历链表。在每次迭代中，我们将当前节点的值与目标值进行比较。如果找到匹配的值，则返回当前节点的位置或引用；如果遍历完整个链表都没有找到匹配的值，则返回null或表示未找到的特殊值。

链表在指定位置之前、之后插入数据

//在指定位置之前插入数据
void SLTInsert(Node*  pphead, Node pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(Node pos, SLTDataType x);
1
2
3
4

void SLTInsert(Node* pphead, Node pos, SLTDataType x) {
	assert(pphead);
	assert(pos);
	//要加上链表不能为空
	assert(*pphead);

	Node newnode = SLTBuyNode(x);
	//pos刚好是头结点
	if (pos == *pphead) {
		//头插
		SLTPushFront(pphead, x);
		return;
	}

	//pos不是头结点的情况
	Node prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev -> newnode -> pos
	prev->next = newnode;
	newnode->next = pos;
}
void SLTInsertAfter(Node pos, SLTDataType x)
{
	assert(pos);
	Node newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
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

链表在指定位置之前、之后插入数据是链表操作中的基本功能。链表作为一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。这种结构允许我们在不移动其他元素的情况下插入或删除元素，因此在许多场景中都非常有用。

首先，我们要明确链表的基本结构。通常，链表节点包含一个数据域和一个指针域。数据域用于存储实际的数据，而指针域则用于指向链表中的下一个节点。对于头节点，其指针域指向链表的第一个节点；对于尾节点，其指针域通常指向空（NULL），表示链表的结束。

在链表中插入数据之前，我们需要确定插入的位置。这可以通过使用索引或遍历链表直到找到适当的节点来实现。一旦找到插入位置，我们就可以创建一个新的节点，并将其插入到链表中。

要在指定位置之后插入数据，我们需要找到该位置的前一个节点。然后，我们将新节点的指针域设置为当前节点的指针域所指向的节点，同时将当前节点的指针域设置为新节点。这样，新节点就被插入到了指定位置之后。

要在指定位置之前插入数据，我们需要找到该位置的节点。然后，我们将新节点的指针域设置为当前节点，并将当前节点的前一个节点的指针域设置为新节点。这样，新节点就被插入到了指定位置之前。

需要注意的是，在插入节点时，我们必须确保正确地更新指针域，以保持链表的完整性和正确性。此外，我们还需要考虑链表的边界情况，例如在链表头部或尾部插入节点时。

在插入数据后，链表的结构可能会发生变化，因此任何依赖于链表结构的操作都可能需要重新评估或调整。此外，插入操作可能会增加链表的长度，这可能会影响链表的性能，特别是在进行搜索或遍历操作时。

总的来说，链表在指定位置之前或之后插入数据是链表操作中的基本操作之一。通过正确地实现这些操作，我们可以充分利用链表的优势，高效地管理和操作数据。

删除链表中的结点

//删除pos节点
void SLTErase(Node* pphead, Node pos);
//删除pos之后的节点
void SLTEraseAfter(Node pos);
1
2
3
4

void SLTErase(Node* pphead, Node pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	Node node = *pphead;
	if (pos == *pphead)
	{
		SLTPopFront(&pos);
	}
	while (node->next != pos)
	{
		node = node->next;
	}
	node->next = pos->next;
	free(pos);
	pos = NULL;
}
void SLTEraseAfter(Node pos)
{
	assert(pos);
	assert(pos->next);
	Node next = pos->next,pre;
	while (next)
	{
		pre = next->next;
		free(next);
		next = pre;
	}
	pos->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
25
26
27
28
29
30
31

删除链表中的结点是一项常见的编程任务，它要求我们在保持链表其他部分完整的同时，移除指定的结点。链表是一种常见的数据结构，它由一系列节点组成，每个节点都包含数据部分和指向下一个节点的指针。为了有效地删除链表中的某个节点，我们需要遵循一定的步骤，并确保不会破坏链表的完整性。

首先，我们需要确定要删除的节点。这通常是通过节点的值或者节点在链表中的位置来实现的。在知道要删除的节点之后，我们需要考虑几种不同的删除情况：

如果要删除的节点是链表的第一个节点，我们需要更新链表的头指针，使其指向第二个节点。

如果要删除的节点是链表的最后一个节点，我们需要找到倒数第二个节点，并将其指针部分设置为null，从而切断与最后一个节点的连接。

如果要删除的节点位于链表的中间，我们需要找到该节点的前一个节点，并将其指针部分更新为指向要删除节点的下一个节点，从而跳过要删除的节点。

在删除节点的过程中，我们必须确保正确地处理内存，以防止内存泄漏。这通常意味着在删除节点后，我们需要释放该节点所占用的内存。

销毁链表

//销毁链表
void SListDesTroy(Node* pphead);
1
2

void SListDesTroy(Node* pphead) {
	assert(pphead);
	assert(*pphead);
	Node pcur = *pphead;
	while (pcur)
	{
		Node next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

链表，这种数据结构在计算机科学中占据着举足轻重的地位，其通过节点之间的链接来存储数据，每个节点都包含数据和指向下一个节点的指针。然而，当链表不再需要时，如何正确地销毁它，释放其占用的内存，就显得尤为重要。

销毁链表的过程通常包括两个主要步骤：遍历链表和释放内存。首先，我们需要从链表的头节点开始，逐个访问链表中的每个节点。在访问每个节点时，我们需要记录下一个节点的位置，以便在释放当前节点后能够继续遍历链表。同时，我们还需要注意处理链表的尾节点，确保不会出现内存泄漏。

在遍历链表的过程中，我们可以通过修改指针的指向来逐个断开节点之间的链接。具体来说，我们可以将当前节点的下一个节点的指针置为null，这样当前节点就不再指向下一个节点，从而实现了断开链接的目的。然后，我们可以释放当前节点所占用的内存，通常可以使用操作系统提供的内存释放函数来完成这一操作。

在释放内存时，我们需要格外小心。一方面，我们需要确保只释放链表节点所占用的内存，而不要误释放其他重要数据的内存。另一方面，我们还需要注意处理可能出现的异常情况，例如内存释放失败等。为了避免这些问题，我们可以使用智能指针等高级内存管理技术来辅助销毁链表。

总的来说，销毁链表是一个复杂而重要的任务。我们需要仔细遍历链表中的每个节点，逐个断开链接并释放内存，以确保链表能够被正确地销毁。同时，我们还需要注意处理可能出现的异常情况，保证程序的稳定性和可靠性。只有这样，我们才能在享受链表带来的便利的同时，避免其带来的潜在风险。

四、双向循环链表代码的具体实现

text.h

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

//定义双向链表中节点的结构
typedef int LTDataType;
typedef struct ListNode {
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode,* Node;

//注意，双向链表是带有哨兵位的，插入数据之前链表中必须要先初始化一个哨兵位
//void LTInit(Node* pphead);
Node LTInit();
Node LTBuyNode(LTDataType x);
//void LTDesTroy(Node* pphead);
void LTDesTroy(Node phead);   //推荐一级（保持接口一致性）

void LTPrint(Node phead);

//不需要改变哨兵位，则不需要传二级指针
//如果需要修改哨兵位的话，则传二级指针
void LTPushBack(Node phead, LTDataType x);
void LTPushFront(Node phead, LTDataType x);

//头删、尾删
void LTPopBack(Node phead);
void LTPopFront(Node phead);

//查找
Node LTFind(Node phead, LTDataType x);

//在pos位置之后插入数据
void LTInsert(Node pos, LTDataType x);
//删除pos位置的数据
void LTErase(Node pos);
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

text.c

#include "text.h"
Node LTBuyNode(LTDataType x)
{
	Node phead = (Node)malloc(sizeof(LTNode));
	assert(phead);
	phead->data = x;
	phead->prev = phead;
	phead->next = phead;
	return phead;
}
Node LTInit()
{
	Node phead = LTBuyNode(-1);
	return phead;
}
void LTDesTroy(Node phead)
{
	assert(phead);
	/*Node ret;
	while (phead->next != phead)
	{
		ret = phead->next;
		phead->next = ret->next;
		phead->next->prev = phead;
		free(ret);
	}
	free(phead);
	phead = NULL;*/
	Node pur = phead->next;
	while (pur != phead)
	{
		Node next = pur->next;
		free(pur);
		pur = next;
	}
	free(phead);
	phead = NULL;
}
void LTPrint(Node phead)
{
	assert(phead);
	Node pur = phead->next;
	while (pur!= phead)
	{
		printf("%d->", pur->data);
		pur = pur->next;
	}
	printf("NULL\n");
}
void LTPushBack(Node phead, LTDataType x)
{
	assert(phead);
	Node newnode = LTBuyNode(x);
	phead->prev->next = newnode;
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev = newnode;
}
void LTPushFront(Node phead, LTDataType x)
{
	assert(phead);
	Node newnode = LTBuyNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	newnode->prev = phead;
	phead->next = newnode;
}
void LTPopBack(Node phead)
{
	assert(phead);
	assert(phead->next != phead);
	Node pur = phead->prev;
	pur->prev->next = phead;
	phead->prev = pur->prev;
	free(pur);
	pur = NULL;
}
void LTPopFront(Node phead)
{
	assert(phead);
	assert(phead->next != phead);
	Node pur = phead->next;
	phead->next = pur->next;
	pur->next->prev = phead;
	free(pur);
	pur = NULL;
}

Node LTFind(Node phead, LTDataType x)
{
	assert(phead);
	Node pur = phead->next;
	while (pur != phead)
	{
		if (pur->data == x)return pur;
		pur = pur->next;
	}
	return NULL;
}
void LTInsert(Node pos, LTDataType x) {
	assert(pos);
	Node newnode = LTBuyNode(x);
	//pos newnode pos->next
	newnode->next = pos->next;
	newnode->prev = pos;

	pos->next->prev = newnode;
	pos->next = newnode;
}
//删除pos位置的数据
void LTErase(Node pos) {
	assert(pos);

	//pos->prev pos  pos->next
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	free(pos);
	pos = 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

main.c

#include "text.h"
void ListTest01() {
	//LTNode* plist = NULL;
	//LTInit(&plist);

	Node plist = LTInit();
	//尾插
	/*LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);*/
	//头插
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);       //4->3->2->1->

	//
	/*LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);*/
	//LTPrint(plist);
	//
	//头删
	/*LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);*/
	//LTPrint(plist);

	Node findRet = LTFind(plist, 3);
	if (findRet == NULL) {
		printf("未找到！\n");
	}
	else {
		printf("找到了！\n");
	}
	在指定位置之后插入数据
	LTInsert(findRet, 66); //4->3->2->1->66->
	LTPrint(plist);

	//删除pos位置的节点
	LTErase(findRet);
	LTPrint(plist);
	LTDesTroy(plist);
	plist = NULL;
}

int main() {
	ListTest01();
	return 0;
}
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

双向循环链表的创建

Node LTBuyNode(LTDataType x);
1

Node LTBuyNode(LTDataType x)
{
	Node phead = (Node)malloc(sizeof(LTNode));
	assert(phead);
	phead->data = x;
	phead->prev = phead;
	phead->next = phead;
	return phead;
}
1
2
3
4
5
6
7
8
9

双向循环链表的初始化

Node LTInit();
1

Node LTInit()
{
	Node phead = LTBuyNode(-1);
	return phead;
}
1
2
3
4
5

在开始编写双向循环链表的初始化代码之前，我们首先需要理解双向循环链表的基本结构。双向循环链表是一种线性数据结构，它包含了一个指向前一个节点的“前指针”和一个指向下一个节点的“后指针”。与传统的双向链表不同，双向循环链表的最后一个节点的后指针指向第一个节点，而第一个节点的前指针则指向最后一个节点，从而形成一个闭环。

双向循环链表的销毁

void LTDesTroy(Node phead);   //推荐一级（保持接口一致性）
1

void LTDesTroy(Node phead)
{
	assert(phead);
	/*Node ret;
	while (phead->next != phead)
	{
		ret = phead->next;
		phead->next = ret->next;
		phead->next->prev = phead;
		free(ret);
	}
	free(phead);
	phead = NULL;*/
	Node pur = phead->next;
	while (pur != phead)
	{
		Node next = pur->next;
		free(pur);
		pur = next;
	}
	free(phead);
	phead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

接口一致性
可以这样理解，就想象你现在是用户，你是想在使用这个软件的时候操作简单还是操作困难，按照正常人来说，肯定是越简单越好，这时候就需要接口一致了，我们作为这个软件的设计者，我们需要把这个软件做的越简单越好

在数据结构和算法的世界里，双向循环链表是一种独特而高效的数据结构。它允许我们在任意节点向前或向后移动，从而方便地访问链表中的任何元素。然而，就像所有资源一样，当我们不再需要双向循环链表时，必须妥善地销毁它，以防止内存泄漏和其他潜在问题。

销毁双向循环链表的过程涉及几个关键步骤。首先，我们必须遍历链表，释放每个节点所占用的内存。由于双向循环链表的特性，我们可以从任何一个节点开始遍历。为了简化操作，我们通常选择头节点作为起点。

在遍历过程中，我们需要逐个访问链表中的每个节点，并释放其内存。这通常通过调用适当的内存释放函数来完成，例如在C++中使用delete操作符，或在C语言中使用free函数。在释放节点内存之前，我们还需确保已经断开了该节点与前一个节点和后一个节点的连接，以防止出现悬挂指针。

一旦所有节点的内存都被释放，我们就需要检查链表的头指针是否已经被正确设置为null或nullptr。这是为了确保链表已经被完全销毁，并且任何尝试访问它的操作都会失败。

值得注意的是，双向循环链表的销毁过程必须小心谨慎，以确保没有遗漏任何节点。否则，未被释放的内存可能会导致内存泄漏，进而影响程序的性能和稳定性。

综上所述，双向循环链表的销毁是一个重要而必要的操作。通过正确地释放每个节点的内存，并断开它们之间的连接，我们可以确保链表被完全销毁，从而避免潜在的内存泄漏和其他问题。这种负责任的资源管理实践是编写高效、可靠的代码的重要组成部分。

双向循环链表的打印

void LTPrint(Node phead);
1

void LTPrint(Node phead)
{
	assert(phead);
	Node pur = phead->next;
	while (pur!= phead)
	{
		printf("%d->", pur->data);
		pur = pur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11

双向循环链表的头插和尾插

//不需要改变哨兵位，则不需要传二级指针
//如果需要修改哨兵位的话，则传二级指针
void LTPushBack(Node phead, LTDataType x);
void LTPushFront(Node phead, LTDataType x);
1
2
3
4

void LTPushBack(Node phead, LTDataType x)
{
	assert(phead);
	Node newnode = LTBuyNode(x);
	phead->prev->next = newnode;
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev = newnode;
}
void LTPushFront(Node phead, LTDataType x)
{
	assert(phead);
	Node newnode = LTBuyNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	newnode->prev = phead;
	phead->next = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

双向循环链表的头删和尾删

//头删、尾删
void LTPopBack(Node phead);
void LTPopFront(Node phead);
1
2
3

void LTPopBack(Node phead)
{
	assert(phead);
	assert(phead->next != phead);
	Node pur = phead->prev;
	pur->prev->next = phead;
	phead->prev = pur->prev;
	free(pur);
	pur = NULL;
}
void LTPopFront(Node phead)
{
	assert(phead);
	assert(phead->next != phead);
	Node pur = phead->next;
	phead->next = pur->next;
	pur->next->prev = phead;
	free(pur);
	pur = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

双向循环链表的元素查找

//查找
Node LTFind(Node phead, LTDataType x);
1
2

Node LTFind(Node phead, LTDataType x)
{
	assert(phead);
	Node pur = phead->next;
	while (pur != phead)
	{
		if (pur->data == x)return pur;
		pur = pur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11

双向循环链表的插入和删除

//在pos位置之后插入数据
void LTInsert(Node pos, LTDataType x);
//删除pos位置的数据
void LTErase(Node pos);
1
2
3
4

void LTInsert(Node pos, LTDataType x) {
	assert(pos);
	Node newnode = LTBuyNode(x);
	//pos newnode pos->next
	newnode->next = pos->next;
	newnode->prev = pos;

	pos->next->prev = newnode;
	pos->next = newnode;
}
//删除pos位置的数据
void LTErase(Node pos) {
	assert(pos);

	//pos->prev pos  pos->next
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

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

---