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

数据结构——双向链表

双向链表实质上是在单向链表的基础上加上了一个指针指向后面地址

单向链表请参考http://t.csdn.cn/3Gxk9

物理结构
首先我们看一下两种链表的物理结构
在这里插入图片描述
我们可以看到:双向在单向基础上加入了一个指向上一个地址的指针,如此操作我们便可以向数组一样操作了,而且尾插也更加方便,复杂度从原来的O(n)变为O(1),并且查找也可以运用二分查找。

一些基础操作

头插

在这里插入图片描述

头删

在这里插入图片描述

尾插

在这里插入图片描述

尾删

在这里插入图片描述

接下来我们来进行代码实现

头文件以及要实现的函数声明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int LTDataType;
typedef struct Slist
{LTDataType val;struct Slist* next;struct Slist* random;
}ListNode;// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
// 扩容
ListNode* my_malloc(LTDataType x);

函数实现

#include "dslist.h"ListNode* my_malloc(LTDataType x)//由于后续要频繁使用到扩容,所以我们直接创一个扩容函数
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));newnode->val = x;newnode->random = NULL;newnode->next = NULL;return newnode;
}ListNode* ListCreate()  //创建一个双向链表
{ListNode* head = (ListNode * )malloc(sizeof(ListNode));head->val = -1;    head->next= NULL;head->random = NULL;return head;
}void ListDestory(ListNode* pHead)  //销毁这个双线链表
{while (pHead)//将每个节点都free掉{ListNode* mid = pHead;pHead = pHead->next;mid->next = NULL;free(mid);}
}void ListPrint(ListNode* pHead)   //打印双向链表
{ListNode* mid = pHead;while (mid)  //循环一个一个打印{printf("%d->", mid->val);mid = mid->next;}printf("NULL");
}void ListPushBack(ListNode* pHead, LTDataType x)    //尾插
{ListNode* newnode = my_malloc(x);if (pHead->next == NULL)       //判断链表是否为空,如果为空则只需要插入一个。{newnode->random = pHead;    //由于循环链表,需要将头节点的random指向插入元素  newnode->next = NULL;pHead->next = newnode;pHead->random = newnode;}else             //如果不为空则正常尾插{ListNode* mid = pHead->random;    //由于双向  头节点的random指针直接指向尾部,所以不需要循环找尾mid->next = newnode;newnode->random = mid;pHead->random = newnode;}
}void ListPopBack(ListNode* pHead)   //尾删
{if (pHead->next == NULL)   //判断是否为空{return;}else{ListNode* mid = pHead->random;   //正常尾删pHead->random = mid->random;mid->random->next = NULL;free(mid);}
}void ListPushFront(ListNode* pHead, LTDataType x)    //头插
{if (pHead->next == NULL) //如果为空  则相当于尾插  调用尾插函数即可{ListPushBack(pHead, x);}else    //不为空正常头插{ListNode* nownode = my_malloc(x);   nownode->next = pHead->next;     //将nownode  的next指向  phead的nextnownode->random = pHead;     //nownode的random指向  pheadpHead->next = nownode;          //phead的next指向nownodenownode->next->random = nownode;}
}void ListPopFront(ListNode* pHead)    //头删
{if (pHead->next == NULL){return;}else{if (pHead->next == pHead->random){ListPopBack(pHead);}else{ListNode* mid = pHead->next;pHead->next = mid->next;mid->next->random = pHead;free(mid);}}
}ListNode* ListFind(ListNode* pHead, LTDataType x)   //寻找元素
{ListNode* left = pHead->next;ListNode* right = pHead->random;while (left && right)    //二分查找{if (left->val == x){return left;}if (right->val == x){return right;}left = left->next;right = right->random;}return NULL;
}void ListInsert(ListNode* pos, LTDataType x)
{ListNode* newnode = my_malloc(x);ListNode* mid = pos->random;mid->next = newnode;pos->random = newnode;newnode->next = pos;
}void ListErase(ListNode* pos)
{ListNode* next = pos->next;ListNode* last = pos->random;next->random = last;last->next = next;free(pos);
}

