摘要：介绍了数据结构中的链表实现。首先概述数据结构的基本概念，包括时间复杂度、空间复杂度等核心指标，以及数据结构的主要分类。重点讲解了链表的特点、分类及实现方法，详细剖析了单向链表的节点定义、创建、头插法、遍历和删除等关键操作，并提供了完整的C语言代码实现。文章还通过对比顺序链表与链表的优缺点，突出链表在动态内存管理方面的优势。最后给出链表操作的实践练习建议，包括多文件编程的实现方法。
一、概要
1、概念
数据结构是计算机存储、组织和管理数据的方式，旨在实现高效的数据访问和修改。它关注数据元素之间的逻辑关系、物理存储方式以及相关操作（如插入、删除、查找等）
程序 = 数据结构 + 算法
2、衡量代码的质量和效率
（1）时间复杂度：数据量的增长与程序运行时间的增长所呈现的比例函数关系，称为时间渐进复杂度函数，也简称时间复杂度。
- 常见的时间复杂度（低 -> 高）：
- O(1)：程序的运行时间与输入数据量无关，始终保持恒定
- O(logn)：程序的运行时间随输入数据量的增长而增长，但增长速度逐渐减慢，最终趋于恒定
- O(n)：程序的运行时间与输入数据量成正比
- O(nlogn)：程序的运行时间是线性时间和对数时间的乘积
- O(n^2)：程序的运行时间与输入数据量的平方成正比
- O(n^3)：程序的运行时间与输入数据量的立方成正比
（2）空间复杂度：数据的增长与程序占据空间的增长所呈现的比例函数关系，称为空间复杂度。
3、数据结构分类
（1）逻辑结构：
线性结构（表）、非线性结构（树）（图）
（2）存储结构：
顺序存储、链式存储、散列存储、索引存储
（3）常见的数据结构：
顺序表、链式表、顺序栈、链式栈、顺序队列、链式队列、二叉树、邻接表、邻接矩阵
二、链表
1、链表概念
（1）顺序链表(数组)特点：
- 存储空间连续
- 访问元素方便
- 无法利用小的空间，必须连续的大空间
- 顺序表元素必须为有限的（不存在无限连续的空间）
插入和删除效率低
（2）链表特点：
- 存储空间不需要连续
- 可以利用一些小的存储空间
- 访问元素不方便
- 链表元素可以没有上限
- 插入和删除效率高
2、链表分类
（1）单向链表：只能通过链表节点找到后一个节点，访问链表元素的方向是单向的
A → B → C → NULL
（2）双向链表：能够通过链表节点找到前一个节点和后一个节点
NULL ⇄ A ⇄ B ⇄ C ⇄ NULL
（3）循环列表：能够通过第一节点快速找到最后一个节点，能够通过最后一个节点快速找到第一个节
A → B → C → A (循环)
（4）内核链表：Linux内核所采用的一种通用的链表结构
三、单向链表
1、定义链表节点类型
（1）链表存放数据的类型
typedef int datatype；
- 定义了
datatype为int类型，表明链表中存放的数据类型为整数
（2）链表节点类型
typedef struct node {
datatype data; //存放数据空间
struct node *pnext; //存放下一个节点地址
}linknode；
- 定义了一个名为
node的结构体，用来表示链表中的节点。结构体中有两个成员： data：用来存放数据，其类型为datatype。pnext：是一个指向node结构体的指针，用来存放下一个节点的地址。- 最后，
node结构体被typedef定义为linknode类型，方便后续使用。
2、空链表的创建
（1）创建一个空的链表节点：
data不需要赋值（最好赋值），空白节点不存放数据，主要为了保证链表操作的便利性，pnext必须赋值为NULL，表示该节点为最后一个节点，将节点地址返回；
（2）代码如下：
/* 创建一个空链表 */
linknode *create_empty_linklist(void)
{
linknode *ptmpnode = NULL;
ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return NULL;
}
ptmpnode->pnext = NULL;return ptmpnode；
}
3、链表的头插法：
（1）步骤：
- 申请新的节点空间
- 将存放的数据让入新申请的数据空间中
- 将新申请节点的pnext赋值为空白节点的pnext
- 将空白节点pnext赋值为新申请节点
（2）代码实现：
/* 插入一个节点 */
int insert_head_linklist(linknode *phead, datatype tmpdata)
{
linknode *ptmpnode = NULL;
ptmpnode = malloc(sizeof(linknode)); //申请空间
if (NULL == ptmpnode)
{
perror("fail to malloc");
return -1;
}
ptmpnode->data = tmpdata; //存放数据
ptmpnode->pnext = phead->pnext; //存放下一个节点地址
phead->pnext = ptmpnode; //更新空白的节点的pnext
return 0;
}
4、链表元素遍历
（1）访问链表中每个节点元素
（2）两种方法：
/* 第一种方法 遍历*/
while （p != NULL） // 指针
p当前指向的是链表中的第一个节点{
p = p -> pnext;
}
/* 第二种方法 遍历*/
while （p ->pnext != NULL）
{
p = p -> pnext;
}
- 方法一：多用于遍历链表中所有节点元素
- 方法二：多用于找到链表最后一个节点
（3）代码实现：
void show_linklist(linknode *phead)
{
linknode *ptmpnode = NULL;
ptmpnode = phead->pnext;
while (ptmpnode != NULL)
{
printf("%d ", ptmpnode->data);
ptmpnode = ptmpnode->pnext;
}
printf("\n");
return;
}
5、链表元素删除
（1）步骤：
- 定义两个指针ptmpnode用来遍历链表查找要删除的节点元素，pprenode永远只想ptmpnode的前一个节点
- 当ptmpnode找到要删除的节点元素，让pprenode->pnext赋值为ptmpnode->pnext将要删除的节点元素释放
- 让ptmpnode判断下一个节点元素是否要删除，直到该指针指向NULL为止
（2）代码实现：
int delete_linklist(linknode *phead, datatype tmpdata)
{
linknode *pprenode = NULL;
linknode *ptmpnode = NULL;
pprenode = phead;
ptmpnode = phead->pnext;
while (ptmpnode != NULL)
{
if (ptmpnode->data == tmpdata)
{
pprenode->pnext = ptmpnode->pnext;
free(ptmpnode);
ptmpnode = pprenode->pnext;
}
else
{
ptmpnode = ptmpnode->pnext;
pprenode = pprenode->pnext;
}
}
return 0;
}
四、练习
1、便于数据结构的练习，将虚拟机进行联网操作，安装visual studio code，同时配置语言实现多文件操作，便于我们进行代码的编写和操作。
2、练习：实现链表的创建，利用链表头插法进行链表元素的遍历和链表元素的删除
（1）main函数，定义链表，函数的调用
（2）各个参量的声明
（3）函数实现的具体过程
（4）结果的实现
