AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【DS】单链表@线性表 —— 增删查改

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

@TOC

嘿嘿：上次实现单链表已经是两个月之前的事儿了，今儿拿出来再写，思路还是在，但确实忘掉了一些细节，一上午出现了各种小问题，全都是自己一个个调出来的，这种快感不是别的什么事情可以代替的。同时也发现，当初觉得想不到的东西，现在看也就是理所当然，这就是螺旋式上升吧:ram:！

0. 引

上文说到顺序表缺陷 ——

:snowflake:1. 空间不够需要 增容，增容是要付出代价的。
:snowflake:2. 为了避免频繁扩容，我们基本都是按倍数去扩（比如扩2倍），这又可能会造成一定的 空间浪费。
:snowflake:3. 顺序表要求数据从开始位置保持连续，那么中间和头部的插入和删除，都需要挪动数据，时间复杂度为 O(N)， 效率不高。

为此，我们引入了链表。

1. 链表的概念和结构

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

  • [ ] 逻辑图 —— 想象出来的形象方式表示

<img src=" title="">

  • [ ] 物理图 —— 内存中的真实存储 —— 通过指针来存储下一个节点的地址，并不连续

<img src=" title="">

2. 链表的分类

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

  • [ ] 单向或双向

<img src=" title="">

  • [ ] 带头不带头

<img src=" title="">

  • [ ] 循环非循环

在这里插入图片描述

当然我们最常用的还是这两种 ——

  1. 无头单向非循环链表

<img src=" title="">

  • 结构简单，但缺陷还是很多（一会儿实现的时候你就知道啦），单纯单链表的增删查改意义不大。
  • 但是还是要写，可能正因为它的缺陷，很多oj题考察的都是单链表
  • 更多的是做更复杂数据结构的子结构，比如哈希桶、邻接表。
  1. 带头双向循环链表

<img src=" title="">

  • 结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。
  • 另外这个结构虽然复杂，却也是无死角的结构，用代码实现时会发现结构会带来很多优势，非常爽，后面我们代码实现了就知道了。

3. 链表的实现

文末领取头文件大家自己写，自己写自己调时候思路是最清晰的，具体实现中每个思路和要注意的小点我都会写好（尤其是它第一次出现的时候）（这链表电脑画图老累了，主要是这个破箭头，ipad上写字还丑，我把我草纸的图弄进来了哦吼吼）红笔写的是边界，耦合色写的是变化过程哈哈。

3.1 打印、申请新节点、销毁

3.1.1 打印

<img src=" title="">

