1. Johngo学长首页
  2. 技术点详细复盘专题
  3. 人工智能

数据结构 | 单链表

• 人工智能 • 阅读 73

…

🌳🌲🌱本文已收录至：数据结构 | C语言
更多知识尽在此专栏中!

数据结构 | 单链表
数据结构 | 单链表

文章目录

; 🌳前言

单链表 是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。 链表 中的数据是以结点来表示的，每个结点的构成： 元素(数据元素的映象) + 指针(指示后继元素存储位置) ，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据

这是百度百科对于 单链表 的解释，通俗来说， 单链表 就是一种数据结构，它包含了一个 数据域 data 和一个 指针域 next ，最大的特点就是 链式存储 。链表有很多种，其中 单链表 是最基本、最简单的一种结构，很多OJ题都会利用 单链表 出题，后面的部分高阶数据结构也会用到 单链表 ，因此学好 单链表 很重要。除了 单链表 外，还有 双向带头循环链表 (后面会介绍)等链表类型，先来进入 单链表 的学习吧！

数据结构 | 单链表

; 🌳正文

🌲链表打印与销毁

🪴打印

单链表 创建时是一个结构体类型的指针， 一开始指向空，只有在经过插入数据后才会有自己的指向 ，因此我们可以根据这一特点， 遍历 整个 单链表 ，并输出其中的 数据域 data。

数据结构 | 单链表 
void SLTPrint(const SLT** pphead)
{
    assert(pphead);

    printf("\n\n当前链表为: ");
    const SLT* cur = *pphead;
    while (cur)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }

    printf("NULL\n\n\n");
}

🪴销毁

销毁 单链表 也需要将其 遍历 一遍， 因为链表中的元素不是连续存放的，只能逐个节点销毁 ，销毁思想为：利用 *pphead 遍历整个 单链表 ，保存头节点 *pphead 的下一个节点信息至 cur，释放原头节点，更新头节点信息(把 cur 的值赋给头节点 *pphead )如此重复，直到释放完所有节点即可。

数据结构 | 单链表 

void SLTDestroy(SLT** pphead)
{
    assert(pphead);

    if (*pphead)
    {
        while (*pphead)
        {
            SLT* cur = (*pphead)->next;
            free(*pphead);
            *pphead = cur;
        }
    }
}

🌲尾部插入与删除

🪴节点申请

单链表 是由一个一个独立存在的节点组成的结构， 当涉及插入操作时，向内存申请节点，涉及删除操作时，就要把对应的节点销毁

static SLT* buyNode(const SLTDataType x)
{
    SLT* newnode = (SLT*)malloc(sizeof(SLT));
    assert(newnode);

    newnode->data = x;
    newnode->next = NULL;

    return newnode;
}

🪴尾插

单链表 尾插是比较费劲的，因为得先通过头节点指针向后 遍历 找到尾节点，然后将尾节点与新节点之间建立链接关系，其中还得分情况尾插

  • 链表为空，直接把新节点赋给头节点
  • *不为空，就需要找到尾节点，建立链接关系

关于 单链表 中函数用二级指针的问题：
插入或删除时，如果是第一次操作，需要对头节点本身造成改变，且头节点是一个 一级指针 ，因此需要通过 二级指针 的方式来在函数中改变头节点的值。至于后续的操作，都只是改变了结构体中的 next 值，因此使用 一级指针 就够了，但是为了函数设计时的普适性， 单链表 中的函数参数都设计成了 二级指针 的形式。

数据结构 | 单链表 
void SLTPushBack(SLT** pphead, const SLTDataType x)
{
    assert(pphead);

    SLT* newnode = buyNode(x);
    SLT* tail = *pphead;

    if (tail == NULL)
    {
        *pphead = tail = newnode;
    }
    else
    {
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }

}

🪴尾删

尾删操作与尾插基本一致，同样是需要找到尾节点，不过每次 tail 指针在向后移动前，会先使用一个 prev 指针保存 tail 的信息，当 tail 为尾节点时，释放 tail ，并将 prev->next 置空，此时的 prev 就是新的尾节点，因为原理都差不多，这里就不用动图展示了，值得注意的是尾删也分两种情况

  • 只有一个节点，此时直接释放头节点(尾节点)，链表置空
  • 存在多个节点，需要先找到尾节点与尾节点的上一个节点，确定新的尾
  • 并不是所有情况都能删除，比如表空的情况，是不能执行操作的，可以用断言处理

数据结构 | 单链表
数据结构 | 单链表 
void SLTPopBack(SLT** pphead)
{
    assert(pphead);
    assert(*pphead);

    SLT* tail = *pphead;
    SLT* prev = NULL;
    while (tail->next)
    {
        prev = tail;
        tail = tail->next;
    }

    free(tail);

    if (prev)
        prev->next = tail = NULL;
    else
        *pphead = NULL;

}

