当前位置: 首页 > news >正文

【数据结构C/C++】双向链表的增删改查

文章目录

  • C
  • C++
  • 408考研各数据结构C/C++代码(Continually updating)

对我个人而言,在开发过程中使用的比较多的就是双向链表了。
很多重要的代码优化都会使用到基于双向链表实现的数据机构。
比如我们常用的HashMap,我们知道Key其实是无序存放的,
而LinkedHashMap底层使用HashMap+双向链表的方式实现了对key的有序遍历。

双向链表的一些重要特点和优点:

双向遍历:
双向链表具有两个指针,一个指向前一个节点(前驱),一个指向后一个节点(后继)。这使得在链表中的任何位置都可以轻松地进行双向遍历,而不仅仅是单向遍历。

前向和后向操作: 可以在双向链表中执行前向和后向操作,这意味着可以轻松地在链表中的任何位置插入、删除或修改节点。

插入和删除效率高: 相对于单向链表,双向链表在某些情况下可以更高效地进行插入和删除操作,因为可以通过两个方向的指针更快地访问前后节点。

反向遍历: 在某些情况下,需要以相反的顺序遍历链表。双向链表使得反向遍历变得容易,无需重新构建链表。

实现双端队列: 双向链表还可以用于实现双端队列(Deque),这是一种允许在两端进行插入和删除操作的数据结构。

尽管双向链表提供了上述优点,但也需要额外的内存来存储每个节点的前向指针,这会增加内存开销。此外,由于维护前向指针和后向指针的关系,代码的实现可能相对复杂一些。

双向链表相对于单链表的区别在于,单链表只有一个指向下一个节点的指针域,而双向链表有两个。因此再管理指针上,需要更多的去注意。
不过原理都大差不差,只不过是再添加和删除一个节点的时候,需要记住去管理当前节点的前后指针域,使得其最终依旧能连起来。
因此我认为在学习双向链表的时候,比较推荐先再草纸上画出大概的思路。
比如再链表中间某个位置添加一个元素,那么应该遍历到当前元素前一个位置就停下,然后去创建新节点,并且将新节点的前后指针域指向当前节点和当前节点的下一个节点。
以此类推,删除也差不多。
所以,继续 show u my code。

C