void SListPrint(SLTNode* phead)
{
    SLTNode* cur = phead;
    while (cur)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

3.1.2 申请新节点

//申请新节点
SLTNode* BuyListNode(SListDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        printf("malloc failed\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

3.1.3 销毁

  • 顺序表中申请的内存是连续的(realloc)，因此一次释放就行；而链表的空间申请时候就不连续，必须遍历回收。
  • free时，data和next都会被置成随机值，因此要记录next

<img src=" title="">

void SListDestroy(SLTNode** pphead)
{
    assert(pphead);
    // 链表的空间必须遍历回收，因为申请时候就不连续
    SLTNode* cur = *pphead;
    SLTNode* next = cur->next;// 记录下一个节点的位置
    while (next)
    {
        free(cur);
        cur = next;
        next = cur->next;
    }
    *pphead = NULL;
}

3.2 尾插、尾删

3.2.1 尾插

  • 为什么要传二级指针？尾插、包括后面的尾删头插头删、前面的销毁都需要传二级指针，而打印、查找就不需要。

:strawberry:实际上，二级指针就是为了处理首节点的改变（pList是链表的地址，类型为SLNode*），后面操纵的都是结构体就不需要。众所周知形参是实参的一份临时拷贝，形参的改变不会影响实参，因此必须传实参地址（在这里类型为SLNode**）以改变实参。

  • 解释一下assert(pphead);，像这种一定不为空的要断言一下，方便查错（传错）

<img src=" title="">

void SListPushBack(SLTNode** pphead, SListDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyListNode(x);
    //1.空链表 - 尾插头结点的地址pList发生改变，因此需要传pList的地址
    //单拎出来处理
    if (*pphead == NULL)
    {
        *pphead = newnode;
        return;
    }
    //2.找尾
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
        tail = tail->next;
    }
    tail->next = newnode;
}

3.2.2 尾删

  • 考虑链表为空 —— 断言结束（STL采取的就是这样粗暴的方式），毕竟，就是你用错了
  • 其余细节过程都在图中

<img src=" title="">

void SListPopBack(SLTNode** pphead)
{
    assert(pphead);
    //1.空链表
    assert(*pphead);
    //2.删的只剩一个节点时
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
        return;
    }

    //3.
    //找尾的上一个
    SLTNode* prevtail = *pphead;
    SLTNode* tail = prevtail->next;
    while (tail->next != NULL)
    {
        prevtail = tail;
        tail = tail->next;
    }
    free(tail);
    prevtail->next = NULL;
}

3.3 头插、头删

3.3.1 头插

<img src=" title="">

void SListPushFront(SLTNode** pphead, SListDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

3.3.2 头删

<img src=" title="">

void SListPopFront(SLTNode** pphead)
{
    assert(pphead);
    //1.删空
    assert(*pphead);
    //2.
    SLTNode* headnext = (*pphead)->next;
    free(*pphead);
    *pphead = headnext;
}

3.4 查找、任意位置插入、任意位置删除

3.4.1 查找

SLTNode* SListFind(SLTNode* phead, SListDataType x)
{
    SLTNode* cur = phead;
    if (phead == NULL)
    {
        //处理空链表，不然后面解引用可是又错了
        return NULL;
    }
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    return NULL;//走到这儿还没找到
}

3.4.2 任意位置插入

<img src=" title="">

//在pos位置之前去插入一个节点--pos位置一般是find来的
void SListInsert(SLTNode** pphead, SLTNode* pos, SListDataType x)
{
    assert(pphead);
    assert(pos);
    SLTNode* newnode = BuyListNode(x);
    //1. 头插
    if (*pphead == pos)
    {
        newnode->next = *pphead;
        *pphead = newnode;
    }
    //2.
    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
        posPrev = posPrev->next;
    }
    posPrev->next = newnode;
    newnode->next = pos;
}

<img src=" title="">

//在pos后边插入--这个更适合也更简单高效
//STL- insert_after
void SListInsertAfter(SLTNode* pos, SListDataType x)
{
    assert(pos);
    SLTNode* newnode = BuyListNode(x);
    SLTNode* posNext = pos->next;
    pos->next = newnode;
    newnode->next = posNext;
}

3.4.3 任意位置删除

<img src=" title="">

void SListErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead);
    assert(pos);
    //删空
    assert(*pphead);
    //1.头删
    //带哨兵位的头的 -- 可以合并 头删与中间删 -- 逻辑结构一样，不会删完
    if (*pphead == pos)
    {
        *pphead = pos->next;
        free(pos);
        return;//自己调出来的
    }

    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
        posPrev = posPrev->next;
    }
    posPrev->next = pos->next;
    free(pos);//注意顺序，对于我很简单啦
    //pos不置空也无所谓，毕竟在函数中是形参，形参的改变不会影响实参，处于好习惯，还是置空比较好
}

当然也可以实现删除pos后面的节点，这个功能很奇葩哈哈给pos不删pos

void SListEraseAfter(SLTNode* pos)
{
    assert(pos);
    assert(pos->next);//一个节点
    SLTNode* posNext = pos->next;
    pos->next = posNext->next;
    free(posNext);
    //next = NULL;//出作用域即销毁，是野指针，但别人拿不到
}

4. 关于单链表的思考

4.1 链表优点

链表弥补了顺序表的缺陷

  1. 按需申请空间，不用了就释放（更合理的使用了空间），不存在空间浪费
  2. 头部和中间插入删除数据，不需要挪动数据

4.1 链表缺点

  1. 每一个数据，都要存一个指针链接后面的数据结点
  2. 不支持随机访问（用下标直接访问第i个元素），而有些算法，需要随机访问，如：二分查找、优化的快排

附录

SingleList.h

#pragma once

//无头单向非循环链表
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SListDataType;

typedef struct SListNode
{
    SListDataType data;
    struct SListNode* next;
}SLTNode;

