从零开始的数据结构学习02——单链表（线性表）

链表，指针，结构体，malloc，链表操作

前情提要：

上一章我们学习了顺序表，我们发现顺序表的一大优点就是：简单、支持随机存取（即可以通过首地址+偏移量直接访问地址），适用于静态数据。但是如果我们遇到数据量较大的情况（如顺序表中存储了一百万数据量），这时假如我们再对该顺序表进行删除和插入的操作，那么每删除/插入一个数据，都可能造成大量数据挨个前移/后移。这也表现出了顺序表的缺点，即不够灵活。那么，有没有更为灵活的存储结构呢？这就要引入链表的思想了。

1.初识链表

指针，结构体，内存空间
链表基于指针实现，它用链式存储结构实现线性表，我们可以从内存空间的角度来理解链表：
图一：
在这里插入图片描述
数组的痛点在于：它像一排固定座位——想加个新观众？得让后面所有人集体后退，效率低到崩溃。
而链表的解法很聪明：它不依赖连续内存，而是用“动态节点”实现灵活拼接。
关键来了：每个节点都是“按需创建”的。
就像你买咖啡时想加新订单？
直接买个新杯子（malloc分配内存），
里面装好咖啡（数据域），
再贴个标签写“购买人是小明”（指针域指向下一个节点）。
数组的“挪动所有人代价” = O(n)，
链表的“贴标签”代价 = O(1)。
动态分配内存，就是链表能“灵活插队”的魔法源头。

小tips：

我们即将正式开始对链表的代码实现部分，有两点是非常值得理解和记忆的

  1. 指针指向的本质是地址赋值。
  2. malloc申请地址空间时，假设我们int* s=(int*)malloc(sizeof(int));虽然对于计算机来说，malloc的这段空间没有名字，但是我们会人为命名该空间为s，也就是说，我们通常会人为地用指针的名称来表示一段空间的名称。
  3. 节点/结点的说法都是对的，下面我们都用节点进行表述

2.链表的初始化

结构体，头指针，头节点，首元节点

由图1可见，在链表的实现中，需要有动态创建节点的操作，而一个节点是由数据域+指针域（下一个数据所在节点的地址）所组成的，也就是说节点依然是由两种不同数据类型组成的——结构体again。
那么，问题来了，我们要如何确定第一个节点的位置？一般的节点都是由上一个节点的指针域所指向的，因此我们不难想到，我们只需要用一个指针（头指针，即指向链表中第一个节点的指针，一般用L表示）来保存第一个节点的位置即可，L指向第一个节点，因此L也指向整个链表，所以我们人为命名第一个节点和整个链表都为L。

2.1第一个节点是头节点or首元节点？

这里有两个重要概念需要进行辨析：
首先来看头节点的定义。头节点，即用来保存第一个数据所在节点的地址的节点，其数据域是不用的（数据域里只有脏数据）。它的作用是，使得第一个数据和其他数据所在的节点统一起来，同时使得空链表和非空链表统一起来。
而首元节点的定义非常直白——就是指第一个数据所在的节点。

概念辨析：

  • 链表中的第一个节点是头节点吗？——不是，因为可能没有头节点。
  • 链表中的第一个节点是首元节点吗？——不是，因为可能有头节点。

链表分为：带头节点的链表（默认）和不带头节点的链表。

  • 头指针是指向头节点的指针吗？——不是，因为可能没有头节点。
  • 头指针是指向整个链表的指针吗？——是的，不管头指针指向头节点/首元节点，都能找到整个链表。

如果第一个节点是首元节点，会发生什么情况呢？如果是这样，就会导致第一个节点有一个非常特殊的地方：其他节点都是“合租”，只有头节点的指针住“单间”。头节点为L，而其他节点为p->next，这导致我们如果对链表头部进行删除/插入操作，会需要对头指针进行修改，并且在链表为空时的形式是头指针为NULL表示空表，与普通节点的形式有别。因此，为了避免这样过于麻烦的操作，且为了保证所有节点的结构一致，我们接下来的代码中都会默认第一个节点是头节点。
此处附上一张图帮助大家更好地理解两种链表的区别：
在这里插入图片描述

下面我们来看链表初始化的代码示例：

