数据结构之链表（1），单链表

前言

    本文讲述了什么是链表，以及实现了完整的单链表。

❤️感谢支持，点赞关注不迷路❤️

一、什么是链表

1.概念

概念：链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

简单来说，链表属于线性表的一种，在逻辑结构上是连续的，物理结构上不一定是连续的，通过指针连接。

2.节点

与顺序表不同的是，链表里的每个节点都是独立申请下来的空间，我们称之为“结点/结点”

结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。也可以说成数据域和指针域两部分

特点：链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点位置，才能从当前结点找到下⼀个结点。

3.链表的性质

链式结构在逻辑上是连续的，在物理结构上不⼀定连续
结点一般是从堆上申请的
从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

4.与顺序表的对比

顺序表的中间/头部插入删除数据的时间复杂度为O(n)，而链表相同功能时间复杂度为O(1)
顺序表增容需要申请请新空间，拷贝数据，释放旧空间。会有不小的消耗。链表每次申请一个节点，不存在拷贝，释放旧空间。
顺序表增容一般是呈2倍的增长，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。链表不存在空间浪费

以上是链表相对与顺序表的优点，但不代表顺序表一定不如链表，顺序表在有些场景下效率还是非常高，因此选择使用什么数据结构是看场景的要求

二、链表的分类

链表的结构非常多样，有带头不带头，单向或者双向，循环不循环，这三种属性情况组合起来就有8种（2x2x2）链表结构：

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表：

无头单向非循环链表（单链表）：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现该结构会带来很多优势，后面我们代码实现了就知道了。

本文主要讲述单链表

三、单链表

单链表的结构如下图：

单链表的结构声明：

typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;//节点数据
struct SListNode* next;//指向下一节点的指针变量
}SLTNode;

以下单链表同样由3个文件组成：

SList.h：单链表的结构声明，各种函数声明
SList.c：用于函数的具体实现
test.c：用于测试单链表（自行测试）

四、单链表的实现

1.SList.h文件

以下是该文件中的代码：

#pragma once
#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);

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//尾删
void SLTPopBack(SLTNode** pphead);

//头删
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除指定位置pos的数据
void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除pos之后的数据
void SLTEraseAfter(SLTNode* pos);

//销毁链表
void SListDestroy(SLTNode** pphead);

2.SList.c文件

1.SLTPrint函数

//打印
void SLTPrint(SLTNode* phead)
{
    SLTNode* pcur = phead;

    //循环打印
    while (pcur)
    {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }

    printf("NULL\n");
}

解析：该函数用于打印链表数据，使用一个pcur指针，只要不为空指针，就循环遍历下一个节点

2.SLTBuyNode函数

//申请节点
SLTNode* SLTBuyNode(SLTDataType x)
{
    //申请一个节点
    SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
    if (node == NULL)
    {
        perror("malloc fail!");
        exit(1);
    }

    //赋值
    node->data = x;
    node->next = NULL;

    return node;
}

解析：

该函数用于申请新节点，一个参数，其为新节点存储的数据
使用malloc函数申请，申请成功后将其数据域赋值为参数值，指针域赋值为空指针NULL
因为该函数主要为其他功能函数服务，因此只需写在 SList.c 文件中即可，无需在头文件SList.h 中声明

3.SLTPushBack函数

//尾插
//因为要修改plist本身，因此需要二级指针来接收
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
    //断言pphead不能为空指针
    assert(pphead);
    //申请新节点
    SLTNode* newnode = SLTBuyNode(x);

    //如果pphead指向的第一个节点就是空指针
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        //找尾结点
        SLTNode* pcur = *pphead;
        while (pcur->next)
        {
            pcur = pcur->next;
        }
        pcur->next = newnode;
    }
}

解析：

该函数功能为：在链表尾部插入一个数据。因此需要链表的头部指针和需要插入的数据x
为什么头节点参数是二级指针？答：因为需要修改原指针变量本身，我们知道函数传参分为传值传参和传址传参（&），想要修改原变量内容就需要传址传参，而这里原变量就是一个指向链表头节点的指针变量，因此原变量通过&传参，就需要二级指针来接收一级指针变量的地址。所以这里就是用二级指针，下面其他的函数同理。
申请完新节点，插入到链表尾部时要分2种情况，1链表为空，2链表不为空。
链表为空则直接将新节点插入链表即可，也就是将指向头结点的指针指向新节点。链表不为空就需要寻找尾结点，尾节点的特点就是next指针指向空。循环之后将尾节点的next指针修改为新节点即可。

