AI 助理
备案控制台
开发者社区 大数据 文章 正文

【数据结构】单链表

2024-07-08 17
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构中的单链表

​

1. 链表的概念及结构

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

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：一个是存放数据元素的数据域，另一个是存储下一个结点地址的指针域。
image.png

注意:
（1）从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续。
（2）现实中的结点一般都是从堆上申请出来的。
（3）从堆上申请的空间，是按照一定的策略来分配的， 两次申请的空间可能连续，也可能不连续。

假设在32位系统上,结点中值域为int类型，则一个结点的大小为8个字节，则也可能有下述链表：
image.png

2. 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

2.1 单向或者双向

image.png

2.2 带头或者不带头（哨兵位）

image.png

2.3 循环或非循环

image.png

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

  1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等等。

  2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构带来很多优势，实现反而简单了。

3. 单链表的定义

typedef int SLTDataType;

typedef struct SListNode
{
   
   
    SLTDataType data;
    struct SListNode* next;  //存放下一个结点的地址
}SLTNode;

使用结构体创建一个单链表。

用SLTDataType替换int，方便对不同类型的数据进行修改。

用SLTNode替换struct SListNode，方便简洁。

data是结点的数据域，*next是结点的指针域。

4. 单链表的接口实现

单链表的所有接口函数一览：

//动态申请一个新结点
SLTNode* BuySListNode(SLTDataType x);
//打印单链表
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);

//在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置
void SLTErase(SLTNode** phead, SLTNode* pos);
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);
//销毁单链表
void SLTDestroy(SLTNode** pphead);

这些接口函数主要实现了单链表的增删改查等功能，接下来我们一一实现这些函数！

4.1 动态申请一个新结点

我们每次给链表插入数据时，都需要动态开辟空间申请结点。所以我们将这个过程封装成函数，方便后续使用。

我们使用malloc()函数动态开辟一块空间表示新结点newnode，malloc函数返回一个void*类型的指针，指向分配的内存块的起始位置。如果内存分配失败，则返回一个空指针NULL。

所以我们要判断newnode是否为空指针NULL，如果newnode是空指针，则用perror()函数打印相关错误，并用exit(-1)退出程序。

如果newnode不为空，我们就用newnode的data赋值。又因为这是新开辟的结点，我们暂时将newnode的next指向空。

//动态申请一个新结点
SLTNode* BuySListNode(SLTDataType x)
{
   
   
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
   
   
        perror("malloc failed");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

4.2 打印单链表

遍历单链表，依次打印单链表的元素。

我们定义一个结构体类型的指针cur，让cur一开始指向头结点。当cur不为空时，输出cur指向的结点的值（cur->data），然后让cur指向下一个结点（cur=cur->next），依次进行，直到cur为空指针时停止。

//打印单链表
void SLTPrint(SLTNode* phead)
{
   
   
    SLTNode* cur = phead;
    while (cur != NULL)
    {
   
   
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

4.3 尾插数据

尾插，就是要先找到单链表的尾结点，然后将数据插入到这个结点之后。

我们要先判断原链表是否为空，如果为空。我们就直接将链表的头指针指向要插入的数据。

（因为我们要改变链表的头指针，也就是要改变结构体的指针，所以我们要使用二级指针）。
image.png

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType 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;
    }
}

4.4 头插数据

头插，只需要申请新结点，然后让新结点的next指向链表的头，再让新结点成为链表的头即可。

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
   
   
    assert(pphead);
    SLTNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

4.5 尾删数据

尾删，就是将最后一个结点的空间释放。并让倒数第二个结点指向NULL。

也就是我们需要知道链表的倒数第二个结点，这里我们使用了一个结构体指针tail用于遍历找到尾结点，还有一个结构体指针tailPrev，用于保存遍历时当前的结点。

通过while(tail->next!=NULL)让tail进行遍历找到尾结点，此时tailPrev保存的就是倒数第二个结点。

但是我们要注意两个特殊情况：

1. 如果链表原本为空，那么就不能进行尾删，需要使用assert()进行断言。

2. 如果链表只有一个结点，我们直接将这个结点释放，并且将头结点置空。
image.png

//尾删
void SLTPopBack(SLTNode** pphead)
{
   
   
    assert(pphead);
    //1、空
    assert(*pphead);

    //2、一个节点
    //3、一个以上节点
    if ((*pphead)->next == NULL)
    {
   
   
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
   
   
        SLTNode* tailPrev = *pphead;
        SLTNode* tail = *pphead;
        while (tail->next != NULL)
        {
   
   
            tailPrev = tail;
            tail = tail->next;
        }
        free(tail);
        tailPrev->next = NULL;
    }
}

else中的代码也可以写成如下：

SLTNode* tail = *pphead;
while (tail->next->next)
{
   
   
    tail = tail->next;
}
free(tail->next);
tail->next = NULL;

4.6 头删数据

头删就是将第一个结点释放，然后让头指针指向原先第二个头结点。

我们这里引入一个指针变量newhead，用SLTNode newhead=(pphead)->next存原先第二个结点，等free()释放完第一个结点后，让头指针指向newhead。

需要注意的是，和尾删一样。如果链表原本为空，那么就不能进行头删，需要使用assert()进行断言。
image.png

//头删
void SLTPopFront(SLTNode** pphead)
{
   
   
    assert(pphead);
    //空
    assert(*pphead);
    //非空
    SLTNode* newhead = (*pphead)->next;
    free(*pphead);
    *pphead = newhead;
}

4.7 查找指定数据

定义一个结构体指针cur来遍历链表，先将cur指向头结点，如果链表某个结点的值和要查找的数据相等（cur->data==x）就返回cur，否则使用cur=cur->next继续遍历查找。

如果遍历完链表也没有找到，返回空指针NULL。

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
   
   
    SLTNode* cur = phead;
    while (cur)
    {
   
   
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

4.8 在指定位置之前插入数据

在指定位置pos前插入数据，就需要遍历链表找到pos的前一个位置，我们用结构体指针posPrev存pos位置的前一个位置。 同时创建一个新结点newnode，让posPrev的next指向newnode,而newnode的next指向pos。

这里也需要注意：

（1）既然是在pos位置之前插入数据，那么pos得是存在的，也就是pos不能为空。

（2）如果pos正好是头结点，相当于进行头插，我们可以复用之前头插操作的代码。
image.png

//在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
   
   
    assert(pphead);
    assert(pos);
    if (pos == *pphead)
    {
   
   
        SLTPushFront(pphead, x);
    }
    else
    {
   
   
        SLTNode* posPrev = *pphead;
        while (posPrev->next != pos)
        {
   
   
            posPrev = posPrev->next;
        }
        SLTNode* newnode = BuySListNode(x);
        posPrev->next = newnode;
        newnode->next = pos;
    }
}

4.9 在指定位置之后插入数据

在指定位置pos之后插入数据比较简单，不需要遍历链表。直接创建一个新结点，让新结点的next指向pos的next，再让pos的next指向newnode即可。
image.png

//在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
   
   
    assert(pos);
    SLTNode* newnode = BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

4.10 删除指定位置

删除指定的结点pos，也需要遍历链表。同时用结构体指针posPrev保存pos的前一个结点，然后将posPrev的next指向pos的next。

这里也需要注意：

（1）既然是删除指定位置pos，那么pos得是存在的，也就是pos不能为空。

（2）如果pos正好是头结点，相当于进行头删，我们可以复用之前头删操作的代码。
image.png

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
   
   
    assert(pphead);
    assert(pos);
    if (pos == *pphead)
    {
   
   
        SLTPopFront(pphead);
    }
    else
    {
   
   
        SLTNode* posPrev = *pphead;
        while (posPrev->next != pos)
        {
   
   
            posPrev = posPrev->next;
        }
        posPrev->next = pos->next;
        free(pos);
    }
}

