C语言实例_双向链表增删改查

一、双向链表介绍

双向链表（Doubly Linked List）是一种常见的数据结构，在单链表的基础上增加了向前遍历的功能。与单向链表不同，双向链表的每个节点除了包含指向下一个节点的指针外，还包含指向前一个节点的指针。

image-20230629101812768

image-20230629101952404

作用和原理：

（1）插入和删除操作：由于双向链表中每个节点都有指向前一个节点的指针，所以在双向链表中进行插入或删除操作时，相对于单向链表更加高效。可以通过修改前后节点的指针来完成插入和删除，而无需遍历链表。

（2）双向遍历：双向链表支持从头部到尾部以及从尾部到头部的双向遍历。这在某些场景下非常有用，例如需要反向查找、删除最后一个节点等。

（3）增加了灵活性：由于每个节点都具有指向前一个节点和后一个节点的指针，双向链表在某些特定场景下更灵活。例如，需要在链表中间插入或删除节点，或者需要修改前一个节点的信息。

双向链表的原理很简单。每个节点由数据域和两个指针组成，其中一个指针指向前一个节点，一个指针指向后一个节点。头节点指向链表的第一个节点，尾节点指向链表的最后一个节点。通过调整节点之间的指针，可以在双向链表中执行插入、删除和遍历等操作。

使用场景：

（1）编辑器中的撤销和重做功能：双向链表可以用于实现撤销和重做功能，每次编辑操作都将其结果存储为一个节点，并使用指针链接起来。通过双向链表，可以方便地在撤销和重做之间进行切换。

（2）浏览器的导航历史：浏览器的导航历史可以使用双向链表来保存已访问的页面，每个页面作为一个节点，并使用指针链接起来，以便进行前进和后退操作。

（3）实现LRU缓存替换算法：LRU缓存中，最近最少使用的数据被淘汰，可以使用双向链表来维护缓存中的数据，最近访问的数据位于链表的头部，最久未访问的数据位于链表的尾部。

（4）实现双向队列：双向链表可以用于实现双向队列（Dequeue），支持在队列的两端进行插入和删除操作。

双向链表提供了更多的灵活性和功能，特别是当需要在双向遍历、频繁的插入和删除操作等场景下使用。在许多常见的数据结构和算法中都有广泛的应用。

二、代码实现

以下是使用C语言实现的完整双向链表代码，包含了链表的创建、增加、删除、修改、排序和插入等功能。代码中封装了一套完整的子函数，以方便使用。