#include <stdio.h>
#include <stdlib.h>// 定义双向链表节点结构
struct Node {int data;struct Node* prev;struct Node* next;
};// 初始化双向链表
struct Node* initializeList() {return NULL; // 返回一个空链表
}// 在链表尾部插入节点
struct Node* insertAtEnd(struct Node* head, int data) {//开辟spacestruct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->next = NULL;if (head == NULL) {newNode->prev = NULL;return newNode; // 如果链表为空,新节点成为链表头}struct Node* current = head;while (current->next != NULL) {current = current->next; // 移动到链表末尾}current->next = newNode;newNode->prev = current;return head;
}// 在链表头部插入节点
struct Node* insertAtBeginning(struct Node* head, int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->next = head;newNode->prev = NULL;if (head != NULL) {head->prev = newNode;}return newNode; // 新节点成为链表头
}// 删除节点
struct Node* deleteNode(struct Node* head, int data) {if (head == NULL) {return NULL; // 空链表,无需删除}if (head->data == data) {struct Node* temp = head;head = head->next;if (head != NULL) {head->prev = NULL;}free(temp);return head; // 删除链表头节点}struct Node* current = head;while (current != NULL && current->data != data) {current = current->next;}if (current != NULL) {struct Node* prevNode = current->prev;struct Node* nextNode = current->next;if (prevNode != NULL) {prevNode->next = nextNode;}if (nextNode != NULL) {nextNode->prev = prevNode;}free(current); // 删除中间或末尾节点}return head;
}// 查找节点
struct Node* searchNode(struct Node* head, int data) {struct Node* current = head;while (current != NULL) {if (current->data == data) {return current; // 找到匹配的节点}current = current->next;}return NULL; // 未找到匹配的节点
}// 修改节点的数据
void modifyNode(struct Node* head, int oldData, int newData) {struct Node* nodeToModify = searchNode(head, oldData);if (nodeToModify != NULL) {nodeToModify->data = newData; // 修改节点的数据}
}// 打印链表(正向)
void printListForward(struct Node* head) {struct Node* current = head;while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");
}// 打印链表(反向)
void printListBackward(struct Node* tail) {struct Node* current = tail;while (current != NULL) {printf("%d -> ", current->data);current = current->prev;}printf("NULL\n");
}// 释放链表内存
void freeList(struct Node* head) {struct Node* current = head;while (current != NULL) {struct Node* temp = current;current = current->next;free(temp);}
}int main() {struct Node* list = initializeList();int choice, data, oldData, newData;while (1) {printf("\nMenu:\n");printf("1. Insert at the end\n");printf("2. Insert at the beginning\n");printf("3. Delete node\n");printf("4. Search node\n");printf("5. Modify node\n");printf("6. Print list forward\n");printf("7. Print list backward\n");printf("8. Exit\n");printf("Enter your choice: ");scanf("%d", &choice);switch (choice) {case 1:printf("Enter data to insert: ");scanf("%d", &data);list = insertAtEnd(list, data);break;case 2:printf("Enter data to insert: ");scanf("%d", &data);list = insertAtBeginning(list, data);break;case 3:printf("Enter data to delete: ");scanf("%d", &data);list = deleteNode(list, data);break;case 4:printf("Enter data to search: ");scanf("%d", &data);if (searchNode(list, data) != NULL) {printf("Found node with data %d\n", data);} else {printf("Node with data %d not found\n", data);}break;case 5:printf("Enter data to modify: ");scanf("%d", &oldData);printf("Enter new data: ");scanf("%d", &newData);modifyNode(list, oldData, newData);break;case 6:printf("List (forward): ");printListForward(list);break;case 7:printf("List (backward): ");printListBackward(list);break;case 8:freeList(list);exit(0);default:printf("Invalid choice! Please try again.\n");}}return 0;
}

C++

#include <iostream>// 定义双向链表节点结构
class Node {
public:int data;Node* prev;Node* next;Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};// 定义双向链表类
class DoublyLinkedList {
public:Node* head;DoublyLinkedList() : head(nullptr) {}// 插入节点到链表尾部void insertAtEnd(int val) {Node* newNode = new Node(val);if (head == nullptr) {head = newNode;} else {Node* current = head;while (current->next != nullptr) {current = current->next;}current->next = newNode;newNode->prev = current;}}// 删除节点void deleteNode(int val) {if (head == nullptr) {return; // 空链表,无需删除}Node* current = head;while (current != nullptr && current->data != val) {current = current->next;}if (current == nullptr) {return; // 未找到匹配的节点}if (current->prev != nullptr) {current->prev->next = current->next;} else {head = current->next;}if (current->next != nullptr) {current->next->prev = current->prev;}delete current;}// 查找节点Node* searchNode(int val) {Node* current = head;while (current != nullptr) {if (current->data == val) {return current; // 找到匹配的节点}current = current->next;}return nullptr; // 未找到匹配的节点}// 修改节点的数据void modifyNode(int oldVal, int newVal) {Node* nodeToModify = searchNode(oldVal);if (nodeToModify != nullptr) {nodeToModify->data = newVal; // 修改节点的数据}}// 打印链表void printList() {Node* current = head;while (current != nullptr) {std::cout << current->data << " <-> ";current = current->next;}std::cout << "nullptr" << std::endl;}// 释放链表内存~DoublyLinkedList() {Node* current = head;while (current != nullptr) {Node* temp = current;current = current->next;delete temp;}}
};int main() {DoublyLinkedList list;int choice, data, oldData, newData;while (true) {std::cout << "\nMenu:\n";std::cout << "1. Insert at the end\n";std::cout << "2. Delete node\n";std::cout << "3. Search node\n";std::cout << "4. Modify node\n";std::cout << "5. Print list\n";std::cout << "6. Exit\n";std::cout << "Enter your choice: ";std::cin >> choice;switch (choice) {case 1:std::cout << "Enter data to insert: ";std::cin >> data;list.insertAtEnd(data);break;case 2:std::cout << "Enter data to delete: ";std::cin >> data;list.deleteNode(data);break;case 3:std::cout << "Enter data to search: ";std::cin >> data;if (list.searchNode(data) != nullptr) {std::cout << "Found node with data " << data << std::endl;} else {std::cout << "Node with data " << data << " not found" << std::endl;}break;case 4:std::cout << "Enter data to modify: ";std::cin >> oldData;std::cout << "Enter new data: ";std::cin >> newData;list.modifyNode(oldData, newData);break;case 5:std::cout << "List: ";list.printList();break;case 6:return 0;default:std::cout << "Invalid choice! Please try again." << std::endl;}}return 0;
}

408考研各数据结构C/C++代码(Continually updating)

408考研各数据结构C/C++代码(Continually updating)
这个模块是我应一些朋友的需求,希望我能开一个专栏,专门提供考研408中各种常用的数据结构的代码,并且希望我附上比较完整的注释以及提供用户输入功能,ok,fine,这个专栏会一直更新,直到我认为没有新的数据结构可以讲解了。
目前我比较熟悉的数据结构如下:
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。
所以我会先有空更新出如下几个数据结构的代码,欢迎关注。 当然,在我前两年的博客中,对于链表、哈夫曼树等常用数据结构,我都提供了比较完整的详细的实现以及思路讲解,有兴趣可以去考古。

相关文章:

【数据结构C/C++】双向链表的增删改查

文章目录 CC408考研各数据结构C/C代码&#xff08;Continually updating&#xff09; 对我个人而言&#xff0c;在开发过程中使用的比较多的就是双向链表了。 很多重要的代码优化都会使用到基于双向链表实现的数据机构。 比如我们常用的HashMap&#xff0c;我们知道Key其实是无…...

Godot 添加Nuget 引用

前言 我的Godot 专栏 我在之前的文章中&#xff0c;解决了Visual Studio 如何去调试正在运行的Godot 程序。Godot 对于C# 的支持只剩下一个&#xff0c;那就是Nuget 添加。 Godot VisualStudio外部编辑器设置 添加Nuget Nuget 添加还是非常的容易的。我们直接添加一个最常用的…...

IC工程师职场必备《经典Verilog100多个代码案例》(附下载)

对于IC行业的人员而言&#xff0c;Verilog是最基础的入门&#xff0c;用于数字电路的系统设计&#xff0c;很多的岗位都会用到&#xff0c;可对算法级、门级、开关级等多种抽象设计层次进行建模。 Verilog由于其简单的语法&#xff0c;和C语言的相似性&#xff0c;目前被各大公…...

springboot项目做成公共项目

一&#xff1a;引言 最近碰到个需求&#xff0c;就是把我项目做成一个公共的提供jar包给别人使用&#xff0c;我也是捣鼓了一段时间去研究这个问题&#xff0c;这个东西其实就是A 项目提供jar包给B项目&#xff0c;B项目只要引入A项目的jar包就可以使用A项目的功能。 问题一&…...

RTC 时间、闹钟

实时时钟RTC是一个独立的定时器。RTC模块拥有一个连续计数的计数器&#xff0c;在软件配置下&#xff0c;可以提供时钟日历的功能。修改计数器的值可以重新设置当前时间和日期 RTC还包含用于管理低功耗模式的自动唤醒单元。 在掉电情况下 RTC仍可以独立运行 只要芯片的备用电源…...

【yolo系列:yolov7训练添加spd-conv】

系列文章目录 yolov7训练添加spd-conv 文章目录 系列文章目录一、spd-conv是什么&#xff1f;二、使用步骤1.第一步&#xff1a;先在models/common.py加上2.第二步&#xff1a;models/yolo.py加上2.第三步&#xff1a;修改yolov7的yaml文件 总结 提示&#xff1a;以下是本篇文…...

面向对象设计-UML六种箭头含义

目录 UML概述UML语义UML表示法 六种常用关系标识方法泛化实现依赖关联聚合组合 本文参考文章 https://blog.csdn.net/qq_25091281/article/details/123801862 UML概述 UML (Unified Modeling Language)为面向对象软件设计提供统一的、标准的、可视化的建模语言。适用于描述以…...

一本没有任何数学公式的自然语言处理入门书

ChatGPT 时代来了&#xff0c;AI 从旧时王谢堂前燕&#xff0c;飞入寻常百姓家。越来越多非 AI 领域 的软件开发者涌进 NLP(自然语言处理)领域。在这个快速发展的时代&#xff0c;如果这些软件开发 者要像读书那样先读 4 年本科、2 年硕士、3 年博士才能搞 AI&#xff0c;风口早…...

【数据结构C/C++】多维数组的原理、访问方式以及作用

文章目录 什么是多维数组&#xff1f;代码讲解使用方式为什么指针遍历的方式是这样子的&#xff1f;&#xff08;助你理解指针的含义&#xff09;使用场景408考研各数据结构C/C代码&#xff08;Continually updating&#xff09; 什么是多维数组&#xff1f; 在C语言中&#x…...

2023年中国烹饪机器人市场发展概况分析:整体规模较小,市场仍处于培育期[图]

烹饪机器人仍属于家用电器范畴&#xff0c;是烹饪小家电的进一步细分&#xff0c;它是烹饪小家电、人工智能和服务机器在厨房领域的融合。烹饪机器人是一种智能化厨房设备&#xff0c;可以根据预设的程序实现自动翻炒和烹饪&#xff0c;是多功能料理机和炒菜机结合的产物。 烹…...

Android原生实现控件选择背景变色方案(API28及以上)

Android控件点击/选择后控件背景变色的实现方式有很多种&#xff0c;例如使用selector的xml文件实现。这里介绍一下另一种Android原生的点击/选择实现方案&#xff08;API28及以上&#xff09;&#xff0c;也就是ColorStateListDrawable。 ColorStateListDrawable是一个可根据不…...

为什么要学C语言及C语言存在的意义

为什么要学C语言及C语言存在的意义 汇编生C&#xff0c;C生万物。linus说自己最喜欢的语言就是C语言&#xff0c;因为看到写出的代码就能想到对应的汇编码。一方面说明C语言足够简洁&#xff0c;没有像C中一样的复杂概念封装&#xff0c;另一方面也说明C语言足够的底层&#xf…...

数据结构——空间复杂度

空间复杂度&#xff0c;与算法运行时所需的内存空间有关。 默认问题规模为n。 举例案例&#xff0c;具体分析。 1.全是普通变量 2.一维数组 3.二维数组 4.递归--变量 不递归的时候空间复杂度是O(1)&#xff0c;递归的话递归n次&#xff0c;乘以n&#xff0c;所以空间复杂度…...

uniapp:swiper-demo效果

单元格轮播 <swiper class"swiper1" :circular"true" :autoplay"true" interval"3000" previous-margin"195rpx" next-margin"195rpx"><swiper-item v-for"(item,index) in 5" :key"inde…...

Graphviz 作图工具

选择 Graphviz 作为作图工具&#xff0c;主要是想通过代码创建图标&#xff0c;按照 Graphviz 的代码规范就可以生成 svg 的图片。当然&#xff0c;这样的工具也有很多&#xff0c;有些 markdown 编辑器也做了集成&#xff0c;比如&#xff1a; flowchart.jsMermaid 了解 Gra…...

vue、vuex状态管理、vuex的核心概念state状态

每一个 Vuex 应用的核心就是 store&#xff08;仓库&#xff09;。“store”基本上就是一个容器&#xff0c;它包含着你的应用中大部分的状态 (state)。Vuex 和单纯的全局对象有以下两点不同&#xff1a; Vuex 的状态存储是响应式的。当 Vue 组件从 store 中读取状态的时候&…...

【QT】Qt Application Manager启动应用源码分析

Qt Application Manager启动应用源码分析 Qt Application Manager&#xff08;以下简称QTAM&#xff09;是QT推出的一款应用管理程序&#xff0c;可以把它简单理解成Android的LauncherSystemUI。但是&#xff0c;QTAM又集成了Wayland功能&#xff0c;并且自身实现了一套Compos…...

MyBatisPlus(十)判空查询

说明 判空查询&#xff0c;对应SQL语句中的 IS NULL语句&#xff0c;查询对应字段为 NULL 的数据。 isNull /*** 查询用户列表&#xff0c; 查询条件&#xff1a;电子邮箱为 null 。*/Testvoid isNull() {LambdaQueryWrapper<User> wrapper new LambdaQueryWrapper<…...

AIGC(生成式AI)试用 8 -- 曾经的难题

长假&#xff0c;远离电脑、远离手机、远离社交。 阴雨连绵&#xff0c;望着窗外发呆&#xff0c;AIGC为何物&#xff1f;有什么问题要问AIGC&#xff1f;AIGC可以代替我来发呆&#xff0c;还是可是为我空出时间发呆&#xff1f; 如果可以替代我发呆&#xff0c;要我何…...

文化主题公园旅游景点3d全景VR交互体验加深了他们对历史文化的认知和印象

如今&#xff0c;沉浸式体验被广泛应用于文旅行业&#xff0c;尤其是在旅游演艺活动中。在许多城市&#xff0c;沉浸式旅游演艺活动已成为游客“必打卡”项目之一。因其独特体验和强互动性&#xff0c;这类演艺活动不仅吸引了外地游客&#xff0c;也吸引了本地观众。 随着信息化…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...