//1.声明一个链表的节点结构
typedef struct Node
{
	int data;
	struct Node * next;	//逻辑上：下一个数据所在节点的地址
} Node, * LinkList;	//此处LinkList等价于Node*
/*增强可读性
LinkList p：指向链表的头指针
Node * p：指向链表的某个节点的指针
*/
//2.下面我们来初始化一个带头节点的空链表L
Node * InitLink()
{	//声明一个头节点指针或赋NULL
	Node * head = (Node*)malloc(sizeof(Node));
	//if(head==NULL)
	head->next=NULL;
	return head;
}

/*注意，千万不能写成下面这样
Node * InitLink()
{
	Node head;
	head.next=NULL;
	return &head;
}
这样写的话head就变成了一个局部变量，我们知道局部变量在栈区而非堆区，
在栈区的变量会随着函数return后被自动回收，因而return后L指向的空间被
自动回收了，因此L也变成了一个野指针,这是非常危险的，这会使得L后续对
内存进行非法操作。*/

int main()
{
	LinkList L = NULL;
	L = InitLink();
	return 0;
}

3.链表的其他操作（增、查、删、改）

增加、查找、删除、修改

3.1增加操作+查找操作

3.1.1头插法：每次在头节点后添加一个数据k

在这里插入图片描述

头插法可以分为三步来看：

  1. 创建节点s，把数据k放到节点s的数据域中；
  2. 节点s的指针域指向原来的首元节点；
  3. 头节点的指针区域指向新节点s；

在代码的具体实现上，我们需要注意：
以上图为例，我们要先把3的地址赋给k，再把k的地址赋给3，否则3的地址会被覆盖掉！因为3的地址是存在头节点中的，所以我们一定要注意地址赋值的先后顺序，否则会造成整个链表的丢失。

下面我们来看头插法的代码示例：

//头插法
//把L看成链表，带返回值（从理解的角度来看，这样写会比void+地址更好理解，因为多一个节点链表肯定会发生变化）
LinkList Head_insert(LinkList L,int k)
{
	Node * s = (Node*)malloc(sizeof(Node));
	/*创建节点s，Node*s,实际是指针s指向了该节点，后续对节点s的操作，
	本质上是通过指针s操作节点中的成员变量*/
	//if(s==NULL)
	s->data=k;//把数据k放到节点s的数据域中
	s->next=L->next;//节点s的指针域指向原来的首元节点，头节点L的指针域中保存了原首元节点的地址
	//L->next本质上代表头节点的指针域，但也可以代表首元节点（因为它指向了首元节点）
	L->next=s;
	return L;
}

int main()
{
	LinkList L = NULL;
	L=InitLink();
	L=Head_insert(L,1);
	L=Head_insert(L,2);
	L=Head_insert(L,3);
	return 0;
}

3.1.2尾插法：在尾节点之后添加数据k

在这里插入图片描述

尾插法也同样可以分为三步来看：

  1. 创建节点s，把数据k放到节点s的数据域中，s的指针域为NULL；
  2. 从头结点开始遍历循环找到尾节点p；
    （1）看哪个节点的指针域为NULL；
    （2）从头节点开始找（空表无首元节点）
    （3）p=p->next;（牢记指针指向就是地址赋值）
  3. 尾节点p之后插入节点s；

下面是尾插法的代码示例：

//尾插法
LinkList Rear_insert(LinkList L,int k)
{
	Node * s = (Node*)malloc(sizeof(Node));	//创建节点s
	//if(s==NULL)
	s->data=k;	//把数据k放到节点s的数据域中
	s->next=NULL;
	//找尾节点
	Node * p = L;	//一开始p指向头节点，从头节点开始找
	while(p->next!=NULL){	//如果节点p的指针域不为NULL，则说明后面还有节点
		p=p->next;
	}
	p->next=s;
	return L;
}

3.1.3指定位置插入：在数据k之后插入数据k1

首先第一个问题是，我们要找到数据k应该从哪里开始找？头节点OR首元节点？
答案应当是从首元节点开始找，因为头节点的数据域是脏数据，假设头节点的数据域中为7，而我们要找的数据k也为7，那必然会对查找结果造成干扰。因此，为了规避脏数据的影响，我们选择从首元节点开始找。
在这里插入图片描述

指定位置查找同样也可以分为三步来看：

  1. 创建节点s，把数据k放到节点s的数据域中；
  2. 找数据k所在节点p（还要判断L->next!=NULL，否则就说明k不存在，无法进行插入操作)；
  3. p节点之后插入s节点；