void SListPrint(SLTNode* phead);
//销毁
void SListDestroy(SLTNode** pphead);

//尾插
void SListPushBack(SLTNode** pphead, SListDataType x);
//尾删
void SListPopBack(SLTNode** pphead);
//头插
void SListPushFront(SLTNode** pphead, SListDataType x);
//头删
void SListPopFront(SLTNode** pphead);

//查找
SLTNode* SListFind(SLTNode* phead, SListDataType x);
//在pos位置之前去插入一个节点--pos位置一般是find来的
void SListInsert(SLTNode** pphead, SLTNode* pos, SListDataType x);
//任意位置删
void SListErase(SLTNode** pphead, SLTNode* pos);
//在pos后边插入--这个更适合也更简单高效
void SListInsertAfter(SLTNode* pos, SListDataType x);

void SListEraseAfter(SLTNode* pos);
//void SListInsert(SLTNode* phead, SLTNode* pos,SListDataType x);
//void SListErase(SLTNode* phead, int pos);

SingleList.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"SList.h"

void SListPrint(SLTNode* phead)
{
    SLTNode* cur = phead;
    while (cur)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void SListDestroy(SLTNode** pphead)
{
    // 这个链表是
    // 链表的空间必须遍历回收，因为申请时候就不连续
    SLTNode* cur = *pphead;
    SLTNode* next = cur->next;// 记录下一个节点的位置
    while (next)
    {
        free(cur);
        cur = next;
        next = cur->next;
    }
    *pphead = NULL;
}

//申请新节点
SLTNode* BuyListNode(SListDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        printf("malloc failed\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

void SListPushBack(SLTNode** pphead, SListDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyListNode(x);
    //1.空链表 - 尾插头结点的地址pList发生改变，因此需要传pList的地址
    // **pphead
    if (*pphead == NULL)
    {
        *pphead = newnode;
        return;
    }
    //找尾
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
        tail = tail->next;
    }
    tail->next = newnode;
}

void SListPopBack(SLTNode** pphead)
{
    assert(pphead);
    //1.空链表
    assert(*pphead);
    //2.删的只剩一个节点时
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
        return;
    }

    //3.普遍情况
    //找尾的上一个
    SLTNode* prevtail = *pphead;
    SLTNode* tail = prevtail->next;
    while (tail->next != NULL)
    {
        prevtail = tail;
        tail = tail->next;
    }
    free(tail);
    prevtail->next = NULL;
}


void SListPushFront(SLTNode** pphead, SListDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

void SListPopFront(SLTNode** pphead)
{
    assert(pphead);
    //1.删空
    assert(*pphead);
    //2.
    SLTNode* headnext = (*pphead)->next;
    free(*pphead);
    *pphead = headnext;
}

SLTNode* SListFind(SLTNode* phead, SListDataType x)
{
    SLTNode* cur = phead;
    if (phead == NULL)
    {
        //处理空链表，不然后面解引用可是又错了
        return NULL;
    }
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    return NULL;//走到这儿还没找到
}

//在pos位置之前去插入一个节点--pos位置一般是find来的
void SListInsert(SLTNode** pphead, SLTNode* pos, SListDataType x)
{
    assert(pphead);
    assert(pos);
    SLTNode* newnode = BuyListNode(x);
    //1. 头插
    if (*pphead == pos)
    {
        newnode->next = *pphead;
        *pphead = newnode;
    }
    //2.
    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
        posPrev = posPrev->next;
    }
    posPrev->next = newnode;
    newnode->next = pos;
}

//在pos后边插入--这个更适合也更简单高效
//STL- insert_after
void SListInsertAfter(SLTNode* pos, SListDataType x)
{
    assert(pos);
    SLTNode* newnode = BuyListNode(x);
    SLTNode* posNext = pos->next;
    pos->next = newnode;
    newnode->next = posNext;
}


//任意位置删
void SListErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead);
    assert(pos);
    //删空
    assert(*pphead);
    //1.头删
    //带哨兵位的头的 -- 可以合并 头删与中间删 -- 逻辑结构一样，不会删完
    if (*pphead == pos)
    {
        *pphead = pos->next;
        free(pos);
        return;//自己调出来的
    }

    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
        posPrev = posPrev->next;
    }
    posPrev->next = pos->next;
    free(pos);//注意顺序，对于我很简单啦
    //pos不置空也无所谓，毕竟在函数中是形参，形参的改变不会影响实参，处于好习惯，还是置空比较好

}

