Hello·World
划水湾
问道台
卷王殿
藏经阁
APP
目录
(08)王道数据结构-单链表插入和删除

按位序插入

带头节点

C
复制代码 
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {      //定义单链表结构
    int data;               //每个节点存放一个数据
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);

int main(void) {
    LinkList L;
    InitList(L);
    if (Empty(L)) {
        printf("链表为空!\n");
    }

    ListInsert(L, 1, 11);
    ListInsert(L, 2, 22);
    ListInsert(L, 3, 33);
    ListInsert(L, 4, 44);
    ListInsert(L, 5, 55);
    ListInsert(L, 6, 66);
    ListInsert(L, 7, 77); 
    ListInsert(L, 8, 88);

    if (!Empty(L)) {
        printf("插入成功！");
    }
    return 0;
}

//初始化空的单链表
bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));   //分配头结点
    if (L == NULL) {    //内存不足，分配失败
        return false;
    }
    L->next = NULL;     //头结点之后暂时没有节点
    return true;
}

//判断单链表是否为空（带头结点）
bool Empty(LinkList L) {
    if (L->next == NULL) {
        return true;
    } else {
        return false;
    }
}
//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
        printf("插入失败!\n");
    }
    LNode *p;   //指针p指向当前扫描到的节点
    int j = 0;  //当前p指向的是第几个节点
    p = L;      //L指向头结点，头结点是第0个节点（不存数据）
    while (p != NULL && j < i-1) {      //循环找到第i-1个节点
        p = p->next;
        j++;
    }
    if (p == NULL) {    //i值不合法
        return false;
        printf("插入失败!\n");
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;        //将节点s连接到p之后
    return true;        //插入成功
}

不带头结点

C
复制代码 
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {      //定义单链表结构
    int data;               //每个节点存放一个数据
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
int main(void) {
    LinkList L;
    InitList(L);
    if (Empty(L)) {
        printf("链表为空!\n");
    }

    ListInsert(L, 1, 11);
    ListInsert(L, 2, 22);
    ListInsert(L, 3, 33);
    ListInsert(L, 4, 44);
    ListInsert(L, 5, 55);
    ListInsert(L, 6, 66);
    ListInsert(L, 7, 77); 
    ListInsert(L, 8, 88);

    if (!Empty(L)) {
        printf("插入成功！");
    }
    return 0;
}

//初始化空的单链表
bool InitList(LinkList &L) {
    L = NULL;   //空表，暂时没有任何节点
    return true;
}

//判断单链表是否为空
bool Empty(LinkList L) {
    return (L==NULL);
}

bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
        printf("插入失败!\n");
    }
    if (i == 1) {   //插入第1个节点的操作与其他节点操作不同
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;      //头指针指向新的节点
        return true;
    }
    LNode *p;   //指针p指向当前扫描到的节点
    int j = 1;  //当前p指向的是第几个节点
    p = L;      //p指向第1个节点（非头节点）
    while (p != NULL && j < i -1 ) {    //循环找到第i-1个节点
        p = p->next;
        j++;
    }

    if (p == NULL) {    //i值不合法
        return false;
        printf("插入失败!\n");
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;        //将节点s连接到p之后
    return true;        //插入成功
}

后插操作

C
复制代码 
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {      //定义单链表结构
    int data;               //每个节点存放一个数据
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
bool InsertNextNode(LNode *p, int e);
int main(void) {
    LinkList L;
    InitList(L);
    if (Empty(L)) {
        printf("链表为空!\n");
    }

    ListInsert(L, 1, 11);
    ListInsert(L, 2, 22);
    ListInsert(L, 3, 33);
    ListInsert(L, 4, 44);
    ListInsert(L, 5, 55);
    ListInsert(L, 6, 66);
    ListInsert(L, 7, 77); 
    ListInsert(L, 8, 88);

    if (!Empty(L)) {
        printf("插入成功！");
    }
    return 0;
}

//初始化空的单链表
bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));   //分配头结点
    if (L == NULL) {    //内存不足，分配失败
        return false;
    }
    L->next = NULL;     //头结点之后暂时没有节点
    return true;
}