#include <stdio.h>
#include <stdlib.h>// 双向链表节点结构
typedef struct Node {int data;              // 数据域struct Node* prev;     // 指向前一个节点的指针struct Node* next;     // 指向后一个节点的指针
} Node;// 创建新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("Failed to allocate memory for new node\n");return NULL;}newNode->data = data;newNode->prev = NULL;newNode->next = NULL;return newNode;
}// 在链表末尾添加节点
void append(Node** head, int data) {Node* newNode = createNode(data);if (newNode == NULL) {return;}if (*head == NULL) {*head = newNode;} else {Node* current = *head;while (current->next != NULL) {    // 找到链表末尾current = current->next;}current->next = newNode;newNode->prev = current;}
}// 在链表头部添加节点
void prepend(Node** head, int data) {Node* newNode = createNode(data);if (newNode == NULL) {return;}if (*head == NULL) {*head = newNode;} else {newNode->next = *head;(*head)->prev = newNode;*head = newNode;}
}// 在指定位置插入节点
void insert(Node** head, int data, int position) {if (position < 0) {printf("Invalid position\n");return;}if (position == 0) {prepend(head, data);return;}Node* newNode = createNode(data);if (newNode == NULL) {return;}Node* current = *head;int count = 0;while (count < (position - 1) && current != NULL) {    // 找到插入位置前一个节点current = current->next;count++;}if (current == NULL) {printf("Invalid position\n");free(newNode);return;}newNode->next = current->next;newNode->prev = current;if (current->next != NULL) {current->next->prev = newNode;}current->next = newNode;
}// 删除指定位置的节点
void removeAt(Node** head, int position) {if (*head == NULL) {printf("List is empty\n");return;}if (position < 0) {printf("Invalid position\n");return;}Node* current = *head;int count = 0;if (position == 0) {*head = current->next;if (*head != NULL) {(*head)->prev = NULL;}free(current);return;}while (count < position && current != NULL) {    // 找到要删除的节点current = current->next;count++;}if (current == NULL) {printf("Invalid position\n");return;}current->prev->next = current->next;if (current->next != NULL) {current->next->prev = current->prev;}free(current);
}// 修改指定位置的节点值
void modify(Node* head, int position, int data) {Node* current = head;int count = 0;while (count < position && current != NULL) {    // 找到要修改的节点current = current->next;count++;}if (current == NULL) {printf("Invalid position\n");return;}current->data = data;
}// 对链表进行排序
void sort(Node** head) {if (*head == NULL) {printf("List is empty\n");return;}Node* current = *head;Node* temp = NULL;int swapped;do {swapped = 0;current = *head;while (current->next != NULL) {if (current->data > current->next->data) {int tmp = current->data;current->data = current->next->data;current->next->data = tmp;swapped = 1;}current = current->next;}temp = current;} while (swapped);
}// 打印链表
void printList(Node* head) {if (head == NULL) {printf("List is empty\n");return;}Node* current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}// 释放链表内存
void freeList(Node** head) {if (*head == NULL) {return;}Node* current = *head;Node* next = NULL;while (current != NULL) {next = current->next;free(current);current = next;}*head = NULL;
}int main() {Node* head = NULL;append(&head, 5);append(&head, 3);prepend(&head, 9);insert(&head, 7, 1);removeAt(&head, 2);modify(head, 0, 2);sort(&head);printList(head);freeList(&head);return 0;
}

代码里实现了创建双向链表、在链表末尾添加节点、在链表头部添加节点、在指定位置插入节点、删除指定位置的节点、修改指定位置的节点值、对链表进行排序、打印链表及释放链表内存等功能。

三、思路讲解

代码里定义了一个双向链表节点结构，包含数据域（data）、指向前一个节点的指针（prev）和指向后一个节点的指针（next）。

typedef struct Node {int data;struct Node* prev;struct Node* next;
} Node;

（1）createNode函数用于创建新节点。分配内存以存储节点，并检查内存分配是否成功。设置节点的数据域为传入的数据，并将前一个节点和后一个节点的指针都设置为NULL。最后，返回新创建的节点的指针。

（2）append函数用于在链表末尾添加节点。首先调用createNode函数创建一个新节点。如果头节点为空，则将新节点设置为头节点。否则，遍历链表直到找到最后一个节点，将新节点连接到最后一个节点的下一个位置，并设置新节点的prev指针指向最后一个节点。

（3）prepend函数用于在链表头部添加节点。首先，调用createNode函数创建一个新节点。如果头节点为空，则将新节点设置为头节点。否则，将新节点的next指针指向当前的头节点，将当前头节点的prev指针指向新节点，然后将新节点设置为头节点。

（4）insert函数用于在指定位置插入节点。首先，检查插入位置是否合法。如果插入位置为0，则调用prepend函数在链表头部插入节点。否则，调用createNode函数创建一个新节点，然后遍历链表直到找到插入位置前一个节点，将新节点插入到这两个节点之间，即将新节点的next指针指向前一个节点的next指针所指向的节点，将新节点的prev指针指向前一个节点，然后更新新节点两侧节点的指针。

（5）removeAt函数用于删除指定位置的节点。首先，检查链表是否为空。如果链表为空，则输出相应的提示信息。如果要删除的位置为0，即删除头节点，需要特殊处理，即将头节点的下一个节点设置为新的头节点，并将新的头节点的prev指针设置为NULL。否则，遍历链表直到找到要删除的节点，将要删除节点的前一个节点的next指针指向要删除节点的下一个节点，然后更新两侧节点的指针。

（6）modify函数用于修改指定位置的节点值。首先，遍历链表直到找到要修改的节点，然后将该节点的数据域设置为传入的新数据。

（7）sort函数用于对链表进行排序。首先，检查链表是否为空。如果链表为空，则输出相应的提示信息。使用冒泡排序算法，重复遍历链表并比较相邻节点的值，如果前一个节点的值大于后一个节点的值，则交换它们的值。重复此过程，直到链表没有发生交换为止。

（8）printList函数用于打印链表中的所有节点的值。首先，检查链表是否为空。如果链表为空，则输出相应的提示信息。遍历链表的每个节点，并输出节点中存储的数据。

（9）freeList函数用于释放链表的内存。首先，检查链表是否为空。如果链表为空，则直接返回。遍历链表的每个节点，使用free函数释放节点的内存，并将节点指针设为NULL，最后将头节点指针设为NULL。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/104385.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Docker之Compose

Docker之Compose

目录 前言 一、Docker-compose概述 1.1Docker Swarm与Docker Compose 1.1.1Docker Swarm 1.1.2Docker Compose 1.1.2.1 三层容器 ​编辑 二、YAML 2.1YAML概述 2.2注意事项 2.3Docker Compose 环境安装 2.3.1下载 三、Docker-Compose配置常用字段 四、Docker-com…
阅读更多...
高手进阶之路---pyqt自定义信号

高手进阶之路---pyqt自定义信号

高手进阶之路—pyqt自定义信号 1.思考问题为什么要自定义信号&#xff0c;qt5本身已有信号槽函数 # pushButton 被clicked的时候connect 函数print self.pushButton.clicked.connect(self.print)def print(self):print("我被点击了")或者使用 # 需要引入 pyqtSlo…
阅读更多...
C#__自定义类传输数据和前台线程和后台线程

C#__自定义类传输数据和前台线程和后台线程

// 前台线程和后台线程 // 默认情况下&#xff0c;用Thread类创建的线程是前台线程。线程池中的线程总是后台线程。 // 用Thread类创建线程的时候&#xff0c;可以设置IsBackground属性&#xff0c;表示一个后台线程。 // 前台线程在主函数运行结束后依旧执行&#xff0c;后台线…
阅读更多...
基于DolphinScheduler的调度流程梳理及落地实践

基于DolphinScheduler的调度流程梳理及落地实践

目 录 01 背景‍ 02 主流调度引擎 ‍‍‍‍‍‍‍ 03 DolphinScheduler核心概念及调度过程‍‍‍‍‍‍ 04 开发实践 01‍ 背景‍‍ 随着数据中台概念及相关技术逐渐成熟、落地&#xff0c;不断有企业将其应用到自身业务中&#xff0c;将原本分散的各系统数据进行整合、分析…
阅读更多...
JavaWeb_LeadNews_Day7-ElasticSearch, Mongodb

JavaWeb_LeadNews_Day7-ElasticSearch, Mongodb

JavaWeb_LeadNews_Day7-ElasticSearch, Mongodb elasticsearch安装配置 app文章搜索创建索引库app文章搜索思路分析具体实现 新增文章创建索引思路分析具体实现 MongoDB安装配置SpringBoot集成MongoDB app文章搜索记录保存搜索记录思路分析具体实现 查询搜索历史删除搜索历史 搜…
阅读更多...
三个视角解读ChatGPT在教学创新中的应用

三个视角解读ChatGPT在教学创新中的应用

第一&#xff0c;我们正处于一个学生使用ChatGPT等AI工具完成作业的时代&#xff0c;传统的教育方法需要适应变化。 教育工作者不应该因为学生利用了先进技术而惩罚他们&#xff0c;相反&#xff0c;应该专注于让学生去挑战超越AI能力范围的任务。这需要我们重新思考教育策略和…
阅读更多...
安卓系列机型永久去除data分区加密 详细步骤解析

安卓系列机型永久去除data分区加密 详细步骤解析

安卓机型玩机搞机刷写第三方twrp存储出现乱码 存储不显示等情况都是没有解密data分区的原因。用户需要在twrp里格式化data分区重启后存储显示正常。那么这个操作后你的数据分区就会呗彻底清除。 今天主要解析下如何操作可以永久解密data分区。其实data分区加密原则上也是厂商为…
阅读更多...
Kaggle回归问题Mercedes——Benz Greener Manufacturing

Kaggle回归问题Mercedes——Benz Greener Manufacturing

目录 前言1 题目介绍2 数据清洗3 数据可视化分析4 模型训练5 源码 前言 这是我在大三选修课的课程设计&#xff0c;内容参考了Kaggle上高赞的代码&#xff0c;有详细批注&#xff0c;整体比较基础&#xff0c;结构相对完整&#xff0c;便于初学者学习。这个是一个回归问题&…
阅读更多...
webscoket在vue中的使用

webscoket在vue中的使用

项目场景&#xff1a; 提示&#xff1a;项目相关背景&#xff1a; 什么是webscoket&#xff1f;: WebSocket是一种计算机通信协议&#xff0c;通过单个TCP连接提供全双工通信信道。实现了web客户端和服务器之间的实时通信&#xff0c;与传统的HTTP连接相比&#xff0c;允许以…
阅读更多...
设计模式笔记

设计模式笔记

工厂模式&#xff1a; 1.Simple Factory Pattern : 是指由一个工厂对象决定创建出哪一种产品类的实例&#xff0c;简单工厂是产品的工厂&#xff0c;工厂类负责创建的对象较少&#xff0c;客户端需要传入工厂类的参数&#xff0c;对于如何创建对象的逻辑不关心。 缺点&#xf…
阅读更多...
Unity3d：GameFramework解析：实体，对象池，资源管理，获取计数，引用计数，自动释放

Unity3d：GameFramework解析：实体，对象池，资源管理，获取计数，引用计数，自动释放

基本概念 1.GF万物基于引用池IReference 2.ObjectBase : IReference类的m_Target持有unity中Mono&#xff0c;资源&#xff0c;GameObejct 3.AssetObject : ObjectBase类m_Target持有Assetbundle中的Asset&#xff0c;具有获取&#xff0c;引用两个计数管理释放 4.ResourceObj…
阅读更多...
线索二叉树——找前驱、后继

线索二叉树——找前驱、后继

前言 一个二叉树被线索化之后&#xff0c;一个节点的前驱或后继会存在两种情况&#xff0c; 1、tag1&#xff0c;有明确的线索化前驱或后继&#xff0c; 2、tag0&#xff0c;只存在左右孩子&#xff0c;但是没用明确的线索化前驱后继&#xff0c;需要分析 //线索二叉树结点定义…
阅读更多...
如何将PC电脑变成web服务器：将内网主机映射到外网实现远程访问

如何将PC电脑变成web服务器：将内网主机映射到外网实现远程访问

如何将PC电脑变成web服务器&#xff1a;将内网主机映射到外网实现远程访问 我是艾西&#xff0c;今天跟大家分享内容还是比较多人问的一个问题&#xff1a;如何将PC电脑变成web服务器。内网主机作为web服务器&#xff0c;内容包括本地内网映射、多层内网映射解决方案、绕过电信…
阅读更多...
Linux socket网络编程概述 和 相关API讲解

Linux socket网络编程概述 和 相关API讲解

socket网络编程的步骤 大体上&#xff0c;连接的建立过程就是&#xff1a;服务器在确定协议类型后&#xff0c;向外广播IP地址和端口号&#xff0c;并监听等待&#xff0c;直到客户端获取了IP地址和端口号并成功连接&#xff1a; 使用socket来进行tcp协议的网络编程的大体步骤…
阅读更多...
创邻科技张晨：图数据库，激活数据要素的新基建

创邻科技张晨：图数据库，激活数据要素的新基建

“数据经济时代&#xff0c;数据要素产业链的各细分领域均蕴含机遇&#xff0c;图技术作为网络协同和数据智能的底层发动机&#xff0c;将深度掘金数字中国价值潜能”。 8月22日&#xff0c;在2023中国&#xff08;南京&#xff09;国际软件产品和信息服务交易博览会的信息技术…
阅读更多...
操作系统期末考试复习——简答题总结

操作系统期末考试复习——简答题总结

最近考研在复习OS&#xff0c;顺便把大二期末考试的简答题整理了一下~ 1、操作系统的定义 “操作系统&#xff08;operating system&#xff0c;简称OS&#xff09;是管理计算机硬件与软件资源的计算机程序 2、操作系统的基本类型及特征 批处理操作系统、分时操作系统、实时…
阅读更多...
400电话系统如何进行数据分析和优化？

400电话系统如何进行数据分析和优化？

400电话系统可以通过以下方式进行数据分析和优化&#xff1a; 呼叫记录&#xff1a;400电话系统会记录每一次呼叫的相关信息&#xff0c;包括呼叫时间、呼叫持续时间、呼叫地点等。通过分析呼叫记录&#xff0c;企业可以了解客户的呼叫习惯和行为模式&#xff0c;如高峰时段、呼…
阅读更多...
新唐Nuc980学习笔记1 - 工程创建和下载

新唐Nuc980学习笔记1 - 工程创建和下载

一、新唐nuc980 新唐nuc980 iot开发板是Linux 工业物联网开发平台&#xff0c;新唐科技提供工业物联网开发平台采用 NUC980DK 微处理器&#xff0c;此为一套完整的工业用物联网开平台&#xff0c;包含了完整的硬件设计与软件参考设计。包含了新唐执行速度 300 MHz 的 ARM9 MPU …
阅读更多...
idea的debug断点的使用

idea的debug断点的使用

添加断点&#xff08;目前不知道如何添加断点&#xff0c;就给AutoConfigurationImportSelector的每个方法都加上断点&#xff09;&#xff1a; 然后将StockApplication启动类以debug方式运行&#xff0c;然后程序就会停在119行 点击上边的step over让程序往下运行一行&#x…
阅读更多...
有效降低传导辐射干扰

有效降低传导辐射干扰

一直以来&#xff0c;设计中的电磁干扰&#xff08;EMI&#xff09;问题十分令人头疼&#xff0c;尤其是在汽车领域。为了尽可能的减小电磁干扰&#xff0c;设计人员通常会在设计原理图和绘制布局时&#xff0c;通过降低高di / dt的环路面积以及开关转换速率来减小噪声源。 但…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023