void SListEraseAfter(SLTNode* pos)
{
    assert(pos);
    assert(pos->next);//一个节点
    SLTNode* posNext = pos->next;
    pos->next = posNext->next;
    free(posNext);
    //next = NULL;//出作用域即销毁，是野指针，但别人拿不到
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"SList.h"

//测试尾插尾删
void testSingleList1()
{
    //指向单链表的指针 - 本质是存储这个单链表头结点的地址的指针变量
    SLTNode* pList;
    pList = NULL;//这个错是我调出来的
    SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 3);
    SListPushBack(&pList, 4);
    SListPrint(pList);

    SListPopBack(&pList);
    SListPopBack(&pList);
    SListPopBack(&pList);
    /*SListPopBack(&pList);
    SListPopBack(&pList);*/

    SListPrint(pList);
    SListDestroy(&pList);
}

//测试头插头删
void testSingleList2()
{
    SLTNode* pList;
    pList = NULL;
    SListPushFront(&pList, 1);
    SListPushFront(&pList, 2);
    SListPushFront(&pList, 3);

    SListPrint(pList);

    SListPopFront(&pList);
    SListPopFront(&pList);
    /*SListPopFront(&pList);
    SListPopFront(&pList);*/

    SListPrint(pList);

    SListDestroy(&pList);
}

//测试任意位置的插入、查找
void testSingleList3()
{
    SLTNode* pList;
    pList = NULL;
    SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 4);
    SListPushBack(&pList, 5);

    SLTNode* ret = SListFind(pList, 2);
    if (ret == NULL)
    {
        printf("not found\n");
    }
    else
    {
        printf("%d\n", ret->data);
    }
    //SListInsert(&pList, ret, 0);//测试头插
    //SListInsert(&pList, ret, 3);

    SListInsertAfter(ret, 3);
    SListPrint(pList);
    SListDestroy(&pList);

}

//测试任意位置删
void testSingleList4()
{
    SLTNode* pList;
    pList = NULL;
    SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 4);
    SListPushBack(&pList, 5);
    SListPrint(pList);

    SLTNode* ret = SListFind(pList, 1);
    if (ret == NULL)
    {
        printf("not found\n");
    }
    else
    {
        printf("%d\n", ret->data);
    }
    //SListErase(&pList, ret);
    //SListErase(&pList, ret);

    SListEraseAfter(ret);
    SListPrint(pList);
    SListDestroy(&pList);

}

int main()
{
    //testSingleList1();
    //testSingleList2();
    //testSingleList3();
    testSingleList4();
    return 0;
}

下一篇来带头双向循环链表

本文完

