AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】手把手教你单链表（c语言）（附源码）

2024-11-05 10
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。

前言

       之前我们学习了顺序表，基于顺序表的结构和实现方式，它有以下缺陷：


1.指定位置、头部的插入/删除的时间复杂度是O(N)，效率并不是很高。


2.在增容时，需要申请额外的空间，当连续的空间不足时，就需要重新开辟空间并且拷贝数据，消耗较大。


3.由于增容操作每次都是以2倍的形式增长，所以势必会造成一定的空间浪费。


鉴于上述数组操作的局限性，我们有必要引入单链表这一更为灵活高效的数据结构。


1.单链表的概念与结构

链表的概念：链表是一种数据内存地址不连续、但是逻辑顺序连续的数据结构。它的逻辑顺序由链表中节点的指针相连接。


节点：由两部分组成：存储数据元素的部分称之为“数据域”，存放其他节点地址的部分称之为“指针域”。每一个数据元素存放于一个“节点”中。


而单链表，也叫做单向链表，它的节点的指针域中存放的是下一个节点的地址。这样节点与节点之间互相连接，就像链条一样将数据串联起来。


单链表的结构如图：



可以看到，单链表就像火车一样，而每一个节点就相当于是一节车厢，它们之间用指针串联在一起。注意：单链表只能做到由前一个节点找到后一个节点，无法逆转；最后一个节点的指针域为空指针。


2.单链表的结构定义

       我们在定义单链表的结构时，定义的是它的节点的结构。代码如下：

typedef int SLTDataType;
 
//定义单链表的节点
typedef struct SListNode
{
    SLTDataType data;//数据域
    struct SListNode* next;//指针域
}SLTNode;

可以看到，它的指针域是指向自己本身类型的指针，这种定义方式也叫做结构体的自引用。它可以使得该节点能够存放一个相同类型节点的地址，并且进行访问操作。


3.单链表的实现

3.1 单链表的方法声明

       单链表的一些常用方法的声明如下：

//打印链表
void SLTPrint(SLTNode* phead);
 
//创建新节点
SLTNode* SLTBuyNode(SLTDataType n);
 
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType n);
 
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType n);
 
//尾删
void SLTPopBack(SLTNode** pphead);
 
//头删
void SLTPopFront(SLTNode** pphead);
 
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType n);
 
//指定位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType n);
 
//指定位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType n);
 
//删除指定位置节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
 
//销毁链表
void SLTDestroy(SLTNode** pphead);

接下来，我们尝试逐一实现以上方法。


3.2 单链表方法实现

3.2.1 打印链表

       打印链表时，我们需要定义一个指针，通过它遍历链表并访问它的数据元素：

//打印链表
void SLTPrint(SLTNode* phead)
{
    SLTNode* cur = phead;//定义指针指向头节点
    while (cur != NULL)//最后一个节点的next为空，cur等于空则说明遍历结束
    {
        printf("%d ", cur->data);//访问数据并打印
        cur = cur->next;//对cur解引用拿到下一个节点的地址，然后赋值给cur，cur就指向了下一个节点
    }
    printf("\n");
}

这里我们需要注意理解语句“cur = cur->next”，由于next存放的是下一个节点的地址，所以将其赋值给cur，cur就指向了下一个节点，循环往复，就达到了遍历的效果。

3.2.2 创建新节点

       在我们进行元素插入操作时，往往要将数据存放在一个节点当中，然后将这个节点插入链表。所以我们将创建节点的操作封装成一个函数：

//创建新节点
SLTNode* SLTBuyNode(SLTDataType n)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//动态开辟一个节点大小的内存
    if (newnode == NULL)//内存开辟失败，则直接退出程序
    {
        perror("malloc");
        exit(1);
    }
    newnode->data = n;//将数据赋值给节点的数据域
    newnode->next = NULL;//为了确保链表末尾为空指针，所以创建的所有节点默认next为空
    return newnode;//将节点返回
}

3.2.3 尾插

       接下来我们学习尾插操作。既然要在链表尾部插入数据，那么就需要我们顺着链表的头节点找到尾部的节点，然后将其指针域指向我们的新节点就好。代码如下：

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType n)
{
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(n);//创建新节点
    if (*pphead == NULL)//头指针为空说明链表为空
    {
        //链表为空，此时插入第一个元素，需要将头指针指向新节点，
        //而在函数内修改头指针就要传入头指针的地址，也就是二级指针
        *pphead = newnode;
    }
    else//链表不为空的情况
    {
        SLTNode* cur = *pphead;
        while (cur->next != NULL)//从头节点开始，循环遍历找到最后一个节点
        {
            cur = cur->next;
        }
        cur->next = newnode;//将新节点的地址赋值给最后一个节点的指针域
    }
}