4.SLTPushFront函数

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);

    //直接申请节点，然后修改新节点指向即可
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = *pphead;

    *pphead = newnode;
}

解析：

功能：在链表头部插入一个新节点。参数同样是一个二级指针和新节点的数据
头插比较简单，只需将新申请的节点的 next 指针指向链表头结点，然后让指向链表头结点的指针指向新节点即可。

5.SLTPopBack函数

//尾删
void SLTPopBack(SLTNode** pphead)
{
    assert(pphead && *pphead);

    //只有一个节点的情况
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        //两个及以上节点的情况
        //申请两个节点用于指向尾节点和倒数第二个节点
        SLTNode* ptail = *pphead;
        SLTNode* prev = NULL;

        while (ptail->next)
        {
            prev = ptail;
            ptail = ptail->next;
        }
        
        //销毁尾结点，然后让倒数第二个节点next指向空
        free(ptail);
        ptail = NULL;
        prev->next = NULL;
    }
}

解析：

功能：删除链表的最后一个节点，参数为一个二级指针
首先断言，不能传空指针并且链表不能为空
尾删也要分两种情况，因为如果只要一个节点，那么就不需要找倒数第二个节点。所以分为链表只有一个节点的情况和有多个节点的情况
只有一个节点，那么我们直接 free 掉该节点，然后让指向头结点的指针置空。多个节点，那么我们就需要找到最后一个节点 ptail 以及倒数第二个节点 prev，使用while循环即可，只要ptail 的下一个节点为空就跳出循环，此时 prev 为倒数第二个节点，然后释放掉最后一个节点，修改倒数第二个节点的next指针即可。

6.SLTPopFront函数

//头删
void SLTPopFront(SLTNode** pphead)
{
    assert(pphead && *pphead);

    SLTNode* next = (*pphead)->next;

    free(*pphead);

    *pphead = next;
}

解析：

功能：删除链表的头部节点
因为参数 *pphead 就是指向链表的头结点，因此删除简单，先创建一个next指针保存头结点的下一个节点，然后释放掉头节点，更改 *pphead 的指向即可

7.SLTFind函数

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
    assert(phead);

    SLTNode* pcur = phead;

    while (pcur)
    {
        //找到了
        if (pcur->data == x)
        {
            return pcur;
        }
        pcur = pcur->next;
    }

    //没找到
    return NULL;
}

解析：

功能：查找数据为 x 的节点，返回该节点的地址。
因为查找操作不会影响头指针 phead，因此参数为一级指针即可
查找很简单，循环遍历链表，让 pcur 一直往后走，直到找到存储 x 的节点，返回该节点，没找到就返回空指针

8.SLTInsert函数

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pphead);
    assert(pos);

    //如果指定位置是头结点
    if (*pphead == pos)
    {
        //头插
        SLTPushFront(pphead, x);
    }
    else
    {
        //新节点
        SLTNode* newnode = SLTBuyNode(x);
        //prev用于找到pos前一个节点
        SLTNode* prev = *pphead;

        while (prev->next != pos)
        {
            prev = prev->next;
        }

        prev->next = newnode;
        newnode->next = pos;
    }
}

解析：

功能：在指定位置之前插入数据，参数为头指针地址、指定位置（用SLTFind函数确定）、需插入的数据x。
首先断言，头指针和pos指针都不能为空，也就是链表不能为空
然后，也分两种情况，因为如果指定位置刚好是头结点，那么只需要使用头插函数即可。如果指定位置不是头结点，我们就需要找到 pos 指向的结点的前一个节点。定义一个指针变量 prev，让它从头往后找，只要它的 next 指针不是 pos，那么就继续往下个节点走，直到找到pos的前一个节点。
找到之后，让 prev 的 next 指针指向新节点，再让新节点的 next 指针指向pos就完成了在指定位置前插入数据。