文章标签：
C++
iOS开发
算法
存储
@浮光掠影
目录
相关文章
2025「AI安全」全球攻防赛小编
|
2天前
|
人工智能 运维 安全
亚太厂商唯一！阿里云以应用身份服务IDaaS入选全球 Gartner Access Management 魔力象限
中国厂商0→1突破
2025「AI安全」全球攻防赛小编
1457 10
2025「AI安全」全球攻防赛小编
|
9天前
|
人工智能 自然语言处理 安全
双第一！阿里云领跑安全运营智能体
喜报～
2025「AI安全」全球攻防赛小编
2113 8
游客geb4fgnutonte
|
3天前
|
搜索推荐 编译器 Linux
一个可用于企业开发及通用跨平台的Makefile文件
一款适用于企业级开发的通用跨平台Makefile，支持C/C++混合编译、多目标输出（可执行文件、静态/动态库）、Release/Debug版本管理。配置简洁，仅需修改带`MF_CONFIGURE_`前缀的变量，支持脚本化配置与子Makefile管理，具备完善日志、错误提示和跨平台兼容性，附详细文档与示例，便于学习与集成。
游客geb4fgnutonte
271 116
阿里云万网官方
|
18天前
|
域名解析 人工智能
【实操攻略】手把手教学，免费领取.CN域名
即日起至2025年12月31日，购买万小智AI建站或云·企业官网，每单可免费领1个.CN域名首年！跟我了解领取攻略吧~
阿里云万网官方
2175 9
阿里云云原生
|
12天前
|
安全 Java Android开发
深度解析 Android 崩溃捕获原理及从崩溃到归因的闭环实践
崩溃堆栈全是 a.b.c？Native 错误查不到行号？本文详解 Android 崩溃采集全链路原理，教你如何把“天书”变“说明书”。RUM SDK 已支持一键接入。
阿里云云原生
663 219
modelscope
|
5天前
|
数据采集 人工智能 自然语言处理
Meta SAM3开源：让图像分割，听懂你的话
Meta发布并开源SAM 3，首个支持文本或视觉提示的统一图像视频分割模型，可精准分割“红色条纹伞”等开放词汇概念，覆盖400万独特概念，性能达人类水平75%–80%，推动视觉分割新突破。
modelscope
349 34
Meta SAM3开源：让图像分割，听懂你的话
游客6mpq4uc7irdxi
|
10天前
|
人工智能 移动开发 自然语言处理
2025最新HTML静态网页制作工具推荐：10款免费在线生成器小白也能5分钟上手
晓猛团队精选2025年10款真正免费、无需编程的在线HTML建站工具，涵盖AI生成、拖拽编辑、设计稿转代码等多种类型，均支持浏览器直接使用、快速出图与文件导出，特别适合零基础用户快速搭建个人网站、落地页或企业官网。
游客6mpq4uc7irdxi
1576 157
阿里云开发者
|
存储 人工智能 监控
从代码生成到自主决策：打造一个Coding驱动的“自我编程”Agent
本文介绍了一种基于LLM的“自我编程”Agent系统，通过代码驱动实现复杂逻辑。该Agent以Python为执行引擎，结合Py4j实现Java与Python交互，支持多工具调用、记忆分层与上下文工程，具备感知、认知、表达、自我评估等能力模块，目标是打造可进化的“1.5线”智能助手。
阿里云开发者
897 61
1837601489925924
|
7天前
|
编解码 Linux 数据安全/隐私保护
教程分享免费视频压缩软件，免费视频压缩，视频压缩免费，附压缩方法及学习教程
教程分享免费视频压缩软件，免费视频压缩，视频压缩免费，附压缩方法及学习教程
1837601489925924
295 140

热门文章

最新文章

  • 1
    2019阿里云双11来袭,价格非常重要,但是懂得上云攻略更重要
  • 2
    OpenSearch大模型实践之Havenask篇
  • 3
    Git——初始化本地项目并上传到gitlab
  • 4
    07.Java基础（泛型）
  • 5
    沫沫金::一个小问题引发的大思考
  • 6
    Hough变换的方法检测直线段，效果良好
  • 7
    java发送内嵌图片邮件
  • 8
    STL——空间的配置和释放std::alloc（第一级配置器和第二级配置器）
  • 9
    MyBatis之一对多映射查询sql配置文件。
  • 10
    Eclipse 4.3正式版发布
  • 1
    《Unity多插件原生库依赖协同适配实战指南》
    41
  • 2
    《Unity安卓开发密钥管理全流程实战指南》
    35
  • 3
    租用阿里云服务器一个月多少钱？看完吓一跳，这么便宜了吗？
    58
  • 4
    基于微信小程序的防诈骗管理系统
    57
  • 5
    从零开始：用Python和Gemini 3四步搭建你自己的AI Agent
    74
  • 6
    云安全自动化：当攻击来敲门，我们用代码说“不”
    55
  • 7
    监控体系大一统：OpenTelemetry 就是运维人的“鸿蒙”
    58
  • 8
    到底该选谁？Hadoop、Spark、Flink、云大数据的“江湖全景图”
    44
  • 9
    jdguiwindows.rar使用步骤 手把手教你打开看jar包（附安装包）
    36
  • 10
    NeurlPS 2025！多伦多大学TIRE助力3D/4D 生成精准保留主体身份
    46

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    阿里云负载均衡收费标准：ALB、NLB和CLB价格，包括LCU费用、实例费和公网带宽价格