🌲头部插入与删除

🪴头插

对于头部操作来说， 单链表 是很轻松的，比如 单链表 头插的本质就是将 新节点 newnode 与 头节点 *pphead 链接，然后更新头节点信息就行了，即 *pphead = newnode ，三行代码就解决了。

数据结构 | 单链表
数据结构 | 单链表 
void SLTPushFront(SLT** pphead, const SLTDataType x)
{
    assert(pphead);

    SLT* newhead = buyNode(x);
    newhead->next = *pphead;
    *pphead = newhead;

}

🪴头删

头删也是比较简单的，先用 cur 指向头节点，先保存 头节点 cur 的下一个节点信息至 节点 newhead，释放 原头节点 cur，更新 newhead 为链表的新头，即 *pphead = newnode 当然涉及删除的操作，都需要进行表空检查，如果链表为空，是不能执行删除的。

数据结构 | 单链表
数据结构 | 单链表 
void SLTPopFront(SLT** pphead)
{
    assert(pphead);
    assert(*pphead);

    SLT* cur = *pphead;
    SLT* newhead = cur->next;

    free(cur);
    cur = NULL;

    *pphead = newhead;

}

🌲节点查找与修改

🪴查找

查找函数很简单， 遍历+比较 就行了， 找到目标元素值后，返回相关节点信息，其实查找这个函数主要是为了配合后面任意插入删除函数的 ，所以比较简单。

SLT* SLTFind(const SLT** pphead, const SLTDataType x)
{
    assert(pphead);

    SLT* cur = (SLT*)*pphead;
    while (cur)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }

    return NULL;
}

🪴修改

修改函数是在查找函数基础上进行的： 当我们输入元素值交给查找函数，找到目标节点后返回其节点信息，然后直接通过返回的节点改变 data 值就行了，在调用查找函数的前提下，一行代码就解决了。

void SLTModify(SLT* node, const SLTDataType val)
{

    assert(node);
    node->data = val;
}

🌲任意位置插入与删除

🪴简单版

简单版是在任意位置后插入元素，删除任意位置后的节点，根据 单链表 的特性，对后面节点进行操作是比较简单，无非就是改变链接关系。但是这种对后操作存在缺陷： 不适合实现头插、头删

🌱插入

插入(后插)主要分两步

  • 获取信息
  • *改变链接关系

获取信息：有三个关键信息：被插入节点 cur 、待插入节点 newnode 和 cur 的下一个节点 tail

改变链接关系：很简单， cur->next = newnode ，后插嘛，先把待插入节点链接到 cur 后面，然后再把 newnode 和 tail 链接起来就行了

这里的 nodeAfter 是需要通过查找函数找出来的，它是一个 一级指针


void SLTInsertAfter(SLT* nodeAfter, const SLTDataType x)
{
    assert(nodeAfter);

    SLT* cur = nodeAfter;
    SLT* newnode = buyNode(x);
    SLT* tail = cur->next;

    cur->next = newnode;
    newnode->next = tail;
}

🌱删除

删除思路，和头删差不多

  • 找到待插入节点 cur
  • 找到 cur 的下一个节点 tail
  • *找到 tail 的下一个节点 newtail

接下来就很简单了，释放 tail 节点，更改链接关系，当然断言是少不了

数据结构 | 单链表
数据结构 | 单链表 
void SLTEraseAfter(SLT* nodeAfter)
{
    assert(nodeAfter);
    assert(nodeAfter->next);

    SLT* cur = nodeAfter;
    SLT* tail = cur->next;
    SLT* newtail = tail->next;

    free(tail);
    tail = NULL;

    cur->next = newtail;
}

🪴困难版

困难版就比较麻烦了，因为它要实现的是任意位置前插元素、删除任意位置的节点， 单链表 的最大缺点是不能回退， 这就意味着即使我们得到了待删除节点，也是很难求出它的上一个节点的 ，对于这种尴尬情况，只能老老实实从头节点处开始向后 遍历 寻找，直到找到待删除节点的上一个节点。

🌱插入

其实这个也没有多困难，无非就是比上一种多个参数，然后多了一步遍历操作而已，内核思想任然不变

  • 获取信息
  • *更改链接关系

数据结构 | 单链表 

void SLTInsert(SLT** pphead, SLT* node, const SLTDataType x)
{
    assert(pphead);

    SLT* newnode = buyNode(x);
    SLT* cur = *pphead;
    SLT* prev = NULL;
    while (cur != node)
    {
        prev = cur;
        cur = cur->next;
    }

    if (prev)
    {
        prev->next = newnode;
        newnode->next = node;
    }
    else
    {
        newnode->next = node;
        *pphead = newnode;
    }
}