4.11 删除指定位置的后一个位置

删除指定位置的后一个位置比较简单，不需要遍历链表。只需要定义一个结构体指针posNext用于保存指定位置pos的后一个位置，然后将pos的next指向posNext的next，再用free()释放posNext，最后将posNext置空即可。

需要注意的是，这里我们也需要用assert（）断言，当pos为空时断言。

如果pos为尾节点时也需要断言。
image.png

//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
   
   
    assert(pos);
    //检查pos是否是尾节点
    assert(pos->next);

    SLTNode* posNext = pos->next;
    pos->next = posNext->next;
    free(posNext);
    posNext = NULL;
}

4.12 销毁单链表

销毁链表，就是将所有结点所占的内存释放，最后将头指针置空。

//销毁单链表
void SLTDestroy(SLTNode** pphead)
{
   
   
    assert(pphead);
    SLTNode* cur = *pphead;
    while (cur)
    {
   
   
        SLTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    *pphead = NULL;
}

5. 单链表的完整代码

5.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;

//动态申请一个新结点
SLTNode* BuySListNode(SLTDataType x);
//打印单链表
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);

//在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置
void SLTErase(SLTNode** phead, SLTNode* pos);
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);
//销毁单链表
void SLTDestroy(SLTNode** pphead);

5.2 SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

