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

简介: 本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的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;//将头指针制空
}

总结

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


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

相关文章
|
14天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
13天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
56 16
|
8天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
49 8
|
8天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
36 7
|
6天前
|
C语言 Windows
C语言课设项目之2048游戏源码
C语言课设项目之2048游戏源码,可作为课程设计项目参考,代码有详细的注释,另外编译可运行文件也已经打包,windows电脑双击即可运行效果
18 1
|
13天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
62 8
|
15天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
35 0
|
存储 缓存 C语言
数据结构——双链表(C语言)
数据结构——双链表(C语言)
|
5月前
|
存储
数据结构——双向链表(C语言版)
数据结构——双向链表(C语言版)
31 2
|
5月前
|
算法 C语言
数据结构——单向链表(C语言版)
数据结构——单向链表(C语言版)
45 2