这里需要注意：当链表为空时，如果我们进行循环遍历，就会发生对空指针解引用的错误，所以直接使头指针指向新节点就好。由于要在函数体内改变参数的值，并且参数是一个一级指针变量，所以要传入一级指针的地址，也就是二级指针。


3.2.4 头插

       对于头插操作，我们需要将新节点的next指向原来的第一个节点，然后将头指针指向新节点。


我们画图表示一下：



代码实现：

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType n)
{
    assert(pphead);//确保传入的不是空指针
    SLTNode* newnode = SLTBuyNode(n);//创建新节点
    newnode->next = *pphead;//使新节点的next指针指向原来的第一个节点
    *pphead = newnode;//头指针指向新节点
}

注意：最后两句代码的顺序不能颠倒，因为如果先让头指针指向新节点，原来的链表的地址就会丢失，无法访问到了。


3.2.5 尾删

       进行尾删操作时，我们也需要遍历链表，找到链表的末尾并释放内存。实际操作要做一些特殊情况和细节的处理：

//尾删
void SLTPopBack(SLTNode** pphead)
{
    assert(pphead && *pphead);//确保传入的不是空指针并且链表不为空
    if ((*pphead)->next = NULL)//链表只有一个节点的情况
    {
        free((*pphead)->next);//释放该节点的空间
        *pphead == NULL;//改变了头节点的值，所以也要传二级指针
    }
    else//节点大于1的情况
    {
        SLTNode* prev = *pphead;
        while (prev->next->next != NULL)//循环遍历，使prev指向倒数第二个节点
        {
            prev = prev->next;
        }
        free(prev->next);//释放最后一个节点的空间
        prev->next = NULL;//将此时的最后一个节点的next制为空
    }
}

3.2.6 头删

       对于头删操作，我们需要记录第二个节点，然后再将第一个节点释放，最后使头指针指向记录的节点即可。当链表只有一个节点时，我们记录的就是NULL，最后将NULL赋值给头指针也合情合理。无需分类讨论。

//头删
void SLTPopFront(SLTNode** pphead)
{
    assert(pphead && *pphead);
    SLTNode* next = (*pphead)->next;//保存第二个节点的地址/空指针（只有一个节点时）
    free(*pphead);//释放第一个节点的空间
    *pphead = next;//让头指针指向刚才保存的节点/空指针，也要传二级指针
}

3.2.7 查找

       查找操作十分简单，只需要遍历链表，如果有匹配的节点，将其地址返回即可。

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType n)
{
    SLTNode* cur = phead;
    while (cur != NULL)//遍历链表的所有节点
    {
        if (cur->data == n)//匹配成功，返回该节点的地址
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;//没有找到，返回空指针
}

3.2.8 指定位置之前插入

       进行指定位置之前插入时，要进行分类讨论：如果指定位置是头节点，则进行头插；其他情况遍历找到该节点的前驱节点prev，然后进行插入操作：



代码实现：

//指定位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType n)
{
    assert(pphead && pos);
    SLTNode* newnode = SLTBuyNode(n);
    if (*pphead == pos)//指定位置是头节点的情况
    {
        //进行头插
        newnode->next = *pphead;
        *pphead = newnode;
    }
    else
    {
        SLTNode* prev = *pphead;
        while (prev->next != pos)//遍历找到pos节点的前驱节点
        {
            prev = prev->next;
        }
        newnode->next = pos;//新节点的next指针指向pos
        prev->next = newnode;//前驱节点的next指针指向新节点
    }
}

3.2.9 指定位置之后插入

       对于指定位置之后插入元素，由于已经找到了前驱节点和后继节点，相比就没有那么麻烦了，只需要直接插入即可。



代码实现：

//指定位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType n)
{
    assert(pos);//确保pos不为空指针
    SLTNode* newnode = SLTBuyNode(n);
    newnode->next = pos->next;//newnode的next指向后继节点
    pos->next = newnode;//前驱节点的next指向newnode
}

3.2.10 删除指定位置的节点

       对于指定位置的删除，我们需要分类讨论：如果此位置是头节点，就进行头删；否则就要找到其前驱节点和后继节点，然后进行删除操作。



//删除指定位置节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && pos && *pphead);//确保传入的不是空指针并且链表不为空
    if (pos == *pphead)//指定位置是头节点情况
    {
        //头删
        *pphead = pos->next;//先使头指针指向第二个节点
        free(pos);//释放掉pos节点
    }
    else
    {
        SLTNode* prev = *pphead;
        while (prev->next != pos)//循环遍历，找到pos的前驱节点
        {
            prev = prev->next;
        }
        prev->next = pos->next;//使前驱节点的next指针指向pos的后继节点
        free(pos);//释放掉pos节点
    }
    pos = NULL;//对野指针及时制空
}