有什么疑惑欢迎大家留言。

相关文章:

数据结构——双向链表

双向链表实质上是在单向链表的基础上加上了一个指针指向后面地址 单向链表请参考http://t.csdn.cn/3Gxk9 物理结构 首先我们看一下两种链表的物理结构 我们可以看到&#xff1a;双向在单向基础上加入了一个指向上一个地址的指针&#xff0c;如此操作我们便可以向数组一样操作…...

Declare 关键字在 TypeScript 中如何正确使用?

如果您编写 TypeScript 代码的时间足够长,您就已经看到过declare关键字。但它有什么作用,为什么要使用它? declare关键字告诉 TypeScript 编译器存在一个对象并且可以在代码中使用。 本文解释了声明关键字并通过代码示例展示了不同的用例。 定义 在 TypeScript 中,decl…...

ChatGPT将会成为强者的外挂?—— 提高学习能力

目录 前言 一、提高学习力 &#x1f9d1;‍&#x1f4bb; 1. 快速找到需要的知识 2. 组合自己的知识体系 3. 内化知识技能 二、提问能力❗ 三、思维、创新能力 &#x1f31f; 1. 批判性思维 1.1 八大基本结构进行批判性提问 1.2 苏格拉底的提问分类方法 2. 结构化思…...

AUTOSAR规范与ECU软件开发(基础篇)1.3 车用控制器软件标准(从OSEK到AUTOSAR)

