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

【数据结构】手撕双向链表

目录

前言

1. 双向链表 

带头双向循环链表的结构

2. 链表的实现

2.1 初始化

2.2 尾插

2.3 尾删

2.4 头插

2.5 头删

2.6 在pos位置之前插入

2.7 删除pos位置

3.双向链表完整源码

List.h

List.c


前言

在上一期中我们介绍了单链表,也做了一些练习题,在一些题中使用单链表会十分繁琐。因为单链表只能正着走,不能倒着走,例如:回文、逆置。本期我们将学习带头双向循环链表。

1. 双向链表 

带头双向循环链表的结构

 特点:带头双向循环链表结构最复杂,一般用在单独存储数据。结构虽然结构复杂,但是使用代码实现以后会发现结构会带来多优势,实现反而简单了。

2. 链表的实现

2.1 初始化

LTNode* LTInit()
{LTNode* phead = CreateLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

2.2 尾插

带哨兵位的链表尾插时不用判断是否有节点,两种情况的插入相同,而且还不用传递二级指针。

void LTPushBack(LTNode* phead, LTDateType x)
{assert(phead);LTNode* newnode = CreateLTNode(x);phead->prev->next = newnode;newnode->prev = phead->prev;newnode->next = phead;phead->prev = newnode;
}

2.3 尾删

在尾删时我们通过 assert(phead->next != phead);  判断链表是否有节点。同时这个代码就有普遍性,不用单独考虑剩一个节点的情况。

void LTPopBack(LTNode* phead)
{assert(phead);LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);phead->prev = tailprev;tailprev->next = phead;
}

2.4 头插

头删重要的是赋值的顺序,顺序错误会找不到后面的节点,导致内存泄漏。带哨兵位的链表不需要传递二级指针,因为改变的是结构体的变量。

void LTPushFront(LTNode* phead, LTDateType x)
{assert(phead);LTNode* newnode = CreateLTNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}

2.5 头删

我们可以多定义几个指针来保存后面节点的地址,这样就不会造成节点的丢失,不用考虑赋值的顺序,会更加方便。 

void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->next;LTNode* next = tail->next;phead->next = next;next->prev = phead;free(tail);tail = NULL;
}

2.6 在pos位置之前插入

void LTInsert(LTNode* pos, LTDateType x)
{assert(pos);LTNode* posprev = pos->prev;LTNode* newnode = CreateLTNode(x);posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;
}

2.7 删除pos位置

void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev;
}

3.双向链表完整源码

List.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDateType;typedef struct ListNode
{LTDateType val;struct ListNode* next;struct ListNode* prev;
}LTNode;LTNode* LTInit();void LTPrint(LTNode* phead);void LTPushBack(LTNode* phead, LTDateType x);void LTPushFront(LTNode* phead, LTDateType x);void LTPopBack(LTNode* phead);void LTPopFront(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDateType x);void LTInsert(LTNode* pos, LTDateType x);void LTErase(LTNode* pos);void LTDestroy(LTNode* phead);

List.c

#include"List.h"LTNode* CreateLTNode(LTDateType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;
}LTNode* LTInit()
{LTNode* phead = CreateLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("<=>哨兵位<=>");while (cur != phead){printf("%d<=>", cur->val);cur = cur->next;}printf("\n");
}void LTPushBack(LTNode* phead, LTDateType x)
{assert(phead);LTNode* newnode = CreateLTNode(x);phead->prev->next = newnode;newnode->prev = phead->prev;newnode->next = phead;phead->prev = newnode;
}void LTPushFront(LTNode* phead, LTDateType x)
{assert(phead);LTNode* newnode = CreateLTNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}void LTPopBack(LTNode* phead)
{assert(phead);LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);phead->prev = tailprev;tailprev->next = phead;
}void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->next;LTNode* next = tail->next;phead->next = next;next->prev = phead;free(tail);tail = NULL;
}LTNode* LTFind(LTNode* phead, LTDateType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}void LTInsert(LTNode* pos, LTDateType x)
{assert(pos);LTNode* posprev = pos->prev;LTNode* newnode = CreateLTNode(x);posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;
}void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev;
}void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}

通过上面链表的实现,我们已经感受到了带头双向循环链表的方便和简单,它不需要去考虑链表是否有元素,还可以找到前一个元素,在我们使用中提供很大的便利。

