好了,学完了顺序表,我们再来看一下链表

线性表链式存储结构的特点是:

用一组任意的存储单元存储线性表的数据元素 (这组存储单元可以是连续的，也可以是不连续的)

说人话就是 链表是一种不要求内存连续、通过“指针/引用”把元素串起来的数据结构。

为了表示每个数据元素a(i)与其直接后续数据元素a(i+1)之间的逻辑关系, 对数据元素a(i)来说除了其本身的信息之外，还需要存储一个指示，其直接后继的信息 (直接后继的存储位置),这两部分信息组成数据元素a(i)的存储映像，称为节点(node)

节点包括两个域:

  • 其中存储数据元素的信息称为数据域 即 data
  • 存储直接后继存储位置有域称为指针域 即 next

指针域中存储的信息称为 指针或链

n个节点[a(i) i范围为(1<=i<=n)的存储映像]链接成一个链表即为线性表(a1,a2…an)

相信你可能没有看懂我说的这些东西是啥玩意

这里是一个C语言的代码示例

1
2
3
4
5
6
//链表存储结构
typedef int ElemType;
typedef struct node{
		ElemType data;
		struct node *next;
}Node;

我们可以把这个用一个图抽象出来

​ image-20260106192044936

其实我个人觉得用铁链这样的结构来描述并不是很准确,我反而觉得像火车这样的模型更加生动形象,火车头是头结点,每节车厢都是一个节点,车厢有自己的编号而且里面的乘客就是数据

​ 卡通手绘火车

我们先来看看单链表吧

单链表

​ image-20260106192446584

这里你也可以看出,单链表的结构非常简单,就像小火车一样,这里从图中你可以发现单链表的几个性质

单链表是最基础、最常见的一种链表

定义

单链表每个节点只有一个指针，只指向「下一个节点」

1
head → [A|•] → [B|•] → [C|null]
  • head：头节点（链表的入口）
  • 最后一个节点指向 null

如果你没看懂的话这里我详细解释一下

​ image-20260106195217062

链由节点构成,data存储数据 next用于连接下一个节点,next为node类型的指针,存储下一个节点的地址

类似于一个半班有40个同学,每个同学的手上都有一张纸,上面写着另一个同学的学号,而同学本身就是一个地址数据,这样这个同学可以用自己的手上的学号找到另一个同学,形成一个链

​ image-20260107103534965

​ 同样的是单链表也是这样的

单链表的初始化

大家是否还记得在上一篇的顺序表当中我们使用动态分配内存来进行顺序表的初始化,这里我们也可以使用malloc动态分配内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;

typedef struct node{
		ElemType data;
		struct node *next;
}Node;

Node*initList(){
	Node*head=(Node*)malloc(sizeof(Node));
	head->data=0;
	head->next=NULL;
	return head;
}

int main(){
	//将list初始化为一个头节点
	Node*list=initList();
	return 1;
}

​ image-20260106194539055

其实本质上就是把第一个点设置为头节点,然后将节点里的data数据归零,并且将节点的下一个节点设置为 null

首先用malloc在堆内存中构建了一个节点大小的空间,作为链表头结点 head 即 initlist 函数返回Node类型的指针head

默认给data数据域为0 令next地址为空

​ image-20260107111435772

单链表的头插法

注意:头插法的顺序和排列的顺序是相反的

刚开始只有一个头节点,如果要插入一个数据就往头节点后面去插 ,把头节点next指向第二个节点的那个地址,如果再要插入一个数据,则仍在头节点之后插入

注意,顺序不能错,错了链表就断了

1
2
3
4
5
6
7
8
9
10
11
12
13
//头插法
int insertHead(Node*L,ElemType e){
	Node*p=(Node*)malloc(sizeof(Node));
	p->data=e;
	p->next=L->next;
	L->next=p;
  return 1;
}
int main(){
	Node *list=initList();
	insertHead(list,10);
	insertHead(list,20);
}

​ 单链表-头插法-01

​ 单链表-头插法-02

​ 单链表-头插法-03

这里我们画一个图直观表述一下

​ image-20260107111909640

第一步:先在内存空间中创建一个节点,然后把传入的e参数赋值给节点中data的数据,即p->data=e;

让头结点参数L指向的下一个节点的地址赋值给新创建的节点指向的下一个节点的地址 即 p->next=L->next;