3.2.11 销毁链表

       当我们使用完链表之后，应当及时释放掉链表的所有节点内存，这个过程称之为销毁链表。代码如下：

//销毁链表
void SLTDestroy(SLTNode** pphead)
{
    assert(pphead);
    SLTNode* cur = *pphead;//从头节点开始遍历
    while (cur != NULL)
    {
        SLTNode* next = cur->next;//先记录下一个节点
        free(cur);//释放当前节点
        cur = next;//释放后，cur指向记录的节点
    }
    *pphead = NULL;//将头指针制空
}

4.程序全部代码

       程序全部代码如下：

#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* SLTBuyNode(SLTDataType n);
 
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType n);
 
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType n);
 
//尾删
void SLTPopBack(SLTNode** pphead);
 
//头删
void SLTPopFront(SLTNode** pphead);
 
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType n);
 
//指定位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType n);
 
//指定位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType n);
 
//删除指定位置节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
 
//销毁链表
void SLTDestroy(SLTNode** pphead);
 
//打印链表
void SLTPrint(SLTNode* phead)
{
    SLTNode* cur = phead;//定义指针指向头节点
    while (cur != NULL)//最后一个节点的next为空，cur等于空则说明遍历结束
    {
        printf("%d ", cur->data);//访问数据并打印
        cur = cur->next;//对cur解引用拿到下一个节点的地址，然后赋值给cur，cur就指向了下一个节点
    }
    printf("\n");
}
 
//创建新节点
SLTNode* SLTBuyNode(SLTDataType n)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//动态开辟一个节点大小的内存
    if (newnode == NULL)//内存开辟失败，则直接退出程序
    {
        perror("malloc");
        exit(1);
    }
    newnode->data = n;//将数据赋值给节点的数据域
    newnode->next = NULL;//为了确保链表末尾为空指针，所以创建的所有节点默认next为空
    return newnode;//将节点返回
}
 
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType n)
{
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(n);//创建新节点
    if (*pphead == NULL)//头指针为空说明链表为空
    {
        //链表为空，此时插入第一个元素，需要将头指针指向新节点，
        //而在函数内修改头指针就要传入头指针的地址，也就是二级指针
        *pphead = newnode;
    }
    else//链表不为空的情况
    {
        SLTNode* cur = *pphead;
        while (cur->next != NULL)//从头节点开始，循环遍历找到最后一个节点
        {
            cur = cur->next;
        }
        cur->next = newnode;//将新节点的地址赋值给最后一个节点的指针域
    }
}
 
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType n)
{
    assert(pphead);//确保传入的不是空指针
    SLTNode* newnode = SLTBuyNode(n);//创建新节点
    newnode->next = *pphead;//使新节点的next指针指向原来的第一个节点
    *pphead = newnode;//头指针指向新节点
}
 
//尾删
void SLTPopBack(SLTNode** pphead)
{
    assert(pphead && *pphead);//确保传入的不是空指针并且链表不为空
    if ((*pphead)->next = NULL)//链表只有一个节点的情况
    {
        free((*pphead)->next);//释放该节点的空间
        *pphead == NULL;//改变了头节点的值，所以也要传二级指针
    }
    else//节点大于1的情况
    {
        SLTNode* prev = *pphead;
        while (prev->next->next != NULL)//循环遍历，使prev指向倒数第二个节点
        {
            prev = prev->next;
        }
        free(prev->next);//释放最后一个节点的空间
        prev->next = NULL;//将此时的最后一个节点的next制为空
    }
}
 