目录 AUTOSAR的前世与今生 1.1~1.3篇幅小结 AUTOSAR的前世与今生 为了迎合汽车高精度、 高实时性、 高可靠性控制的需要, 嵌入式实时操作系统(Real Time Operating System, RTOS) 逐渐在ECU中使用。与此同时, 由于不同实时操作系统间应用程序接口(Application Programmi…...

R语言5_安装Giotto

环境Ubuntu22/20, R4.1. 已开启科学上网。 第一步&#xff0c;更新服务器环境&#xff0c;进入终端&#xff0c;键入如下命令&#xff0c; apt-get update apt install libcurl4-openssl-dev libssl-dev libxml2-dev libcairo2-dev libgtk-3-dev libhdf5-dev libmagick9-dev …...

centos按用户保存历史执行命令

centos7 按用户记录历史命令的方法 在/etc/profile文件中添加以下代码。 添加完成后执行source /etc/profile 用户重新登录即可发现history被清空了。这时可以去看/usr/share/.history文件夹&#xff0c;该文件夹保存了所有用户每次登录所执行过的的操作记录。 文件路径为 /usr…...

【力扣】61. 旋转链表 <快慢指针>

【力扣】61. 旋转链表&#xff08;每个节点向右移k个单位&#xff09; 给你一个链表的头节点 head &#xff0c;旋转链表&#xff0c;将链表每个节点向右移动 k 个位置。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], k 2 输出&#xff1a;[4,5,1,2,3] 示例 2&a…...

编写一个指令(v-focus2end)使输入框文本在聚焦时焦点在文本最后一个位置

项目反馈输入框内容比较多时候&#xff0c;让鼠标光标在最后一个位置&#xff0c;心想什么奇葩需求&#xff0c;后面试了一下&#xff0c;是有点影响体验&#xff0c;于是就有了下面的效果&#xff0c;我目前的项目都是若依的架子&#xff0c;用的是vue2版本。vue3的朋友想要使…...

Virtualbox设置访问外网以及主机和虚拟机互通

参考链接 1、设置使虚拟机访问外网。选中虚拟机&#xff0c;右击选择“设置”。 2、在设置中选择“网络”&#xff0c;然后点击“网卡1”&#xff0c;选择“网络地址转换&#xff08;NAT&#xff09;”模式&#xff0c;点击“确定”。 4.此时你的虚拟机就可以访问外网了 5…...

请简述React是什么?React的主要特点有哪些?React中有哪些主要组件?

1、请简述React是什么&#xff1f; React是一个用于构建用户界面的JavaScript库&#xff0c;它由Facebook开发并开源。React的主要特点是其数据驱动和组件化的设计理念。它允许开发者将复杂的界面分解为简单的组件&#xff0c;并将这些组件以数据流的方式组合在一起&#xff0…...

DevOps最佳实践和工具在本地环境中的概述

引言 最近&#xff0c;我进行了一次网上搜索&#xff0c;以寻找DevOps的概述&#xff0c;尽管有大量的DevOps工具和实践&#xff0c;但我无法找到一个综合的概述。因此&#xff0c;我开始了对DevOps生态系统和最佳实践的梳理&#xff0c;以创建一个整体视图,方便后续研究实践 C…...

kafka和rabbitmq之间的区别以及适用场景

Kafka 和 RabbitMQ 都是流行的消息传递系统&#xff0c;用于实现分布式系统中的消息传递、事件处理和数据流。它们在设计和适用场景上有一些不同&#xff0c;下面详细介绍它们之间的区别和适用场景。 Kafka 特点和优势&#xff1a; 高吞吐量&#xff1a; Kafka 的设计目标是实…...

python——案例15:判断奇数还是偶数

案例15&#xff1a;判断奇数还是偶数numint(input(输入数值&#xff1a;))if(num%2)0: #通过if语句判断print("{0}是偶数".format(num))else: #通过else语句判断print("{0}是奇数".format(num))...

springboot汽车租赁后台java出租客户管理jsp源代码mysql

本项目为前几天收费帮学妹做的一个项目&#xff0c;Java EE JSP项目&#xff0c;在工作环境中基本使用不到&#xff0c;但是很多学校把这个当作编程入门的项目来做&#xff0c;故分享出本项目供初学者参考。 一、项目描述 springboot汽车租赁后台 系统有1权限&#xff1a;管理…...

Linux学习之sed删除、追加、插入、更改、读写文件、下一行、打印、退出和seq命令

cat /etc/redhat-release看到操作系统是CentOS Linux release 7.6.1810&#xff0c;uname -r看到内核版本是3.10.0-957.el7.x86_64&#xff0c;sed --version可以看到sed版本是4.2.2。 echo a : 1 : good : g >> sed_daicpnrwq.txt echo b : 2 : well : w >> sed…...

JuiceFS 在多云存储架构中的应用 | 深势科技分享

2020 年末&#xff0c;谷歌旗下 DeepMind 研发的 AI 程序 AlphaFold2 在国际蛋白质结构预测竞赛上取得惊人的准确度&#xff0c;使得 “AI 预测蛋白质结构” 这一领域受到了空前的关注。今天我们邀请到同领域企业&#xff0c;深势科技为大家分享其搭建基础平台时的实践与思考。…...

什么是DNS的缓存?

DNS 缓存是一个临时的数据库&#xff0c;存储在计算机或网络设备&#xff08;如路由器&#xff09;上&#xff0c;用于保存最近的 DNS 查询结果。这种缓存机制可以加速后续的相同查询&#xff0c;因为设备可以直接从缓存中提取先前的查询结果&#xff0c;而不需要再次到外部的 …...

smtplib.SMTPHeloError: (500, b‘Error: bad syntax‘)

如果你编写邮件收发工具的时候,有可能会遇到这个问题。这里直接给出解决办法。 目录 1、检查系统版本 2、点击右侧的更改适配器选项...

/proc directory in linux

Its zero-length files are neither binary nor text, yet you can examine and display themUnder Linux, everything is managed as a file; even devices are accessed as files (in the /dev directory). Although you might think that “normal” files are either text …...

装饰器模式(C++)

定义 动态(组合)地给一个对象增加一些额外的职责。就增加功能而言&#xff0c;Decorator模式比生成子类(继承)更为灵活(消除重复代码&减少子类个数)。 一《设计模式》 GoF 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xf…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...