​ image-20260107112001392

第二步: 然后将p的地址赋值为当前头结点指向的下一个地址 即 L->next=p;

​ image-20260107112758717

​ image-20260107112831150

这个我们可以用更加直观的可视化图看一下

​ image-20260107113505921

说人话就是先创建一个空节点,塞进去一个数据,再把这个节点和之前和头结点相连的那个节点连起来,再让头结点连接这个节点,这样可以确保链不会断掉

单链表的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//遍历
void listNode(Node*L){
	Node*p=L->next;
	while(p!=NULL){
		printf("%d\n",p->data);
		p=p->next;
	}
	printf("\n");
}

int main(){
	Node *list=initList();
	insertHead(list,10);
	insertHead(list,20);
	insertHead(list,30);
	
	listNode(list);
	return 0;
}

​ image-20260107114631726

遍历的原理也十分浅显易懂:

打印头结点的下一个节点的数据,打印完了再换下一个,一直到遇到尾节点全部打印完成为止

单链表的尾插法

其实相比于头插法这种倒序插入,我更喜欢尾插法这种正序插入的方式

尾插法就是先获取尾节点的地址,然后再去进行尾插法

即先传进来L链表,链表进来之后赋值给一个p指针 , 如果p的next不为空我们就持续循环p等于p的next , 相当于一个链一个链的去找,找到最后一个链的时候跳出循环 , 跳出循环的时候 p就是链表的尾节点

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
//尾插法
//先获取尾节点
Node*get_tail(Node*L){
	Node *p=L;
	while(p->next!=NULL){
		p=p->next;
	}
	return p;
}
//再实现尾插
Node*insertTail(Node *tail,ElemType e){
	Node *p=(Node*)malloc(sizeof(Node));
	p->data=e;
	tail->next=p;
	//让p的下一个节点变成NULL,并返回尾节点的地址
	p->next=NULL;
	return p;
}

int main(){
	Node *list=initList();
	//得到当前尾节点
	Node *tail=get_tail(list);
	//每次在尾节点位置插入数据后更新尾节点的位置
	tail=insertTail(tail,10);
	tail=insertTail(tail,20);
	tail=insertTail(tail,30);
	
	listNode(list);
	return 0;
}

​ 单链表-尾插法-01

​ 单链表-尾插法-02

​ 单链表-尾插法-03

这里我们可以详细描述一下

第一步:先获取尾节点的地址,思路和遍历差不多

​ image-20260107115906521

第二步:这个和头插法基本上差不过,只是多一个步骤那就是将插入的节点变成尾节点

​ image-20260107122507227

这里可以用一个图来直观描述

​ image-20260107122745285

单链表在指定位置插入数据

前面说的头插法和尾插法只是在表头或者表尾插入节点,而这里是在任意位置插入

原理:

将原来的链拆除,生成一个新的节点,让新的节点指向插入之前的位置 , 即先获取要插入的节点的位置, 然后让新节点指向要插入的节点所指向的位置,再让被插入的节点指向新节点

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
//在指定位置插入数据
int insertNode(Node*L,int pos,ElemType e){
	//用来保存插入位置的前驱节点
	Node *p=L;
	int i=0;
	//遍历链表找到插入位置的前驱节点
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL){
			return 0;
		}
	}
	//要插入的新节点
	Node *q=(Node *)malloc(sizeof(Node));
	q->data=e;
	q->next=p->next;
	p->next=q;
	return 1;
	
}

int main(){
	Node *list=initList();
	//得到当前尾节点
	Node *tail=get_tail(list);
	//每次在尾节点位置插入数据后更新尾节点的位置
	tail=insertTail(tail,10);
	tail=insertTail(tail,20);
	tail=insertTail(tail,30);
	//插入前
	listNode(list);
	//插入节点
	insertNode(list,2,15);
	//插入后
	listNode(list);
	return 0;
}

​ image-20260107140622958

​ 单链表-在指定位置插入数据

单链表的删除