本次的内容到这里就结束啦。希望大家阅读完可以有所收获,同时也感谢各位读者三连支持。文章有问题可以在评论区留言,博主一定认真认真修改,以后写出更好的文章。 

相关文章:

【数据结构】手撕双向链表

目录 前言 1. 双向链表 带头双向循环链表的结构 2. 链表的实现 2.1 初始化 2.2 尾插 2.3 尾删 2.4 头插 2.5 头删 2.6 在pos位置之前插入 2.7 删除pos位置 3.双向链表完整源码 List.h List.c 前言 在上一期中我们介绍了单链表&#xff0c;也做了一些练习题&…...

性能测试 —— Jmeter接口处理不低于200次/秒-场景

需求&#xff1a;期望某个接口系统的处理能力不低于200次/秒&#xff0c;如何设计&#xff1f; ①这个场景是看服务器对某个接口的TPS值是否能大于等于200&#xff0c;就可以了&#xff1b; ②系统处理能力&#xff1a;说的就是我们性能测试中的TPS&#xff1b; ③只要设计一…...

Qt中使用QNetworkAccessManager类发送https请求时状态码返回0

前言 在项目开发中&#xff0c;碰到一个问题&#xff0c;使用QNetworkAccessManager类对象发送https请求时&#xff0c;状态码一直返回0&#xff0c;抓包分析看请求响应也是正常的。费了好大劲终于搞定了&#xff0c;主要是两个原因导致的。 原因一&#xff1a;未设置支持SSL…...

Linux - 物理内存管理 - memmap

说明 裁减内核预留内存占用&#xff0c;在启动log中&#xff0c;发现memmap占用了大块内存&#xff08;446个pages&#xff09;。 On node 0 totalpages: 32576 memblock_alloc_try_nid: 1835008 bytes align0x40 nid0 from0x0000000000000000 max_addr0x0000000000000000 al…...

Python爬虫动态ip代理防止被封的方法

目录 前言 一、什么是动态IP代理&#xff1f; 二、如何获取代理IP&#xff1f; 1. 付费代理IP 2. 免费代理IP 3. 自建代理IP池 三、如何使用代理IP爬取数据&#xff1f; 1. 使用requests库设置代理IP 2. 使用urllib库设置代理IP 3. 使用selenium库设置代理IP 四、常…...

01Urllib

1.什么是互联网爬虫&#xff1f; 如果我们把互联网比作一张大的蜘蛛网&#xff0c;那一台计算机上的数据便是蜘蛛网上的一个猎物&#xff0c;而爬虫程序就是一只小蜘蛛&#xff0c;沿着蜘蛛网抓取自己想要的数据 解释1&#xff1a;通过一个程序&#xff0c;根据Url(http://www.…...

python爬取酷我音乐 根据歌名进行爬取

# _*_ coding:utf-8 _*_ # 开发工具:PyCharm # 公众号:小宇教程import urllib.parse from urllib.request import urlopen import json import time import sys import osdef Time_1...

【深度学习】吴恩达课程笔记(五)——超参数调试、batch norm、Softmax 回归

笔记为自我总结整理的学习笔记&#xff0c;若有错误欢迎指出哟~ 【吴恩达课程笔记专栏】 【深度学习】吴恩达课程笔记(一)——深度学习概论、神经网络基础 【深度学习】吴恩达课程笔记(二)——浅层神经网络、深层神经网络 【深度学习】吴恩达课程笔记(三)——参数VS超参数、深度…...

腾讯云轻量级服务器和云服务器什么区别?轻量服务器是干什么用的

随着互联网的迅速发展&#xff0c;服务器成为了许多人必备的工具。然而&#xff0c;面对众多的服务器选择&#xff0c;我们常常会陷入纠结之中。在这篇文章中&#xff0c;我们将探讨轻量服务器和标准云服务器的区别&#xff0c;帮助您选择最适合自己需求的服务器。 腾讯云双十…...

解决:虚拟机远程连接失败

问题 使用FinalShell远程连接虚拟机的时候连接不上 发现 虚拟机用的VMware&#xff0c;Linux发行版是CentOs 7&#xff0c;发现在虚拟机中使用ping www.baidu.com是成功的&#xff0c;但是使用FinalShell远程连接不上虚拟机&#xff0c;本地网络也ping不通虚拟机&#xff0c…...

