导航：首页 > 开发技术 >

C++如何实现单链表

发表于：2025-02-02 作者：千家信息网编辑

千家信息网最后更新 2025年02月02日，小编给大家分享一下C++如何实现单链表，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！单链表的实现(从入门到熟练)概念和结构

千家信息网最后更新 2025年02月02日C++如何实现单链表

小编给大家分享一下C++如何实现单链表，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

单链表的实现(从入门到熟练)

概念和结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构

数据元素的逻辑顺序是通过链表中的指针链接次序实现的

图示：

注意：

链表结构在逻辑上为连续的，但是物理上（内存中）不一定连续

链表节点都是在堆上申请出来的，申请空间按一定策略分配

结构种类

链表具有多种结构：单向\双向，带头\不带头，循环\非循环

实际上最常用的是：无头单向非循环链表，带头双向循环链表

链表的实现

注意：这里实现的是无头单向非循环链表

增删查改接口

// 动态申请一个节点SListNode* BuySListNode(SLTDateType x);// 单链表打印void SListPrint(SListNode* plist);// 单链表尾插void SListPushBack(SListNode** pplist, SLTDateType x);// 单链表的头插void SListPushFront(SListNode** pplist, SLTDateType x);// 单链表的尾删void SListPopBack(SListNode** pplist);// 单链表头删void SListPopFront(SListNode** pplist);// 单链表查找SListNode* SListFind(SListNode* plist, SLTDateType x);// 单链表在pos位置之后插入xvoid SListInsertAfter(SListNode* pos, SLTDateType x);// 单链表删除pos位置之后的值void SListEraseAfter(SListNode* pos);

节点结构体创建

typedef int SLTDateType;typedef struct SListNode{ SLTDateType data; struct SListNode* next; }SListNode;

节点开辟

对于链表来说，每需要空间就需要进行开辟，这里我们将之封装成一个函数，便于后续调用直接使用（开辟的同时进行赋值）

参考代码：

//链表节点开辟SLTNode* BuySListNode(SLTDateType x){        //动态分配一个节点        SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));        if (newnode == NULL)        {                //分配失败则打印错误信息并结束进程                perror("newnode fail:");                exit(-1);        }        //成功则进行赋值        newnode->data = x;        newnode->next = NULL;        //返回节点地址，以便后续操作        return newnode;}

数据打印

注意：

1.对于不带头的链表来说，打印数据不需要修改链表首节点地址（故只要传链表指针）

2.用循环遍历链表，每打印数据，需要指向下一个节点

3.依靠尾节点的址域为NULL来结束循环

代码：

//链表数据打印void SListPrint(SLTNode* phead)//一级指针接收一级指针（打印不需改变指针本身内容）{        //创建一个寻址指针        SLTNode* cur = phead;        while (cur!=NULL)//后续还有节点        {                //打印数据并指向下一个节点                printf("%d->", cur->data);                cur = cur->next;        }        //最后打印空指针        printf("NULL\n");        return;}

链表尾插数据

要尾插数据则需要遍历找到链表的尾节点
对于不带头链表，尾插数据也可能是插在链表首元素的地址（当链表为空），需要修改链表指针的内容（故需要传入链表指针的地址）
插入数据要开辟节点

代码：

//链表尾插数据void SListPushBack(SLTNode** pphead, SLTDateType x)//二级指针接收一级指针（尾插存在需改变链表指针本身内容）{        //避免传入错误(直接报错便于找到错误位置)        assert(pphead);        //接收新节点的地址        SLTNode* newnode=BuySListNode(x);        //头节点为空        if (*pphead == NULL)        {                *pphead = newnode;        }        else        {                //找尾节点                SLTNode* tail = *pphead;//创建寻址节点                //两个及以上节点的情况                while (tail->next != NULL)                {                        //指向下一个节点                        tail = tail->next;                 }                //找到了                tail->next = newnode;        }        return;}

注意代码中的assert的作用：

正确传入链表指针的地址是不会为空的
但是对于非正常传入链表指针（不是链表指针的地址）且此时链表指针为空则会发生报错（assert报错会告诉错误位置），告诉程序员应该传入链表指针的地址

头删

注意：

删除前需要保存当前节点的址域（即保存下个节点的空间地址，以防丢失）
前删数据即删除当前链表首节点，即需修改链表指针的内容（故需传入链表指针的地址）
删除后修改链表指针内容，指向新的首节点
如果链表为空时无法删除（保存下个节点地址会造成非法访问）