//动态申请一个新结点
SLTNode* BuySListNode(SLTDataType x)
{
   
   
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
   
   
        perror("malloc failed");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

//打印单链表
void SLTPrint(SLTNode* phead)
{
   
   
    SLTNode* cur = phead;
    while (cur != NULL)
    {
   
   
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType 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;
    }
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
   
   
    assert(pphead);
    SLTNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

//尾删
void SLTPopBack(SLTNode** pphead)
{
   
   
    assert(pphead);
    //1、空
    assert(*pphead);

    //2、一个节点
    //3、一个以上节点
    if ((*pphead)->next == NULL)
    {
   
   
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
   
   
        SLTNode* tailPrev = *pphead;
        SLTNode* tail = *pphead;
        while (tail->next != NULL)
        {
   
   
            tailPrev = tail;
            tail = tail->next;
        }
        free(tail);
        tailPrev->next = NULL;
    }
}

//头删
void SLTPopFront(SLTNode** pphead)
{
   
   
    assert(pphead);
    //空
    assert(*pphead);
    //非空
    SLTNode* newhead = (*pphead)->next;
    free(*pphead);
    *pphead = newhead;
}

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
   
   
    SLTNode* cur = phead;
    while (cur)
    {
   
   
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

//在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
   
   
    assert(pphead);
    assert(pos);
    if (pos == *pphead)
    {
   
   
        SLTPushFront(pphead, x);
    }
    else
    {
   
   
        SLTNode* posPrev = *pphead;
        while (posPrev->next != pos)
        {
   
   
            posPrev = posPrev->next;
        }
        SLTNode* newnode = BuySListNode(x);
        posPrev->next = newnode;
        newnode->next = pos;
    }
}

//在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
   
   
    assert(pos);
    SLTNode* newnode = BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
   
   
    assert(pphead);
    assert(pos);
    if (pos == *pphead)
    {
   
   
        SLTPopFront(pphead);
    }
    else
    {
   
   
        SLTNode* posPrev = *pphead;
        while (posPrev->next != pos)
        {
   
   
            posPrev = posPrev->next;
        }
        posPrev->next = pos->next;
        free(pos);
    }
}

//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
   
   
    assert(pos);
    //检查pos是否是尾节点
    assert(pos->next);

    SLTNode* posNext = pos->next;
    pos->next = posNext->next;
    free(posNext);
    posNext = NULL;
}

//销毁单链表
void SLTDestroy(SLTNode** pphead)
{
   
   
    assert(pphead);
    SLTNode* cur = *pphead;
    while (cur)
    {
   
   
        SLTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    *pphead = NULL;
}

5.3 Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

void TestSList()
{
   
   
    SLTNode* plist = NULL;
    SLTPushBack(&plist, 1);
    SLTPushBack(&plist, 2);
    SLTPushBack(&plist, 3);
    SLTPushBack(&plist, 4);
    SLTPushBack(&plist, 5);
    SLTPrint(plist);

    SLTPushFront(&plist, 10);
    SLTPushFront(&plist, 20);
    SLTPushFront(&plist, 30);
    SLTPushFront(&plist, 40);
    SLTPrint(plist);

    SLTPopFront(&plist);
    SLTPrint(plist);

    SLTPopBack(&plist);
    SLTPrint(plist);

    SLTNode* pos = SLTFind(plist, 2);
    if (pos)
    {
   
   
        pos->data *= 100;
    }
    SLTPrint(plist);

    pos = SLTFind(plist,10);
    SLTInsert(&plist, pos, 39);
    SLTPrint(plist);

    SLTInsertAfter(pos, 56);
    SLTPrint(plist);

    pos = SLTFind(plist, 20);
    SLTErase(&plist, pos);
    SLTPrint(plist);

    pos = SLTFind(plist, 3);
    SLTEraseAfter(pos);
    SLTPrint(plist);

    SLTDestroy(&plist);
}

int  main()
{
   
   
    TestSList();
    return 0;
}

6. 总结

到这里，我们就用C语言实现了数据结构中的单链表。有什么问题欢迎在评论区讨论。如果觉得文章有什么不足之处，可以在评论区留言。如果喜欢我的文章，可以点赞收藏哦！

​

文章标签：
存储
C语言
DataX
关键词：
数据结构单链表
是基德吖
目录
相关文章
睡觉待开机
|
5天前
【数据结构】单链表(长期维护)（1）
【数据结构】单链表(长期维护)（1）
睡觉待开机
11 0
小李很执着
|
3月前
|
存储
[数据结构]——单链表——超详解
[数据结构]——单链表——超详解
小李很执着
45 0
chian-ocean
|
11天前
|
存储
【数据结构】单链表--＞详细讲解，后赋源码
【数据结构】单链表--＞详细讲解，后赋源码
chian-ocean
15 4
睡觉待开机
|
5天前
【数据结构】单链表(长期维护)（2）
【数据结构】单链表(长期维护)（2）
睡觉待开机
5 0
lge101058
|
2月前
|
存储 测试技术
【数据结构】最最基础的链式结构——单链表，还不会你就吃大亏了！
【数据结构】最最基础的链式结构——单链表，还不会你就吃大亏了！
lge101058
30 5
倔强的石头_
|
2月前
|
算法 程序员 数据处理
【数据结构与算法】使用单链表实现队列：原理、步骤与应用
【数据结构与算法】使用单链表实现队列：原理、步骤与应用
倔强的石头_
25 0
倔强的石头_
|
2月前
|
算法 C语言
【数据结构与算法 经典例题】返回单链表的倒数第 k 个节点
【数据结构与算法 经典例题】返回单链表的倒数第 k 个节点
倔强的石头_
24 0
倔强的石头_
|
2月前
|
存储 算法 C语言
【数据结构与算法】深入理解 单链表
【数据结构与算法】深入理解 单链表
倔强的石头_
20 0
Sessy
|
3月前
＜数据结构＞栈和队列. 顺序表实现栈，单链表实现队列.
＜数据结构＞栈和队列. 顺序表实现栈，单链表实现队列
Sessy
35 3
叶落闲庭
|
3月前
|
索引
【数据结构】单链表代码实现
【数据结构】单链表代码实现
叶落闲庭
21 1