SpringBoot项目集成发邮件功能

1&#xff1a;引入依赖2&#xff1a;配置设置3&#xff1a;授权码获取&#xff1a;4&#xff1a;核心代码5&#xff1a;postman模拟验证6&#xff1a;安全注意 1&#xff1a;引入依赖 <dependency><groupId>org.apache.commons</groupId><artifactId>c…...

【Spring篇】使用注解进行开发

&#x1f38a;专栏【Spring】 &#x1f354;喜欢的诗句&#xff1a;更喜岷山千里雪 三军过后尽开颜。 &#x1f386;音乐分享【如愿】 &#x1f970;欢迎并且感谢大家指出小吉的问题 文章目录 &#x1f33a;原代码&#xff08;无注解&#xff09;&#x1f384;加上注解⭐两个注…...

Flink(六)【DataFrame 转换算子(下)】

前言 今天学习剩下的转换算子&#xff1a;分区、分流、合流。 每天出来自学是一件孤独又充实的事情&#xff0c;希望多年以后回望自己的大学生活&#xff0c;不会因为自己的懒惰与懈怠而悔恨。 回答之所以起到了作用&#xff0c;原因是他们自己很努力。 …...

【2023春李宏毅机器学习】生成式学习的两种策略

文章目录 1 各个击破2 一步到位3 两种策略的对比 生成式学习的两种策略&#xff1a;各个击破、一步到位 对于文本生成&#xff1a;把每一个生成的元素称为token&#xff0c;中文当中token指的是字&#xff0c;英文中的token指的是word piece。比如对于unbreakable&#xff0c;他…...

Android13 adb 无法连接?

Android13 adb 无法连接? 文章目录 Android13 adb 无法连接?一、前言二、替换adbGoogle 官网对adb的介绍&#xff1a;Google 提供的adb tools的下载&#xff1a; 三、总结1、adb connect 连接后显示offline2、输入adb devices 报错&#xff1a;版本不匹配导致3、adb常用命令4…...

Ubuntu 20.04 调整交换分区大小

Ubuntu 调整交换分区大小 一、系统情况二、去除旧的交换分区文件三、配置并启用交换分区四、查看swap文件大小 一、系统情况 Ubuntu &#xff1a;Ubuntu 20.04.6 LTS 交换分区位置&#xff1a; cat /proc/swaps二、去除旧的交换分区文件 去掉旧的交换分区有两个步骤&#x…...

将Agent技术的灵活性引入RPA,清华等发布自动化智能体ProAgent

近日&#xff0c;来自清华大学的研究人员联合面壁智能、中国人民大学、MIT、CMU 等机构共同发布了新一代流程自动化范式 “智能体流程自动化” Agentic Process Automation&#xff08;APA&#xff09;&#xff0c;结合大模型智能体帮助人类进行工作流构建&#xff0c;并让智能…...

高济健康:数字化科技创新与新零售碰撞 助推医疗产业优化升级

近日&#xff0c;第六届中国国际进口博览会在上海圆满落幕&#xff0c;首次亮相的高济健康作为一家专注大健康领域的疾病和健康管理公司&#xff0c;在本届进博会上向业内外展示了围绕“15分钟步行健康生活圈”构建进行的全域数字化升级成果。高济健康通过数字化科技创新与新零…...

SystemVerilog学习 (5)——接口

一、概述 验证一个设计需要经过几个步骤&#xff1a; 生成输入激励捕获输出响应决定对错和衡量进度 但是&#xff0c;我们首先需要一个合适的测试平台&#xff0c;并将它连接到设计上。 测试平台包裹着设计,发送激励并且捕获设计的输出。测试平台组成了设计周围的“真实世界”,…...

vue3插槽的使用

什么是插槽 Vue 3 插槽&#xff08;Slots&#xff09;是一个强大的工具&#xff0c;用于在组件之间传递内容和逻辑。通过使用插槽&#xff0c;我们可以将子组件中的内容插入到父组件中的特定位置。本篇文章将总结 Vue 3 插槽的基本用法、特点以及使用场景。 基本用法 插槽分为…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...