🌱删除

删除是一样的逻辑，不过多了一个 tail 而已，指向的位置是 node 的下一个节点， 其余步骤跟插入基本一致，之后也是一样的更改链接关系，一样需要判断是否为空表，如果为空表需要更新头节点信息。

其实现在看来，困难版的插入删除，就像是尾部插入删除的升级版，有些麻烦，但很可靠，困难版的任意位置插入删除可以完全替代头尾插入删除，也就是说写这一对函数就够了。

void SLTErase(SLT** pphead, SLT* node)
{
    assert(pphead);
    assert(node);

    SLT* cur = *pphead;
    SLT* prev = NULL;
    SLT* tail = node->next;
    while (cur != node)
    {
        prev = cur;
        cur = cur->next;
    }

    free(node);

    if (prev)
        prev->next = tail;
    else
        *pphead = tail;
}

🌲源码区

代码放一起看，会更好理解一些~

🪴功能声明头文件部分

#pragma once
#include
#include
#include
#include

typedef int SLTDataType;

typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;
}SLT;

void SLTDestroy(SLT** pphead);
void SLTPrint(const SLT** pphead);

void SLTPushBack(SLT** pphead, const SLTDataType x);
void SLTPopBack(SLT** pphead);

void SLTPushFront(SLT** pphead, const SLTDataType x);
void SLTPopFront(SLT** pphead);

void SLTInsertAfter(SLT* nodeAfter, const SLTDataType x);
void SLTEraseAfter(SLT* nodeAfter);

void SLTInsert(SLT** pphead, SLT* node, const SLTDataType x);
void SLTErase(SLT** pphead, SLT* node);

SLT* SLTFind(const SLT** pphead, const SLTDataType x);

void SLTModify(SLT* node, const SLTDataType val);

🪴功能实现源文件部分

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

void SLTDestroy(SLT** pphead)
{
    assert(pphead);

    if (*pphead)
    {
        while (*pphead)
        {
            SLT* cur = (*pphead)->next;
            free(*pphead);
            *pphead = cur;
        }
    }
}

void SLTPrint(const SLT** pphead)
{
    assert(pphead);

    printf("\n\n当前链表为: ");
    const SLT* cur = *pphead;
    while (cur)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }

    printf("NULL\n\n\n");
}

static SLT* buyNode(const SLTDataType x)
{
    SLT* newnode = (SLT*)malloc(sizeof(SLT));
    assert(newnode);

    newnode->data = x;
    newnode->next = NULL;

    return newnode;
}

void SLTPushBack(SLT** pphead, const SLTDataType x)
{
    assert(pphead);

    SLT* newnode = buyNode(x);
    SLT* tail = *pphead;

    if (tail == NULL)
    {
        *pphead = tail = newnode;
    }
    else
    {
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }

}

void SLTPopBack(SLT** pphead)
{
    assert(pphead);
    assert(*pphead);

    SLT* tail = *pphead;
    SLT* prev = NULL;
    while (tail->next)
    {
        prev = tail;
        tail = tail->next;
    }

    free(tail);

    if (prev)
        prev->next = tail = NULL;
    else
        *pphead = NULL;

}

void SLTPushFront(SLT** pphead, const SLTDataType x)
{
    assert(pphead);

    SLT* newhead = buyNode(x);
    newhead->next = *pphead;
    *pphead = newhead;

}

void SLTPopFront(SLT** pphead)
{
    assert(pphead);
    assert(*pphead);

    SLT* cur = *pphead;
    SLT* newhead = cur->next;

    free(cur);
    cur = NULL;

    *pphead = newhead;

}

void SLTInsertAfter(SLT* nodeAfter, const SLTDataType x)
{
    assert(nodeAfter);

    SLT* cur = nodeAfter;
    SLT* newnode = buyNode(x);
    SLT* tail = cur->next;

    cur->next = newnode;
    newnode->next = tail;
}

void SLTEraseAfter(SLT* nodeAfter)
{
    assert(nodeAfter);
    assert(nodeAfter->next);

    SLT* cur = nodeAfter;
    SLT* tail = cur->next;
    SLT* newtail = tail->next;

    free(tail);
    tail = NULL;

    cur->next = newtail;
}

void SLTInsert(SLT** pphead, SLT* node, const SLTDataType x)
{
    assert(pphead);

    SLT* newnode = buyNode(x);
    SLT* cur = *pphead;
    SLT* prev = NULL;
    while (cur != node)
    {
        prev = cur;
        cur = cur->next;
    }

    if (prev)
    {
        prev->next = newnode;
        newnode->next = node;
    }
    else
    {
        newnode->next = node;
        *pphead = newnode;
    }
}