7.SLTInsertAfter函数

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);

    SLTNode* newnode = SLTBuyNode(x);
    //先让newnode的next指向下一个节点
    newnode->next = pos->next;
    //再修改pos的next指针
    pos->next = newnode;
}

解析：

功能：在指定位置之后插入数据。
因为受影响的节点只有pos指向的节点，所以只需要传pos指针和需要增加的数据 x 即可。
pos指针使用SLTFind函数指定即可
实现简单，注意顺序即可，将新节点的next指针指向pos节点的下一个节点，然后让pos指针的next指针指向新节点即可。

8.SLTErase函数

//删除指定位置pos的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && *pphead);
    assert(pos);

    //如果pos位置是第一个位置
    if (*pphead == pos)
    {
        //头删
        SLTPopFront(pphead);
    }
    else
    {
        //找到pos前一个节点
        SLTNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }

        //释放
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

解析：

功能：删除指定位置的节点。
参数需用到头节点和pos指向节点
也要分两种情况，因为如果需删除节点刚好是头结点，直接头删即可，如果不是头结点，则需要找到指定位置的前一个节点，老套路，找到之后，先修改 prev 的next指针，然后释放pos指向的节点。

9.SLTEraseAfter函数

//删除pos之后的数据
void SLTEraseAfter(SLTNode* pos)
{
    assert(pos && pos->next);

    SLTNode* del = pos->next;

    //让pos指向它之后的之后的数据
    pos->next = pos->next->next;

    free(del);
    del = NULL;
}

解析：

功能：删除pos位置后一个节点
只需要pos指针即可
实现简单，先保存需删除的节点地址，然后改变pos的next指针指向，最后释放掉 del 即可。

10.SListDestroy函数

//销毁链表
void SListDestroy(SLTNode** pphead)
{
    assert(pphead && *pphead);
    SLTNode* pcur = *pphead;

    //循环销毁链表
    while (pcur)
    {
        SLTNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }

    //记得将头指针指置空
    *pphead = NULL;
}

解析：

功能：销毁整个链表
断言确保链表不为空
创建pcur循环遍历链表，只要pcur不为空，释放该空间。
最后记得将头指针置空

五、SList.c文件完整代码

#include "SList.h"

//打印
void SLTPrint(SLTNode* phead)
{
    SLTNode* pcur = phead;

    //循环打印
    while (pcur)
    {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }

    printf("NULL\n");
}

//申请节点
SLTNode* SLTBuyNode(SLTDataType x)
{
    //申请一个节点
    SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
    if (node == NULL)
    {
        perror("malloc fail!");
        exit(1);
    }

    //赋值
    node->data = x;
    node->next = NULL;

    return node;
}

//尾插
//因为要修改plist本身，因此需要二级指针来接收
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
    //断言pphead不能为空指针
    assert(pphead);
    //申请新节点
    SLTNode* newnode = SLTBuyNode(x);

    //如果pphead指向的第一个节点就是空指针
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        //找尾结点
        SLTNode* pcur = *pphead;
        while (pcur->next)
        {
            pcur = pcur->next;
        }
        pcur->next = newnode;
    }
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);

    //直接申请节点，然后修改新节点指向即可
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = *pphead;

    *pphead = newnode;
}

//尾删
void SLTPopBack(SLTNode** pphead)
{
    assert(pphead && *pphead);

    //只有一个节点的情况
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        //两个及以上节点的情况
        //申请两个节点用于指向尾节点和倒数第二个节点
        SLTNode* ptail = *pphead;
        SLTNode* prev = NULL;

        while (ptail->next)
        {
            prev = ptail;
            ptail = ptail->next;
        }
        
        //销毁尾结点，然后让倒数第二个节点next指向空
        free(ptail);
        ptail = NULL;
        prev->next = NULL;
    }
}