代码：

//链表前删数据void SListPopFront(SLTNode** pphead){        //避免传入错误(直接报错便于找到错误位置)        assert(pphead);        //链表为空的情况        if (*pphead == NULL)        {                return;        }        //创建指针保存第二个节点地址        SLTNode* next = (*pphead)->next;        //释放当前头结点空间        free(*pphead);        //更新头结点数据        *pphead = next;        return;}

链表数据查找

注意：

查找时用循环遍历链表
对于查找数据不用修改链表指针的内容，故只需传入链表指针就行了
查找到时则返回节点地址，否则返回NULL

代码：

//链表数据查找SLTNode* SListFind(SLTNode* phead, SLTDateType x){        //创建寻址指针        SLTNode* cur = phead;        while (cur!=NULL)        {                if (cur->data == x)//找到数据符合节点                {                        return cur;//返回节点地址（好处：以便后续再寻找或修改）                }                else                {                        //找下一个节点                        cur = cur->next;                }        }        //未找到数据符合节点        return NULL;}

链表pos位置前插数据

注意：

想要pos位置前插数据，不仅需要找到pos位置，还需要记录pos的前一个节点位置
传入的pos为NULL则报错
进行修改前节点的址域成新节点，并让新节点的址域修改成pos，这才是一个成功的pos位置前插数据
循环遍历链表查找pos位置，没有找到pos位置则什么也不干

代码：

//链表pos位置往前插入(较难)（还有在pos位置之后插入，简单点）void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x){        //避免传入错误(直接报错便于找到错误位置)        assert(pphead);        assert(pos);        SLTNode* newnode = BuySListNode(x);        //首结点符合的情况        if (*pphead == pos)        {                newnode->next = *pphead;                *pphead = newnode;        }        else        {                //创建寻址指针                SLTNode* cur = *pphead;                while (cur !=NULL)                {                        if (cur->next!= pos)                        {                                cur = cur->next;//找到下一节点                        }                        else // 找到对应空间                        {                                cur->next = newnode;                                newnode->next = pos;                                return;//结束寻找（否则会一直插入，造成死循环）                        }                }        }        //未找到则什么也不干        return;}

链表pos位置后插数据

注意：

后插则不用关注是否为首节点
也不用找到遍历找到前节点的位置
后插则先将新节点址域改成pos后节点地址再将pos的址域改成新节点地址

ps:一定要注意修改链接节点址域的先后，避免地址的丢失

代码：

//链表pos位置往后插入void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x){        SLTNode* newnode = BuySListNode(x);        newnode->next = pos->next;        pos->next = newnode;        return;}

链表pos位置数据删除

注意：

考虑删除首节点的情况，可能修改链表指针的内容，故需要传入链表指针的地址
对于删除节点，需要先保存pos位置下一个节点地址，将pos位置释放，再将pos位置前节点的址域改成pos位置后节点的地址，这才是成功的删除pos位置节点
循环找pos位置，没找到则什么也不干

参考代码:

//链表pos位置删除void SListErase(SLTNode** pphead, SLTNode* pos){        //避免传入错误(直接报错便于找到错误位置)        assert(pphead);        assert(pos);        //头结点符合的情况        if (*pphead == pos)        {                *pphead = (*pphead)->next;                free(pos);        }        else        {                //创建寻址指针                SLTNode* cur = *pphead;                while (cur != NULL)                {                        if (cur->next != pos)                        {                                cur = cur->next;//找到下一节点                        }                        else // 找到对应空间                        {                                SLTNode* next = cur->next->next;                                free(cur->next);                                cur->next = next;                                return;//结束寻找                        }                }        }        //未找到则什么也不干        return;}

链表节点释放

注意:

对于动态开辟的内存空间，在使用后一定要记得的进行释放（避免造成内存泄漏）
因为链表节点是一个个开辟的，同样的释放也需要一个个进行释放
循环遍历释放当前节点前需保存后一个节点的地址，避免地址丢失无法释放
释放完后，还需将链表指针给置空（避免使用野指针）

参考代码:

//链表节点释放void SListDestory(SLTNode** pphead){        //避免传入错误(直接报错便于找到错误位置)        assert(pphead);        //遍历释放        SLTNode* cur = *pphead;        while (cur)        {                //保存下一个地址                SLTNode* next = cur->next;                free(cur);                cur = next;        }        //置空        *pphead = NULL;        return;}