原理: 先找到要删除节点的前置节点,用指针记录要删除的节点,通过修改前置节点的后继结点实现删除,释放删除节点的内存空间

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
//删除节点
int deleteNode(Node *L,int pos){
	//要删除节点的前驱
	Node*p=L;
	int i=0;
	//遍历链表找到要删除节点的前驱
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL){
			return 0;
		}
	}
	if(p->next==NULL){
		printf("要删除的位置错误\n");
		return 0;
	}
	//q指向要删除的节点
	Node *q=p->next;
	//让要删除节点的前驱指向要删除节点的后继
	p->next=q->next;
	//释放要删除节点的内存空间
	free(q);
	return 1;
}

int main(){
	Node *list=initList();
	//得到当前尾节点
	Node *tail=get_tail(list);
	//每次在尾节点位置插入数据后更新尾节点的位置
	tail=insertTail(tail,10);
	tail=insertTail(tail,20);
	tail=insertTail(tail,30);
	//插入前
	listNode(list);
	//插入节点
	insertNode(list,2,15);
	//插入后
	listNode(list);
	//删除
	deleteNode(list,2);
	//删除后
	listNode(list);
	return 0;
}

​ image-20260108101907256

​ 单链表-删除节点

单链表获取链表长度

声明一个变量用来累加每循环一次累加一次到尾节点为止,返回尾节点的长度

这个代码假如前面的代码大家看懂了应该可以轻轻松松看懂吧,本质和遍历一样

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
//获取链表长度
int listLength(Node *L){
	Node*p=L;
	int len=0;
	while(p!=NULL){
		p=p->next;
		len++;
	}
	return len;
}

int main(){
	Node *list=initList();
	//得到当前尾节点
	Node *tail=get_tail(list);
	//每次在尾节点位置插入数据后更新尾节点的位置
	tail=insertTail(tail,10);
	tail=insertTail(tail,20);
	tail=insertTail(tail,30);
	//插入前
	listNode(list);
	//插入节点
	insertNode(list,2,15);
	//插入后
	listNode(list);
	//删除
	deleteNode(list,2);
	//删除后
	printf("%d",listLength(list));
	//链表长度
	listLength(list);
	return 0;
}

​ image-20260108103644323

单链表释放链表

指针p指向头节点后的第一个节点,判断指针p是否指向空节点,如果指针P不为空,用指针q记录指针p的后继节点,释放指针P指向的节点,指针p和指针q指向同一个节点循环

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
//释放列表
void freeList(Node*L){
	//L头节点
	Node *p=L->next;
	Node *q;
	while(p!=NULL){
		q=p->next;
		free(p);
		p=q;
	}
	L->next=NULL;
}

int main(){
	Node *list=initList();
	//得到当前尾节点
	Node *tail=get_tail(list);
	//每次在尾节点位置插入数据后更新尾节点的位置
	tail=insertTail(tail,10);
	tail=insertTail(tail,20);
	tail=insertTail(tail,30);
	//插入前
	listNode(list);
	//插入节点
	insertNode(list,2,15);
	//插入后
	listNode(list);
	//删除
	deleteNode(list,2);
	//删除后
	listNode(list);
	
	//链表长度
	printf("%d\n",listLength(list));
	freeList(list);
	printf("%d\n",listLength(list));
	return 0;
}

​ image-20260108103406542

​ image-20260108103544150

​ image-20260108103603614

好了,最基本的我们说完了——-等一下,你不能走,把这碗鸡汤喝了 狗头狗头狗头

单链表的双指针

这个其实用实际的例子来解释更直观一点,不然太抽象了

例一

​ 单链表应用01-01

​ 单链表应用01-02

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
//找到节点数据
int findNodeFS(Node *L,int k){
	Node *fast=L->next;
	Node *slow=L->next;
	//循环K次每次先走1步,即先走K步
	for(int i=0;i<k;i++){
		fast=fast->next;
	}
	
	while(fast!=NULL){
		fast=fast->next;
		slow=slow->next;
	}
	printf("倒数第%d个节点值为:%d\n",k,slow->data);
	return 1;
}

int main(){
	Node *list=initList();
	//得到当前尾节点
	Node *tail=get_tail(list);
	//每次在尾节点位置插入数据后更新尾节点的位置
	tail=insertTail(tail,10);
	tail=insertTail(tail,20);
	tail=insertTail(tail,30);
	tail=insertTail(tail,40);
	tail=insertTail(tail,50);
	tail=insertTail(tail,60);
	tail=insertTail(tail,70);
	
	listNode(list);
	//找到节点值
	findNodeFS(list,3);
	return 0;
}