3.1.3.1查找操作

不过在写指定位置插入的代码之前，我们首先要先写一个查找操作的函数：
用指针p进行遍历查找，为了规避头节点脏数据影响，应从首元节点开始找，找的过程中 要先判空再对比数据是否相同

查找操作的代码如下：

Node * Find(LinkList L,int k)
{
	//从首元节点开始找
	Node * p = L->next;	//p有可能是空的
	while(p!=NULL&&p->data!=k)
	{	//节点p的数据域不为看，说明p不是我们要的节点，继续往后走
		p=p->next;
	}
	/*while循环停止的情况为：（1）p为NULL，k不存在；
	（2）p不为NULL，并且数据域是k，p是要找的节点*/
	return p;
}

写完查找的函数之后，我们便可以开始写指定位置插入的代码了，这部分的代码在地址赋值上和头插法是类似的。我们要首先将p->next赋值给s->next，再将s赋值给p->next，如果顺序颠倒，那s节点的地址会将原本k的指针域所存放的下一个数据的地址覆盖掉。
下面是代码示例：

//3.指定位置插入数据：在k之后插入数据k1
LinkList Insert(LinkList L,int k,int k1)
{
	Node * s = (Node*)malloc(sizeof(Node));
	//if(s==NULL)
	s->data=k1;
	Node * p = Find(L,k);
	if(p==NULL)
	{
		printf("%d不存在，无法插入\n",k);
		return L;
	}
	s->next=p->next;
	p->next=s;
	return L;
}

3.2修改操作：把链表中的某个数据k改成k1

关于本部分没有什么太值得注意的，整体思路就是调用查找函数，找到k的位置，然后用k1赋值覆盖。
下面是代码示例：

//4.修改操作
Node * p = Find(L,k);
if(p==NULL)
{
	printf("%d不存在\n",k);
	return L;
}
p->data=k1;

3.3删除操作：在链表中删除数据k

删除操作我们也能分为三步来看：

  1. 找到数据k所在节点p及前一个节点pre
  2. pre指向p的后一个节点
  3. 删除p节点

在这里插入图片描述

不过删除操作中我们无法再调用Find函数，因为Find只能找到p，找不到pre。

下面是代码示例：

//5.删除操作
LinkList Delet(LinkList L,int k)
{	//p从首元节点开始，pre从头节点开始，一起往后走
	Node * p = L->next;
	Node * pre = L;
	while(p!=NULL&&p->data!=k)
	{
		p=p->next;
		pre=pre->next;
	}	//两种情况：（1）p为NULL,k不存在；（2）p存在，k为数据域，p是要找的节点
	if(p==NULL)
	{
		printf("%d不存在，无法删除\n",k);
	}
	else{
		pre->next=p->next;	//pre指向p的后一个节点
		free(p);
		p=NULL;
	}
	return L;
}

当然，我们也能对上面的代码进行一些优化，我们可以发现虽然我们无法从节点p反向找到节点pre，但是我们可以通过节点pre找到节点p和节点p->next，因为p->next就是pre。
优化代码如下：

LinkList Delet(LinkList L,int k)
{
	Node * pre = L;
	while(pre->next!=NULL&&pre->next->data!=k)
	{
		pre=pre->next;
	}
	if(pre->next==NULL)
	{
		printf("%d不存在，无法删除\n",k);
	}
	else{
		Node * p = pre->next;	//保存要删除节点的指针，以便后续释放该节点占用的内存
		pre->next=pre->next->next;
		free(p);
		p=NULL;
	}
	return L;
}

4.汇总

那么到这里，对单链表的学习也基本完成了，接下来我会将通过Show函数将先前的代码示例进行汇总，并提供一份可供展示单链表效果的代码。
Show函数代码示例如下：

void Show(LinkList L)
{
	Node * p = L->next;
	if(p==NULL)
	{
		printf("空链表\n");
		return;
	}
	while(p!=NULL)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}

汇总代码如下：

#include<stdio.h>
#include<stdlib.h>
//声明一个链表的节点结构
typedef struct Node
{
	int data;
	struct Node * next;	//逻辑上：下一个数据所在节点的地址
} Node,* LinkList;	//此处LinkList等价于Node*