//头删
void SLTPopFront(SLTNode** pphead)
{
    assert(pphead && *pphead);

    SLTNode* next = (*pphead)->next;

    free(*pphead);

    *pphead = next;
}

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
    assert(phead);

    SLTNode* pcur = phead;

    while (pcur)
    {
        //找到了
        if (pcur->data == x)
        {
            return pcur;
        }
        pcur = pcur->next;
    }

    //没找到
    return NULL;
}

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pphead);
    assert(pos);

    //如果指定位置是头结点
    if (*pphead == pos)
    {
        //头插
        SLTPushFront(pphead, x);
    }
    else
    {
        //新节点
        SLTNode* newnode = SLTBuyNode(x);
        //prev用于找到pos前一个节点
        SLTNode* prev = *pphead;

        while (prev->next != pos)
        {
            prev = prev->next;
        }

        prev->next = newnode;
        newnode->next = pos;
    }
}

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);

    SLTNode* newnode = SLTBuyNode(x);
    //先让newnode的next指向下一个节点
    newnode->next = pos->next;
    //再修改pos的next指针
    pos->next = newnode;
}

//删除指定位置pos的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && *pphead);
    assert(pos);

    //如果pos位置是第一个位置
    if (*pphead == pos)
    {
        //头删
        SLTPopFront(pphead);
    }
    else
    {
        //找到pos前一个节点
        SLTNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }

        //释放
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

//删除pos之后的数据
void SLTEraseAfter(SLTNode* pos)
{
    assert(pos && pos->next);

    SLTNode* del = pos->next;

    //让pos指向它之后的之后的数据
    pos->next = pos->next->next;

    free(del);
    del = NULL;
}

//销毁链表
void SListDestroy(SLTNode** pphead)
{
    assert(pphead && *pphead);
    SLTNode* pcur = *pphead;

    //循环销毁链表
    while (pcur)
    {
        SLTNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }

    //记得将头指针指置空
    *pphead = NULL;
}

六、使用演示

不完全演示：

#include "SList.h"

void SListTest1()
{
    //指针要初始化为空
    SLTNode* plist = NULL;
    
    //尾插
    SLTPushBack(&plist, 1);
    SLTPushBack(&plist, 2);
    SLTPushBack(&plist, 3);
    SLTPushBack(&plist, 4);
    SLTPushBack(&plist, 5);
    printf("尾插：");
    SLTPrint(plist);

    //头插
    SLTPushFront(&plist, 11);
    SLTPushFront(&plist, 12);
    SLTPushFront(&plist, 13);
    SLTPushFront(&plist, 14);
    SLTPushFront(&plist, 15);
    printf("头插：");
    SLTPrint(plist);

    //尾删
    SLTPopBack(&plist);
    printf("尾删：");
    SLTPrint(plist);

    //头删
    SLTPopFront(&plist);
    printf("头删：");
    SLTPrint(plist);

    //指定位置之前插入数据
    SLTInsert(&plist, SLTFind(plist, 2), 66);
    printf("在2的前面插入66：");
    SLTPrint(plist);

    //删除指定位置数据
    SLTErase(&plist, SLTFind(plist, 66));
    printf("删除66：");
    SLTPrint(plist);

    //销毁链表
    SListDestroy(&plist);
    printf("销毁：");
    SLTPrint(plist);
}

int main()
{
    SListTest1();

    return 0;
}

运行结果：

总结

    以上就是本文的全部内容，感谢支持。

标签：数据结构 c语言链表

本文转载自: https://blog.csdn.net/x_p96484685433/article/details/142557783
版权归原作者 进击的_鹏 所有，如有侵权，请联系我们删除。

数据结构之链表（1），单链表

前言

一、什么是链表

1.概念

2.节点

3.链表的性质

4.与顺序表的对比

二、链表的分类

三、单链表

四、单链表的实现

1.SList.h文件

2.SList.c文件

1.SLTPrint函数

2.SLTBuyNode函数

3.SLTPushBack函数

4.SLTPushFront函数

5.SLTPopBack函数

6.SLTPopFront函数

7.SLTFind函数

8.SLTInsert函数

7.SLTInsertAfter函数

8.SLTErase函数

9.SLTEraseAfter函数

10.SListDestroy函数

五、SList.c文件完整代码

六、使用演示

总结

发表评论

“数据结构之链表（1），单链表”的评论:

关于作者

overfit同步小助手

相关阅读

文章导航