​

第一步:我们先假设找到这个4节点(倒数第三个节点),让快慢指针都指向第一个节点即头节点的下一个节点

image-20260108105305089

第二步:先让快指针走3步,这里本质上是用慢指针来找到数据的

​ image-20260108105414949

第三步:快指针走完后两个指针再同步走

​ image-20260108105624598

第四步:一直到快指针遇到尾节点时慢指针就找到了

​ image-20260108105701910

image-20260108105730652

例二

这个例子也是第一眼抽象至极

​ 单链表应用02-01

第一步:我们要先求出两个链表的长度,用于判断两个链表的长度的差距

​ 单链表应用02-02

第二步:让快指针指向更长的那个链表并先走两表的差距长度

​ 单链表应用02-03

第三步:然后两个指针一起动

​ 单链表应用02-04

第四步:然后就会发现两个指针指向同一个地方

​ 单链表应用02-05

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
//初始化节点(带节点数据域参数)  不同于之前的单链表的初始化,因为我们要传参,而不是空参
Node*initListWithElem(ElemType e){
	Node *node=(Node*)malloc(sizeof(Node));
	node->data=e;
	node->next=NULL;
	return node;
}

//查找两个节点共同后缀的起始位置
Node*findIntersectionNode(Node *headA,Node*headB){
	if(headA==NULL||headB==NULL){
		return NULL;
	}
	
	Node*p=headA;
	int lenA=0;
	int lenB=0;
	
	//遍历链表A,获取链表A的长度
	while(p!=NULL){
		p=p->next;
		lenA++;
	}
	
	//遍历链表B,获取链表B的长度
	p=headB;
	while(p!=NULL){
		p=p->next;
		lenB++;
	}
	
	Node *m;//快指针
	Node *n;//慢指针
	int step;//两个单词之间手差值,可以用于快指针先走的步数
	
	if(lenA>lenB){
		step=lenA-lenB;
		m=headA;
		n=headB;
	}else{
		step=lenB-lenA;
		m=headB;
		n=headA;
	}
	
	//让快指针先走step步
	for(int i=0;i<step;i++){
		m=m->next;
	}
	//快慢指针同步走,直到指向同一个节点退出循环
	while(m!=n){
		m=m->next;
		n=n->next;
	}
	return m;
}



int main(){
	Node *listA=initList();
	Node *listB=initList();
	
	//得到当前尾节点
	Node *tailA=get_tail(listA);
	Node *tailB=get_tail(listB);
	//每次在尾节点位置插入数据后更新尾节点的位置
	tailA=insertTail(tailA,'l');
	tailA=insertTail(tailA,'o');
	tailA=insertTail(tailA,'a');
	tailA=insertTail(tailA,'d');
	
	
	tailB=insertTail(tailB,'b');
	tailB=insertTail(tailB,'e');
	
//	这段代码的问题是：
//	每次 insertTail 都会新建一个节点，即使你插入的是相同的字符 'i'，它们也是两个不同的节点。
//	所以 tailA 和 tailB 的尾部节点地址不同，没有共享，自然找不到共同后缀。
	
//	tailA=insertTail(tailA,'i');
//	tailA=insertTail(tailA,'n');
//	tailA=insertTail(tailA,'g');
//	
//	tailB=insertTail(tailB,'i');
//	tailB=insertTail(tailB,'n');
//	tailB=insertTail(tailB,'g');
	
	
	
//	这段代码的核心是：
//  nodeI、nodeN、nodeG 是同一份节点对象，被两个链表共享。
//	因此两个链表在尾部确实指向了同一个物理地址，满足了“共享后缀”的要求。
	
	Node *nodeI=initListWithElem('i');
	tailA=insertTailWithNode(tailA,nodeI);
	tailB=insertTailWithNode(tailB,nodeI);
	
	Node *nodeN=initListWithElem('n');
	tailA=insertTailWithNode(tailA,nodeN);
	tailB=insertTailWithNode(tailB,nodeN);
	
	Node *nodeG=initListWithElem('g');
	tailA=insertTailWithNode(tailA,nodeG);
	tailB=insertTailWithNode(tailB,nodeG);
	
	listNode(listA);
	listNode(listB);
	printf("%c\n",findIntersectionNode(listA,listB)->data);
	
	return 0;
}