//判断单链表是否为空（带头结点）
bool Empty(LinkList L) {
    if (L->next == NULL) {
        return true;
    } else {
        return false;
    }
}
//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
        printf("插入失败!\n");
    }
    LNode *p;   //指针p指向当前扫描到的节点
    int j = 0;  //当前p指向的是第几个节点
    p = L;      //L指向头结点，头结点是第0个节点（不存数据）
    while (p != NULL && j < i-1) {      //循环找到第i-1个节点
        p = p->next;
        j++;
    }
    return InsertNextNode(p,e);
}
//后插操作：在p节点之后插入元素e
bool InsertNextNode(LNode *p, int e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {    //内存分配失败
        return false;
    }
    s->data = e;    //用节点s保存数据元素e
    s->next = p->next;
    p->next = s;
    return true;
}

前插操作

C
复制代码 
//前插操作：在p节点之前插入元素e
bool InsertPriorNode(LNode *p, int e) {
    if (p == NULL) {
        return false;
    } 
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {    //内存分配失败
        return false;
    }
    s->next = p->next;
    p->next = s;        //新节点s连在p之后
    s->data = p->data;
    p->data = e;
    return true;
}

bool InsertPriorNode(LNode *p, LNode *s) {
    if (p == NULL) {
        return false;
    } 
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {    //内存分配失败
        return false;
    }
    s->next = p->next;
    p->next = s;        //新节点s连在p之后
    s->data = p->data;
    p->data = e;
    return true;
}

按位序删除

带头结点

C
复制代码 
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {      //定义单链表结构
    int data;               //每个节点存放一个数据
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
bool ListDelete(LinkList &L, int i, int &e);
int main(void) {
    LinkList L;
    InitList(L);
    if (Empty(L)) {
        printf("链表为空!\n");
    }

    ListInsert(L, 1, 11);
    ListInsert(L, 2, 22);
    ListInsert(L, 3, 33);
    ListInsert(L, 4, 44);
    ListInsert(L, 5, 55);
    ListInsert(L, 6, 66);
    ListInsert(L, 7, 77); 
    ListInsert(L, 8, 88);

    if (!Empty(L)) {
        printf("插入成功！");
    }

    int e = 0;
    ListDelete(L, 8, e);

    return 0;
}

//初始化空的单链表
bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));   //分配头结点
    if (L == NULL) {    //内存不足，分配失败
        return false;
    }
    L->next = NULL;     //头结点之后暂时没有节点
    return true;
}

//判断单链表是否为空（带头结点）
bool Empty(LinkList L) {
    if (L->next == NULL) {
        return true;
    } else {
        return false;
    }
}
//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
        printf("插入失败!\n");
    }
    LNode *p;   //指针p指向当前扫描到的节点
    int j = 0;  //当前p指向的是第几个节点
    p = L;      //L指向头结点，头结点是第0个节点（不存数据）
    while (p != NULL && j < i-1) {      //循环找到第i-1个节点
        p = p->next;
        j++;
    }
    if (p == NULL) {    //i值不合法
        return false;
        printf("插入失败!\n");
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;        //将节点s连接到p之后
    return true;        //插入成功
}
//按位序删除：带头结点
bool ListDelete(LinkList &L, int i, int &e) {
    if (i < 1) {
        return false;
    }
    LNode *p;       //指针p指向当前扫描到的节点
    int j = 0;      //当前p指向的是第几个节点
    p = L;          //L指向头结点，头结点是第0个节点（不存数据）
    while(p != NULL && j < i-1) {   //循环找到第i-1个节点
        p = p->next;
        j++;
    }

    if (p==NULL) {  //i值不合法
        return false;
    }
    if (p->next == NULL) {  //第i-1个节点之后已无其他节点
        return false;
    }
    LNode *q = p->next;     //令p指向被删除节点
    e = q->data;            //用e返回元素的值
    p->next = q->next;      //将*q节点从链中“断开”
    free(q);
    return true;
}

注意事项： 这里没有写查找功能，无法验证是否删除成功，留在下一节查找功能验证！

C
复制代码 
//删除指定节点p
bool DeleteNode(LNode *p) {
    if (p==NULL) {
        return false;
    }
    LNode *q = p->next;         //令q指向*p的后继节点
    p->data = p->next->data;    //和后继节点交换数据域
    p->next = q->next;
    free(q);
    return true;
}

其中时间复杂度为O(1)