//头删
void SLTPopFront(SLTNode** pphead)
{
    assert(pphead && *pphead);
    SLTNode* next = (*pphead)->next;//保存第二个节点的地址/空指针（只有一个节点时）
    free(*pphead);//释放第一个节点的空间
    *pphead = next;//让头指针指向刚才保存的节点/空指针，也要传二级指针
}
 
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType n)
{
    SLTNode* cur = phead;
    while (cur != NULL)//遍历链表的所有节点
    {
        if (cur->data == n)//匹配成功，返回该节点的地址
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;//没有找到，返回空指针
}
 
//指定位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType n)
{
    assert(pphead && pos);
    SLTNode* newnode = SLTBuyNode(n);
    if (*pphead == pos)//指定位置是头节点的情况
    {
        //进行头插
        newnode->next = *pphead;
        *pphead = newnode;
    }
    else
    {
        SLTNode* prev = *pphead;
        while (prev->next != pos)//遍历找到pos节点的前驱节点
        {
            prev = prev->next;
        }
        newnode->next = pos;//新节点的next指针指向pos
        prev->next = newnode;//前驱节点的next指针指向新节点
    }
}
 
//指定位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType n)
{
    assert(pos);//确保pos不为空指针
    SLTNode* newnode = SLTBuyNode(n);
    newnode->next = pos->next;//newnode的next指向后继节点
    pos->next = newnode;//前驱节点的next指向newnode
}
 
//删除指定位置节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && pos && *pphead);//确保传入的不是空指针并且链表不为空
    if (pos == *pphead)//指定位置是头节点情况
    {
        //头删
        *pphead = pos->next;//先使头指针指向第二个节点
        free(pos);//释放掉pos节点
    }
    else
    {
        SLTNode* prev = *pphead;
        while (prev->next != pos)//循环遍历，找到pos的前驱节点
        {
            prev = prev->next;
        }
        prev->next = pos->next;//使前驱节点的next指针指向pos的后继节点
        free(pos);//释放掉pos节点
    }
    pos = NULL;//对野指针及时制空
}
 
//销毁链表
void SLTDestroy(SLTNode** pphead)
{
    assert(pphead);
    SLTNode* cur = *pphead;//从头节点开始遍历
    while (cur != NULL)
    {
        SLTNode* next = cur->next;//先记录下一个节点
        free(cur);//释放当前节点
        cur = next;//释放后，cur指向记录的节点
    }
    *pphead = NULL;//将头指针制空
}

总结

       相比于顺序表，单链表采用了不同的物理结构，这使得头插、头删等操作的效率高于顺序表，并且插入一个数据就会创建一个节点，避免了空间的浪费。


      学习单链表是数据结构中相当重要的一个环节，学会了单链表，才会更容易地理解其他数据结构的底层逻辑。我们在学习数据结构时，要注意勤画图，勤调试，才能让我们的编程能力更上一层楼。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

