目录
一、引言
1.数据结构的重要性
数据结构是计算机科学的基石，如同搭建高楼大厦的砖块，合理选择与运用数据结构能让程序的运行效率、存储空间利用实现质的飞跃。无论是开发大型软件系统，还是解决日常算法问题，熟悉数据结构都是迈向高效编程的关键一步。例如在搜索引擎中，恰当的数据结构可实现快速的数据检索，确保用户能迅速获取所需信息；在图形图像处理领域，特定的数据结构能助力复杂图形的构建与渲染，呈现震撼视觉效果。
2.单链表在其中的地位
单链表在数据结构中具有重要地位，主要体现在以下几个方面：
- 基础且关键的入门数据结构：学习数据结构时，单链表是重要的基础内容，是从基础编程语言过渡到数据结构学习的关键一步，能反映学习者对基础语言中指针、结构体及函数模块等知识的掌握程度，熟练掌握单链表有助于提升编程功底与代码能力.
- 线性表的典型代表：线性表是常见的数据结构，包括顺序表、链表、栈、队列、字符串等，而单链表是链表的一种基本形式，也是线性表在链式存储结构上的具体实现，其通过指针链接数据元素，形成逻辑上连续的线性结构.
- 动态存储结构的代表：与数组等静态存储结构相比，单链表是一种物理存储结构上非连续、非顺序的动态存储结构，在需要增加或删除节点时，可灵活地向内存申请或释放节点空间，无需像数组那样预先分配大量连续空间，避免了空间浪费，也提高了内存的使用效率.
- 数据操作的灵活性：在进行插入和删除操作时，单链表无需挪动大量数据元素，时间复杂度相对较低，在头部插入、中间插入或尾部插入以及按值或位置删除节点等操作上，具有较高的效率，相比之下，数组在进行类似操作时往往需要移动大量元素，时间复杂度较高.
- 构建复杂数据结构的基础单元：单链表常作为构建更复杂数据结构的基础组成部分，如哈希桶、图的邻接表等数据结构常采用单链表来实现存储和管理数据，体现了单链表在数据结构体系中的基础性和重要性.
二、什么是单链表
1.单链表的定义
单链表是一种基础的数据结构，它由一系列节点组成，每个节点包含两个部分：一个数据域和一个指向下一个节点的指针域。在单链表中，数据元素可以非连续地存储在内存中，而节点之间通过指针相互连接。
在单链表中，每个节点由一个数据元素和一个指针构成。数据元素可以是任何类型，而指针则指向链表中的下一个节点。如果一个节点的指针为空（NULL），则表示它是链表的最后一个节点。单链表通常通过一个头指针来访问，头指针指向链表的第一个节点。
无头单向非循环链表
没有专门的头节点，链表直接以第一个存储实际数据的节点开始。这使得链表的结构看起来更加简洁，但在操作时，尤其是涉及到链表头部的操作时，需要额外考虑链表为空的特殊情况。
带头单向非循环链表
有一个专门的头节点。这个头节点不存储实际的数据元素（当然，也可以存储一些与链表相关的辅助信息，如链表的长度等，但通常不用于存储常规数据）。它的主要作用是为了方便链表的操作。例如，在插入和删除操作时，不需要对链表为空的情况进行特殊处理，因为始终有一个头节点存在。
2.基本概念解释
- 节点：是单链表的基本组成单元，如同链条上的一个个环扣，每个节点承载着单链表的部分数据信息以及与其他节点的连接关系，它们相互串联构成完整的链表结构。
- 数据域：作为节点的关键组成部分，是真正存储数据元素的区域，数据域中的内容依据具体的应用场景而定，可以是整数、字符串、结构体等各种类型的数据，比如在学生信息管理系统里，数据域可能存放学生的学号、姓名、成绩等详细信息。
- 指针域：它负责维护节点之间的逻辑顺序，是节点中用于指向下一个节点存储位置的指针变量，通过指针域的指向，将零散分布在内存中的各个节点按特定顺序串接起来，形成一条具有先后次序的链表，确保数据能够按照线性的方式被访问和处理。
三、单链表的结构特点
1.与数组对比的优势
- 内存动态分配更灵活：数组在创建时需要预先确定大小，这就要求开发者提前预估所需存储的数据量。一旦预估不准，数据量超出数组容量，可能引发数组越界错误；而若预估过大，又会造成内存空间闲置浪费。单链表则不同，它的节点是按需逐个创建并分配内存的，系统会根据实际插入的数据动态地为新节点开辟空间，完美契合数据量不确定的应用场景，从根本上避免了因空间分配不合理导致的问题。
- 插入和删除操作高效便捷：在数组中执行插入或删除操作时，往往牵一发而动全身。以在数组中间插入一个元素为例，为了给新元素腾出位置，其后的所有元素都得依次向后挪动一位，涉及大量的数据移动，时间复杂度高达 O (n)；删除操作同理，删除一个元素后，其后元素需逐个前移填补空位。单链表在此方面表现卓越，插入节点时，只需调整待插入位置前后节点的指针指向，时间复杂度稳定在 O (1)；删除节点亦是如此，修改相关指针便可轻松移除节点，无需大规模移动数据，极大地提升了操作效率。
2.存在的劣势
- 随机访问能力欠佳：数组凭借下标可以实现瞬间定位任意元素，时间复杂度低至 O (1)，就像一本带有目录的书籍，通过页码（下标）能快速翻到指定内容。单链表却没有这般 “超能力”，由于其节点在内存中呈离散分布，彼此依靠指针串联，要访问链表中的某个特定节点，只能从表头开始，顺着指针逐个节点排查，平均下来时间复杂度为 O (n)，如同在一条没有索引的链条上寻找特定环扣，效率明显较低。
- 额外存储开销较大：每个单链表节点除了要为数据预留存储空间（数据域），还得专门开辟一块空间用于存放指向下一节点的指针（指针域）。这意味着相较于单纯存储数据的数组，单链表在存储相同数量的数据时，占用的内存空间更多，尤其在处理大规模数据时，这种额外的指针开销累积起来不容小觑，对内存资源造成一定的 “负担”。
- 遍历效率相对低下：数组元素在内存中连续存放，顺序遍历访问时，CPU 能够充分利用内存的局部性原理，快速地从相邻内存单元读取数据，如同沿着一条通畅的高速公路疾驰。单链表节点散布在内存各处，遍历过程中，每访问下一个节点，都要通过指针进行跳转，这个跳转操作涉及复杂的内存寻址过程，打断了 CPU 原本流畅的访存节奏，使得遍历速度大打折扣，相比数组的顺序遍历，效率明显落后。
注意：
1.从上图可以看到，链式机构在逻辑上是连续的，在物理结构上不一定连续；
2.现实中结点⼀般都是从堆上申请的；
3.从堆上申请的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续
四、单链表的基本操作
在这里，我们以无头单向非循环链表为例：
1.节点的创建
在上面讲过，一个链表由多个节点链接构成，而一个节点由数据域和指针域构成，数据域存放数据，指针域指向下一个节点，所有我们定义一个结构体SLTNode，包含数据域data和指向下一个节点的指针域next。
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data; //数据域
struct SListNode* next; //指针域
}SLTNode;现在，我们已经定义的节点的类型，接下来，我们在main函数中定义一个SLTNode的结构体类型的指针plist并让它指向空，在后面我们让它作为头指针对它进行节点的插入操作。
SLTNode* plist = NULL;
2.动态申请一个节点
在我们进行插入节点之前，我们需要先生成一个新的节点，并把数据存入新节点的数据域data，无论是头插、尾插、或者在任意位置插入节点，我们都需要生成新的节点，所有在这里，我把它写成了一个函数。
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //开辟新的节点
if (newnode == NULL) //如果开辟失败则返回NULL
{
perror("malloc fail");
return NULL;
}
newnode->data = x; //在新节点中插入数据
newnode->next = NULL; //将新节点指向的下一个节点置为空
return newnode; //返回新节点的地址
}
3.插入节点
3.1尾插
如果当前为空链表，那么直接让plist指向新生成的节点即可。
如果当前链表不为空，那么我们需要找到最后一个节点（找尾），在最后一个节点之后插入新的节点。
我们定义一个结构体指针tail进行找尾，首先我们让它指向头结点，然后让它指向下一个节点（tail=tail->next），判断当前节点的下一个节点是否为空，如果不为空则让tail在次指向下一个节点，接着判断，直到tail的下个节点为空，那么tail指向的就是尾节点，找到尾节点之后，让tail指向新节点即可。
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
//链表本身就是空的
if (*pphead ==NULL)
{
*pphead = newnode;
}
//链表本身不为空
else
{
//找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}void SLTPushBack(SLTNode** pphaed, SLTDataType x);在这里为何要穿二级指针呢？传一级指针可以吗？
在main函数中，我们定义的是SLTNode* plist，如果链表本身尾空，我们需要生成新的节点，使plish指向新的节点，假如传一级指针（传值调用），在运行窗口会发现只会打印NULL，因为形参的改变不会影响到实参，所有需要传二级指针（传址调用），从而改变实参。
3.2头插
相对于尾插来说，头插十分简单，因为头插不用找尾，直接生成一个新节点，让新节点的next指向链表头结点即可，最后别忘了让头节点指针指向新的头结点。
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}3.3在pos之前插入
在前面学习了尾插，头插之后，我们还需要学习在某个位置插入。在这里，首先说一下在pos之前插入，pos是一个节点的地址（在5.查找节点时会学习查找某一个节点，并返回其地址）。
大致思路：
- 如果pos节点的地址等于头结点的地址时调用头插SLTPushFront即可。
- 如果链表中有多个节点，pos不等于头结点的地址时，那么要找到pos位置之前的节点，在pos位置之前的节点后链接一个新的节点，让新的节点在链接pos位置的节点即可。
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead != NULL && pos != NULL);
if (*pphead==pos)
{
SLTPushFront(pphead, x);
}
else //有多个结点
{
SLTNode* PreviousNode = *pphead;
while (PreviousNode->next != pos)
{
PreviousNode = PreviousNode->next;
}
//找到插入位置后，开辟新的空间
SLTNode* newnode = BuySLTNode(x);
PreviousNode->next = newnode;
newnode->next = pos;
}
}3.4在pos位置后面插入
在pos位置后面插入，我们需要生成一个新节点，并且找到pos位置之后的节点（pos->next）让新节点的next指向pos位置之后的节点，然后让pos->next指向新节点，这样整个链表便又连接起来了。
如果不是很理解，可以自己画图理解一下，在这里就不画图了！！！
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos != NULL);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}4.删除节点
4.1尾删
大致思路：
- 如果只有一个节点时，直接释放掉这个节点即可。
- 如果有多个节点要找到链表中倒数第二个节点和最后一个节点，释放掉最后一个节点，让倒是第二个节点的next指向空。
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);
//只有一个结点
if ((*pphead)->next==NULL)
{
free(*pphead);
*pphead = NULL;
}
else//多个结点
{
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
4.2头删
大致思路：
- 保存第一个节点的地址，找到第二个节点，让头指针指向第二个节点。
- 释放第一个节点。
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);
SLTNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}4.3在pos位置删除
大致思路：
- 如果pos位置等于头结点位置，那么只有使用头删即可。
- 如果pos位置不等于头结点的位置，那么我们需要找到pos之前的节点，让pos之前的节点与pos位置之后的节点链接，释放pos位置的节点。
void SListErased(SLTNode** pphead, SLTNode* pos)
{
assert(pphead != NULL);
assert(pos != NULL);
assert(*pphead);
if (*pphead==pos)
{
SLTPopFront(pphead);
}
else
{
SLTNode* PreviousNode = *pphead;
while (PreviousNode->next != pos)
{
PreviousNode = PreviousNode->next;
}
PreviousNode->next = pos->next;
free(pos);
//pos = NULL;
}
}4.4在pos位置后面删除
大致思路：
- 找见要删除的节点，也就是pos->next，并存起来。
- 找见要删除的节点后面的节点，也就是pos->next->next，让pos->next与要删除的节点的后面的节点链接（pos->next=pos->next->next）。
- 释放要删除的节点。
void SlistEraseAfter(SLTNode* pos)
{
assert(pos != NULL && pos->next != NULL);
找见pos位置的下一个结点的下一个结点
//SLTNode* secondnode = pos->next->next;
//free(pos->next);
//pos->next = secondnode;
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
5.查找节点
查找节点函数需要传入的参数为头结点和要查找的值，如果找到这个值返回这个结点的地址，没有找到，就返回NULL；
大致思路：
- 遍历整个链表，当结点为空时停止循环。
- 判断每个节点的data是否与要查找的值x相等，如果相等则返回当前节点的地址，不相等，就指向下一个节点（cur=cur->next）。
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur !=NULL)
{
if (cur->data==x)
{
return cur;
}
else
{
cur = cur->next;
}
}
printf("没有找到\n");
return NULL;
}6.打印链表
很简单，直接看代码。
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d ", cur->data);
cur = cur->next;
//cur++; 不能这么写，链表在内存中不一定连续
}
printf("NULL\n");
}7.链表销毁
在链表销毁完成后，我们需要把之前定义的plish置空，一种方式是函数里面自动置空，需要传二级指针（传址调用），令一种是用的人置空，只需要一级指针即可。
大致思路：
- 从前往后销毁
- 保存当前节点的下一个节点：tmp=cur->next
- 释放当前节点
- 当前节点等于tmp
- 循环直链表为空
void SLTDestory(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
SLTNode* tmp = cur->next;
free(cur);
cur = tmp;
}
}五、完整代码
1.SList.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
//生成结点
SLTNode* BuySLTNode(SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphaed, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphaed);
//头插
void SLTPushFront(SLTNode** pphaed, SLTDataType x);
//头删
void SLTPopFront(SLTNode** pphaed);
//单链表查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//pos之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//pos位置删除
void SListErased(SLTNode** pphead, SLTNode* pos);
//pos后面插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//pos位置后面删除
void SlistEraseAfter(SLTNode* pos);
//链表销毁(交给用的人置空)
void SLTDestory(SLTNode* phead);
//链表销毁(函数置空)
void SLTDestoryN(SLTNode** pphead);2.SList.c
#include"SList.h"
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d ", cur->data);
cur = cur->next;
//cur++; 不能这么写，链表在内存中不一定连续
}
printf("NULL\n");
}
//生成结点
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//尾插 本质：原尾结点中要存储新的尾结点的地址(不为空链表的尾插)
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
if (*pphead ==NULL) //链表本身就是空的
{
*pphead = newnode;
}
else //链表本身不为空
{
//找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
//尾删1
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);
//只有一个结点
if ((*pphead)->next==NULL)
{
free(*pphead);
*pphead = NULL;
}
else//多个结点
{
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
尾删2
//void SLTPopBack(SLTNode** pphead)
//{
// assert(pphead);
// assert(*pphead != NULL);
// //只有一个结点
// if ((*pphead)->next == NULL)
// {
// free(*pphead);
// *pphead = NULL;
// }
// else//多个结点
// {
// SLTNode* tail = *pphead;
// SLTNode* prev = *pphead;
// while (tail->next->next != NULL)
// {
// prev = tail;
// tail = tail->next;
// }
// free(tail);
// tail = NULL;
// prev->next = NULL;
// }
//}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);
SLTNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}
//单链表查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur !=NULL)
{
if (cur->data==x)
{
return cur;
}
else
{
cur = cur->next;
}
}
printf("没有找到\n");
return NULL;
}
//pos之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead != NULL && pos != NULL);
if (*pphead==pos)
{
SLTPushFront(pphead, x);
}
else //有多个结点
{
SLTNode* PreviousNode = *pphead;
while (PreviousNode->next != pos)
{
PreviousNode = PreviousNode->next;
}
//找到插入位置后，开辟新的空间
SLTNode* newnode = BuySLTNode(x);
PreviousNode->next = newnode;
newnode->next = pos;
}
}
//pos后面插入
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos != NULL);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//pos位置删除
void SListErased(SLTNode** pphead, SLTNode* pos)
{
assert(pphead != NULL);
assert(pos != NULL);
assert(*pphead);
if (*pphead==pos)
{
SLTPopFront(pphead);
}
else
{
SLTNode* PreviousNode = *pphead;
while (PreviousNode->next != pos)
{
PreviousNode = PreviousNode->next;
}
PreviousNode->next = pos->next;
free(pos);
//pos = NULL;
}
}
//pos位置后面删除
void SlistEraseAfter(SLTNode* pos)
{
assert(pos != NULL && pos->next != NULL);
找见pos位置的下一个结点的下一个结点
//SLTNode* secondnode = pos->next->next;
//free(pos->next);
//pos->next = secondnode;
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
//链表销毁
void SLTDestory(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
SLTNode* tmp = cur->next;
free(cur);
cur = tmp;
}
}
//链表销毁(函数置空)
void SLTDestoryN(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* tmp = cur->next;
free(cur);
cur = tmp;
}
*pphead = NULL;
}