//初始化一个带头节点的空链表L
Node * InitLink()
{	//声明一个头节点指针或赋NULL
	Node * head = (Node*)malloc(sizeof(Node));
	//if(head==NULL)
	head->next=NULL;
	return head;
}

//头插法
LinkList Head_insert(LinkList L,int k)
{
	Node * s = (Node*)malloc(sizeof(Node));
	/*创建节点s，Node*s,实际是指针s指向了该节点，后续对节点s的操作，
	本质上是通过指针s操作节点中的成员变量*/
	//if(s==NULL)
	s->data=k;//把数据k放到节点s的数据域中
	s->next=L->next;//节点s的指针域指向原来的首元节点，头节点L的指针域中保存了原首元节点的地址
	//L->next本质上代表头节点的指针域，但也可以代表首元节点（因为它指向了首元节点）
	L->next=s;
	return L;
}

//尾插法
LinkList Rear_insert(LinkList L,int k)
{
	Node * s = (Node*)malloc(sizeof(Node));	//创建节点s
	//if(s==NULL)
	s->data=k;	//把数据k放到节点s的数据域中
	s->next=NULL;
	//找尾节点
	Node * p = L;	//一开始p指向头节点，从头节点开始找
	while(p->next!=NULL){	//如果节点p的指针域不为NULL，则说明后面还有节点
		p=p->next;
	}
	p->next=s;
	return L;
}

//查找操作
Node * Find(LinkList L,int k)
{
	//从首元节点开始找
	Node * p = L->next;	//p有可能是空的
	while(p!=NULL&&p->data!=k)
	{	//节点p的数据域不为看，说明p不是我们要的节点，继续往后走
		p=p->next;
	}
	/*while循环停止的情况为：（1）p为NULL，k不存在；
	（2）p不为NULL，并且数据域是k，p是要找的节点*/
	return p;
}

//指定位置插入数据：在k之后插入数据k1
LinkList Insert(LinkList L,int k,int k1)
{
	Node * s = (Node*)malloc(sizeof(Node));
	//if(s==NULL)
	s->data=k1;
	Node * p = Find(L,k);
	if(p==NULL)
	{
		printf("%d不存在，无法插入\n",k);
		return L;
	}
	s->next=p->next;
	p->next=s;
	return L;
}

//删除操作
LinkList Delet(LinkList L,int k)
{	//p从首元节点开始，pre从头节点开始，一起往后走
	Node * p = L->next;
	Node * pre = L;
	while(p!=NULL&&p->data!=k)
	{
		p=p->next;
		pre=pre->next;
	}	//两种情况：（1）p为NULL,k不存在；（2）p存在，k为数据域，p是要找的节点
	if(p==NULL)
	{
		printf("%d不存在，无法删除\n",k);
	}
	else{
		pre->next=p->next;	//pre指向p的后一个节点
		free(p);
		p=NULL;
	}
	return L;
}

//展示函数
void Show(LinkList L)
{
	Node * p = L->next;
	if(p==NULL)
	{
		printf("空链表\n");
		return;
	}
	while(p!=NULL)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}

int main()
{
	LinkList L = NULL;
	L=InitLink();
	L=Head_insert(L,1);
	L=Head_insert(L,2);
	L=Head_insert(L,3);
	Show(L);
	L=Rear_insert(L,4);
	L=Rear_insert(L,5);
	Show(L);
	L=Insert(L,1,10);
	L=Insert(L,4,7);
	Show(L);
	L=Delet(L,100);
	L=Delet(L,1);
	L=Delet(L,5);
	L=Delet(L,4);
	Show(L);
	return 0;
}

最后的最后：
主包是大一学生，目前博客打算以整理平时所学的知识点为主（当成笔记本来用 ），欢迎大家一起讨论，如有什么错误或者理解不够深刻也欢迎大家的批评指正。

# 数据结构 # 学习 # c语言 # 算法 # 开发语言 # 学习方法
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

cover

【Agent Memory篇】01：OpenClaw整体架构与设计哲学

avatar AtomGit开源社区
cover

基于单位功率因数的永磁同步电机（SPMSM）矢量控制Simulink仿真探索

avatar AtomGit开源社区
cover

分布式驱动汽车稳定性控制：从模型搭建到控制策略探索

avatar AtomGit开源社区