文章标签：
C语言
存储
ephemerals__
目录
相关文章
弹性计算-百晓生
|
4天前
|
弹性计算 双11 开发者
阿里云ECS“99套餐”再升级！双11一站式满足全年算力需求
11月1日，阿里云弹性计算ECS双11活动全面开启，在延续火爆的云服务器“99套餐”外，CPU、GPU及容器等算力产品均迎来了全年最低价。同时，阿里云全新推出简捷版控制台ECS Lite及专属宝塔面板，大幅降低企业和开发者使用ECS云服务器门槛。
弹性计算-百晓生
87647 10
弹性计算-百晓生
|
21天前
|
存储 弹性计算 人工智能
阿里云弹性计算_通用计算专场精华概览 | 2024云栖大会回顾
阿里云弹性计算产品线、存储产品线产品负责人Alex Chen（陈起鲲）及团队内多位专家，和中国电子技术标准化研究院云计算标准负责人陈行、北京望石智慧科技有限公司首席架构师王晓满两位嘉宾，一同带来了题为《通用计算新品发布与行业实践》的专场Session。本次专场内容包括阿里云弹性计算全新发布的产品家族、阿里云第 9 代 ECS 企业级实例、CIPU 2.0技术解读、E-HPC+超算融合、倚天云原生算力解析等内容，并发布了国内首个云超算国家标准。
弹性计算-百晓生
101032 9
阿里云弹性计算_通用计算专场精华概览 | 2024云栖大会回顾
周周的奇妙编程
|
3天前
|
人工智能 弹性计算 文字识别
基于阿里云文档智能和RAG快速构建企业"第二大脑"
在数字化转型的背景下，企业面临海量文档管理的挑战。传统的文档管理方式效率低下，难以满足业务需求。阿里云推出的文档智能（Document Mind）与检索增强生成（RAG）技术，通过自动化解析和智能检索，极大地提升了文档管理的效率和信息利用的价值。本文介绍了如何利用阿里云的解决方案，快速构建企业专属的“第二大脑”，助力企业在竞争中占据优势。
周周的奇妙编程
4910 4
周周的奇妙编程
|
2天前
|
人工智能 自然语言处理 安全
创新不设限，灵码赋新能：通义灵码新功能深度评测
自从2023年通义灵码发布以来，这款基于阿里云通义大模型的AI编码助手迅速成为开发者心中的“明星产品”。它不仅为个人开发者提供强大支持，还帮助企业团队提升研发效率，推动软件开发行业的创新发展。本文将深入探讨通义灵码最新版本的三大新功能：@workspace、@terminal 和 #team docs，分享这些功能如何在实际工作中提高效率的具体案例。
周周的奇妙编程
2863 8
沃通WoTrus
|
8天前
|
负载均衡 算法 网络安全
阿里云WoSign SSL证书申请指南_沃通SSL技术文档
阿里云平台WoSign品牌SSL证书是由阿里云合作伙伴沃通CA提供，上线阿里云平台以来，成为阿里云平台热销的国产品牌证书产品，用户在阿里云平台https://www.aliyun.com/product/cas 可直接下单购买WoSign SSL证书，快捷部署到阿里云产品中。
沃通WoTrus
1852 6
阿里云WoSign SSL证书申请指南_沃通SSL技术文档
沃通WoTrus
|
11天前
|
Web App开发 算法 安全
什么是阿里云WoSign SSL证书？_沃通SSL技术文档
WoSign品牌SSL证书由阿里云平台SSL证书合作伙伴沃通CA提供，上线阿里云平台以来，成为阿里云平台热销的国产品牌证书产品。
沃通WoTrus
1791 2
石臻臻的杂货铺
|
20天前
|
编解码 Java 程序员
写代码还有专业的编程显示器？
写代码已经十个年头了, 一直都是习惯直接用一台Mac电脑写代码 偶尔接一个显示器, 但是可能因为公司配的显示器不怎么样, 还要接转接头 搞得桌面杂乱无章，分辨率也低，感觉屏幕还是Mac自带的看着舒服
石臻臻的杂货铺
3785 13
云大宝
|
27天前
|
存储 人工智能 缓存
AI助理直击要害，从繁复中提炼精华——使用CDN加速访问OSS存储的图片
本案例介绍如何利用AI助理快速实现OSS存储的图片接入CDN，以加速图片访问。通过AI助理提炼关键操作步骤，避免在复杂文档中寻找解决方案。主要步骤包括开通CDN、添加加速域名、配置CNAME等。实测显示，接入CDN后图片加载时间显著缩短，验证了加速效果。此方法大幅提高了操作效率，降低了学习成本。
云大宝
5392 15
探索云世界
|
14天前
|
人工智能 关系型数据库 Serverless
1024，致开发者们——希望和你一起用技术人独有的方式，庆祝你的主场
阿里云开发者社区推出“1024·云上见”程序员节专题活动，包括云上实操、开发者测评和征文三个分会场，提供14个实操活动、3个解决方案、3 个产品方案的测评及征文比赛，旨在帮助开发者提升技能、分享经验，共筑技术梦想。
探索云世界
1155 152
绿水长流*z
|
22天前
|
存储 缓存 关系型数据库
MySQL事务日志-Redo Log工作原理分析
事务的隔离性和原子性分别通过锁和事务日志实现，而持久性则依赖于事务日志中的`Redo Log`。在MySQL中，`Redo Log`确保已提交事务的数据能持久保存，即使系统崩溃也能通过重做日志恢复数据。其工作原理是记录数据在内存中的更改，待事务提交时写入磁盘。此外，`Redo Log`采用简单的物理日志格式和高效的顺序IO，确保快速提交。通过不同的落盘策略，可在性能和安全性之间做出权衡。
绿水长流*z
1585 14