本文由 Robin 原创发布于 阳光沙滩 ， 未经作者授权，禁止转载
评论
0 / 1024
推荐文章
linux服务器的日志、容器清理
本手册提供了一套全面的Linux服务器磁盘清理与排查方法，帮助用户高效管理磁盘空间。通过查看磁盘使用情况、分析Docker占用、清理无用容器和日志，确保系统运行流畅。适合需要优化服务器性能的运维人员参考。
Archer39点赞
记给网站接入图形验证码
本文分享了如何为个人站点添加图形验证码以提升安全性，详细介绍了使用第三方接口实现验证码功能的过程，并通过代码示例展示了具体实现方式。对于关注网站安全的开发者来说，这篇文章提供了实用的参考价值。
东子1041
Java开发环境搭建
本文是一份详细的Java开发环境搭建指南，涵盖了Java的发展历史、版本选择及安装配置过程。无论你是初学者还是有经验的开发者，都能从中找到实用的信息和步骤，帮助你快速上手Java开发。
拉大锯841
Vue3.js项目的创建
本文详细介绍了如何使用Vue3创建项目，包括Node.js的安装和配置，以及项目的初始化过程。适合初学者学习如何快速搭建Vue3开发环境，并推荐了相关课程供进一步学习。
拉大锯108点赞
Network Tools : 您的运维“助手”升级了
Network Tools是一款专为解决运维难题而设计的软件，集设备管理、配置备份、性能监控和告警处理于一体。通过统一的工作台，帮助运维人员更高效地管理资产、定位故障并提升团队协作效率。无论是设备在线状态还是具体问题排查，都能得到全面支持。
南城阿宇1392
Ubuntu 软件安装与彻底卸载指南
本文详细介绍了在 Ubuntu 系统中如何规范安装和彻底卸载 .deb 格式软件，包括依赖修复、残留清理以及图形化工具推荐，适合需要维护系统环境的用户。
南城阿宇1461
JavaWeb开发客户程序更新特殊环境下的骚操作
本文分享了在无外网环境下，如何利用Docker和docker-compose实现高效部署的实战经验。通过基础镜像和本地jar包挂载的方式，解决了内网环境下的依赖问题，适合需要灵活部署方案的技术人员参考。
拉大锯93点赞
Linux 防火墙完全指南：从原理到多发行版实战
本文全面解析Linux防火墙的底层原理与主流工具配置，涵盖UFW、firewalld、iptables、nftables等方案，适合不同发行版用户。从基础概念到生产环境加固建议，助你掌握核心安全策略，确保服务器与网络的安全运行。
拉大锯3001
水上派对英语单词篇
探索FLOATOPIA水上派对的完整指南，涵盖签到流程、场地指引、安全须知、活动安排及夜场舞会等实用英语词汇与对话。无论是初学者还是老手，都能轻松掌握关键术语，享受完美水上体验。
拉大锯206点赞
麒麟操作系统下使用 virt-customize 重置虚拟机 root 密码实战
本文详细介绍了在麒麟操作系统环境下使用 virt-customize 工具重置 KVM 虚拟机 root 密码的完整流程，包含安装步骤、常见问题及解决方案，帮助运维人员高效处理密码遗忘或批量初始化场景，避免数据丢失。
拉大锯1861
浅析JS预编译-函数篇
本文详细讲解了JavaScript中函数的预编译过程，包括AO对象的创建、变量和函数声明的提升，以及执行阶段的变化。适合初学者了解JS执行机制，帮助深入理解代码运行逻辑。
东子1991
访问Github的另一种姿势
本文介绍了如何通过Watt ToolKit等工具加速访问Github，适合对网络技术感兴趣的读者。内容涵盖工具介绍、下载和使用方法，以及一些实用技巧，值得一看。
东子2562
使用Gulp压缩JS
本文详细介绍了如何使用Gulp压缩JavaScript文件，特别是支持ES6语法的处理方法。通过实际操作和效果对比，帮助开发者提升代码性能，适合对前端自动化工具感兴趣的读者。
东子2131
使用Gulp压缩CSS
本文详细介绍了如何使用Gulp工具对CSS文件进行压缩，提升网页加载速度。适合需要优化静态资源的开发者，提供清晰的步骤和示例，帮助快速上手。
东子2081
从0部署Nuxtjs项目
本文详细介绍了如何将Nuxt.js项目部署到公网，涵盖Node.js安装、环境配置、源码上传及使用PM2启动服务的全过程，适合开发者学习和实践。
东子2532
Linux 命令行美化利器：tree 命令完全指南（安装 + 全部参数详解）
掌握 Linux 下的 `tree` 命令，快速直观地查看目录结构。本文详细讲解安装方法、参数含义及实战场景，适合开发者和系统管理员提升工作效率。
拉大锯2351
Linux常用命令（一）
本文详细介绍了Linux基础命令，包括文件操作、系统显示、网络状态、软件包管理等，适合初学者学习和查阅，是掌握Linux系统的实用指南。
东子2342
大模型推理参数解码：温度、Top-p 与核采样如何塑造生成文本的灵魂
探索大语言模型的采样参数如何塑造生成内容，从温度到Top-p，从惩罚机制到熵控制，揭示背后的信息论原理与实践策略。了解如何通过参数调优，让AI既保持知识的严谨，又拥有创造力的自由。
拉大锯219点赞
记从0使用Claude code写代码
本文介绍了如何使用Claude Code搭配DeepSeek进行编程，详细讲解了安装Node.js、全局安装Claude、配置模型以及使用方法。对于开发者来说，这是一份实用的技术教程，尤其适合对AI编程工具感兴趣的读者。
东子2691
Android-Studio-Gradle同步失败-Library为null的通用排查指南
遇到 Android Studio Gradle Sync 失败时，不要轻易删除全局缓存。本文详细解析了错误原因，并提供了一系列精准的排查步骤和解决方案，帮助开发者快速定位并解决问题，提升开发效率。
A lonely cat4642
PHP实现密码加密
本文详细介绍了Bcrypt密码加密技术及其在PHP中的应用，帮助开发者提升用户密码的安全性。通过实际代码示例，展示了如何使用password_hash和password_verify函数进行密码加密与验证，是学习网络安全知识的实用指南。
东子2511
WordCloud效果，滚动标签
本文详细介绍了如何在Vue项目中集成WordCloud组件，包括依赖安装、属性配置和使用方法。适合开发者学习如何实现数据可视化功能，提升项目交互体验。
拉大锯320点赞
从0使用WordPress搭建一个优美的网站
本文详细介绍了如何使用WordPress搭建一个美观的网站，从安装到主题配置和功能拓展，为读者提供了实用的操作指南。无论是初学者还是有一定经验的开发者，都能从中获得有价值的参考。
东子3051
JS实现在网站底部添加运行时间
想知道如何在网站底部显示运行时间？本文详细讲解了通过JavaScript实现这一功能的方法，包括时间计算逻辑和代码实现。适合前端开发者学习参考，轻松为网站添加实用功能。
东子2471
在Vercel上部署Hexo博客
本文详细介绍了如何在Vercel上快速部署Hexo博客，无需后端服务即可实现高效发布。相比传统方式，省去了手动生成和上传静态文件的步骤，更加便捷。适合想要搭建个人博客的开发者参考。
东子2561
从0搭建一个Hexo博客
本文详细介绍了Hexo博客框架的使用方法，从安装到部署全流程讲解，适合想快速搭建个人博客的技术爱好者。内容清晰易懂，是入门Hexo的理想指南。
东子265点赞
离线设备激活方案：古老的 Windows 光盘激活，离线算法授权等
本文深入解析了离线激活的核心原理与实现方式，从历史案例到现代技术，全面剖析了如何在无网络环境下确保软件授权的安全性。通过设备指纹、授权文件校验等手段，为开发者提供了可复用的架构设计思路，适用于工业、医疗等对网络依赖较低的场景。
拉大锯396点赞
Hexo实现生成站点地图
想为你的Hexo博客添加站点地图功能吗？本文详细介绍了如何通过安装插件和配置文件来实现，适合没有内置该功能的新主题或自定义主题的用户。简单步骤助你提升搜索引擎优化效果。
东子2042
Hexo实现代码压缩
本文分享了如何通过Hexo插件优化博客性能，详细介绍了安装和配置过程，帮助提升网页加载速度。适合对网站优化感兴趣的开发者阅读。
东子2481
记一次 GitHub 幽灵协作者大清洗：强制重写 Git 历史与穿透 CDN 缓存实践
本文详细讲解了如何解决GitHub上出现的‘幽灵协作者’问题，通过重写Git历史和穿透CDN缓存，彻底清理错误提交记录。适合开发者学习如何高效管理项目历史与优化仓库信息。
A lonely cat3061
1
本网站由程序猿(媛)用爱驱动 Copyright©阳光沙滩(0x07DE-0x07E9)
Design by ZengXue in Guangzhou and code by great TrillGates in Shenzhen