void SLTErase(SLT** pphead, SLT* node)
{
    assert(pphead);
    assert(node);

    SLT* cur = *pphead;
    SLT* prev = NULL;
    SLT* tail = node->next;
    while (cur != node)
    {
        prev = cur;
        cur = cur->next;
    }

    free(node);

    if (prev)
        prev->next = tail;
    else
        *pphead = tail;
}

SLT* SLTFind(const SLT** pphead, const SLTDataType x)
{
    assert(pphead);

    SLT* cur = (SLT*)*pphead;
    while (cur)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }

    return NULL;
}

void SLTModify(SLT* node, const SLTDataType val)
{

    assert(node);

    node->data = val;
}

🪴主函数调用源文件部分

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

void menu()
{
    printf("0.退出    1.打印\n");
    printf("2.尾插    3.尾删\n");
    printf("4.头插    5.头删\n");
    printf("6.任意插(后插)   7.任意删(后删)\n");
    printf("8.任意插(前插)   9.任意删(当前)\n");
    printf("10.查找   11.修改\n");
}

int main()
{
    SLT* s = NULL;
    int input = 1;
    while (input)
    {
        menu();
        printf("请选择:>");
        scanf("%d", &input);
        system("cls");
        int val = 0;
        int pos = 0;
        switch (input)
        {
        case 0:
            printf("成功退出\n");
            break;
        case 1:
            SLTPrint(&s);
            break;
        case 2:
            printf("请输入一个数:>");
            scanf("%d", &val);
            SLTPushBack(&s, val);
            break;
        case 3:
            SLTPopBack(&s);
            break;
        case 4:
            printf("请输入一个数:>");
            scanf("%d", &val);
            SLTPushFront(&s, val);
            break;
        case 5:
            SLTPopFront(&s);
            break;
        case 6:
            printf("请输入被插入的节点值:>");
            scanf("%d", &pos);
            printf("请输入一个数:>");
            scanf("%d", &val);
            SLTInsertAfter(SLTFind(&s, pos), val);
            break;
        case 7:
            printf("请输入被删除的节点值:>");
            scanf("%d", &pos);
            SLTEraseAfter(SLTFind(&s, pos));
            break;
        case 8:
            printf("请输入被插入的节点值:>");
            scanf("%d", &pos);
            printf("请输入一个数:>");
            scanf("%d", &val);
            SLTInsert(&s, SLTFind(&s, pos), val);
            break;
        case 9:
            printf("请输入被删除的节点值:>");
            scanf("%d", &pos);
            SLTErase(&s, SLTFind(&s, pos));
            break;
        case 10:
            printf("请输入被查找的节点值:>");
            scanf("%d", &pos);
            SLT* tmp = SLTFind(&s, pos);
            printf("当前节点的地址为:%p\n", tmp);
            break;
        case 11:
            printf("请输入被修改的节点值:>");
            scanf("%d", &pos);
            printf("请输入一个数:>");
            scanf("%d", &val);
            SLTModify(SLTFind(&s, pos), val);
            break;
        default :
            printf("选择错误，重新选择!\n");
            break;
        }
    }
    SLTDestroy(&s);
    return 0;
}

🌲相关OJ试题推荐

下面是几道关于 单链表 的OJ试题，可以试着解决一下，加强对链表的认识

  1. 203.移除链表元素
  2. 206.反转单链表
  3. 876.链表的中间结点
  4. 链表中倒数第k个结点
  5. 21.合并两个有序链表
  6. CM11 链表分割
  7. OR36 链表的回文结构
  8. 160.相交链表
  9. 141.环形链表
  10. 141.环形链表 ||
  11. 138.复制带随机指针的链表

🌳总结

以上就是关于 单链表 的全部内容了， 单链表 中用到了 二级指针 这个东西，如果使用带哨兵位的 单链表 就可以不用 二级指针 ，但是这种结构用的比较少，单纯的学好 单链表 ，能快速提高我们对链表的认识，毕竟链表这个工具后续还会用到。从文中可以看出， 单链表 相对于 顺序表 ，不用考虑空间问题，且头插头删效率很高，可惜 单链表 不支持下标的随机访问。总之， 顺序表 和 单链表 各有各的用途，二者相辅相成，都是很不错的数据结构。

如果你觉得本文写的还不错的话，期待留下一个小小的赞👍，你的支持是我分享的最大动力！

如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正

数据结构 | 单链表

…

相关文章推荐
数据结构 | 顺序表
数据结构 | 时间复杂度与空间复杂度
C语言进阶——动态内存管理

Original: https://blog.csdn.net/weixin_61437787/article/details/127818154
Author: Yohifo
Title: 数据结构 | 单链表

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/659898/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球