数据结构笔记第3篇:双向链表
1、双向链表的结构
注意:这里的 "带头" 跟前面我们说的 "头结点" 是两个概念,实际前面的在单链表阶段称呼不严谨,但是为了同学们更好的理解就直接称为单链表的头结点。
带头链表里的头结点,实际为 "哨兵位" ,哨兵位节点不存储任何有效元素,只是站在这里 "放哨的"。
"哨兵位" 存在的意义:
遍历循环链表避免死循环。
注意:双向链表中,哨兵位的下一个节点是链表的第一个节点(头结点)。哨兵位的前一个节点是链表的最后一个节点(尾结点)。所以双向链表的头插是在哨兵位的后面插入数据。尾插则是在哨兵位之前插入数据。
哨兵位是作为头结点和尾结点的中点,是头结点的起点也是尾节点的终点。这样解释更容易理解。
2、 双向链表的实现
List.h 链表函数和链表节点类型的声明:
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
typedef struct ListNode
{SLDataType data;//存储数据struct ListNode* prve;//存储前一个节点的地址struct ListNode* next;//存储下一个节点的地址
}SList;
SList* SLInit();void SLPushBack(SList* phead, SLDataType x);//尾插
void SLPrint(SList* phead);//显示链表数据
void SLPustFront(SList* phead, SLDataType x);//头插
void SLPopBack(SList* phead);//尾删
void SLPopFront(SList* phead);//头删
void SLInsert(SList* pos, SLDataType x);//指定位置插入
SList* SLfind(SList* phead, SLDataType x);//查找节点
void SLEarse(SList* pos);//指定位置删除
void SLDestory(SList** pphead);//链表销毁
List.c 链表函数的实现:
#include "List.h"
//链表初始化
SList* SLInit()
{SList* phead = (SList*)malloc(sizeof(SList));if (phead == NULL){perror("malloc error");return NULL;}phead->data = -1;//因为是循环链表,所以初始化要遵循循环格式phead->next = phead;phead->prve = phead;return phead;
}
//创建链表节点
SList* ListBuyNode(SLDataType x)
{SList* retNode = (SList*)malloc(sizeof(SList));if (retNode == NULL){perror("malloc error");return NULL;}retNode->data = x;retNode->prve = retNode;retNode->next = retNode;return retNode;
}
//链表尾插
void SLPushBack(SList* phead, SLDataType x)
{assert(phead);SList* Node = ListBuyNode(x);Node->prve = phead->prve;Node->next = phead;phead->prve->next = Node;phead->prve = Node;
}
//链表数据显示
void SLPrint(SList* phead)
{assert(phead);SList* pcur = phead->next;while (pcur != phead)//哨兵位作为结束标识{printf("%d", pcur->data);if (pcur->next != phead)printf("->");pcur = pcur->next;}printf("\n");
}
//链表头插
void SLPustFront(SList* phead, SLDataType x)
{assert(phead);SList* Node = ListBuyNode(x);Node->next = phead->next;Node->prve = phead;phead->next->prve = Node;phead->next = Node;
}
//链表尾删
void SLPopBack(SList* phead)
{assert(phead);assert(phead->next != phead);SList* del = phead->prve;del->prve->next = phead;phead->prve = del->prve;free(del);del = NULL;
}
//链表头删
void SLPopFront(SList* phead)
{assert(phead);assert(phead->next != phead);SList* del = phead->next;del->next->prve = phead;phead->next = del->next;free(del);del = NULL;
}
//指定位置插入
void SLInsert(SList* pos, SLDataType x)
{assert(pos);SList* Node = ListBuyNode(x);Node->next = pos->next;Node->prve = pos;pos->next = Node;Node->next->prve = Node;
}
//查找节点
SList* SLfind(SList* phead, SLDataType x)
{assert(phead);SList* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//指定位置删除
void SLEarse(SList* pos)
{assert(pos);pos->prve->next = pos->next;pos->next->prve = pos->prve;free(pos);pos = NULL;
}
//链表销毁
void SLDestory(SList** pphead)
{assert(pphead && *pphead);SList* pcur = (*pphead)->next;while (pcur != *pphead){SList* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;
}
test.c 函数的调用:
#include "List.h"void SLtest()
{SList* plist = NULL;plist = SLInit();//尾插SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPrint(plist);//打印:1->2->3->4//头插SLPustFront(plist, 5);SLPustFront(plist, 6);SLPustFront(plist, 7);SLPrint(plist);//打印:7->6->5->1->2->3->4//尾删SLPopBack(plist);SLPrint(plist);//打印:7->6->5->1->2->3//头删SLPopFront(plist);SLPrint(plist);//打印:6->5->1->2->3//指定位置插入SList* find = SLfind(plist, 5);SLInsert(find, 11);SLPrint(plist);//打印:6->5->11->1->2->3//指定位置删除find = SLfind(plist, 1);SLEarse(find);SLPrint(plist);//打印:6->5->11->2->3//链表销毁SLDestory(&plist);
}
int main()
{SLtest();return 0;
}
3、顺序表和双向链表的优缺点分析
不同点 | 顺序表 | 链表 |
存储空间上 | 物理上一定连续 | 逻辑上连续,但物理上不一定连续 |
随机访问 | 支持O(1) | 不支持O(N) |
任意位置插入或者删除元素 | 可能需要搬移元素,效率低O(N) | 只需要修改指针指向 |
插入 | 动态顺序表,空间不够时需要扩容 | 没有容量的概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
数据结构第3篇笔记到这里也就结束了,我们下一篇笔记再见-
相关文章:

数据结构笔记第3篇:双向链表
1、双向链表的结构 注意:这里的 "带头" 跟前面我们说的 "头结点" 是两个概念,实际前面的在单链表阶段称呼不严谨,但是为了同学们更好的理解就直接称为单链表的头结点。 带头链表里的头结点,实际为 "哨兵…...
详细对比Java SPI、Spring SPI 和 Dubbo SPI
SPI(Service Provider Interface)概述 定义:SPI是一种动态替换发现机制,用于实现接口与实现的解耦,提高框架的可扩展性。核心思想:解耦和方便扩展。 Java SPI 约定规范: 扩展类文件放在META-…...
CPU的核心数和线程数
CPU的核心数和线程数 一、关系: 1、线程数可以模拟出不同的CPU核心数。 CPU的核心数指的是硬件上存在着几个核心,而线程数可以模拟出多个核心数的功能。线程数越多,越有利于同时运行多个程序,因为线程数等同于在某个瞬间CPU能同…...

电脑游戏录屏,3款实用软件推荐给你
在电竞游戏热潮席卷全球的今天,电脑游戏录屏早已不再是简单的画面捕捉,它成为了记录电竞风采、打造专属游戏记忆的重要手段。通过游戏录屏,我们可以定格游戏中的精彩瞬间,重温那些令人热血沸腾的电竞时刻。那么,在进行…...

C#桌面应用开发:番茄定时器
C#桌面应用开发:番茄定时器 1、环境搭建和工程创建: 步骤一:安装visual studio2022 步骤二:新建工程 2、制作窗体部件 *踩过的坑: (1)找不到工具箱控件,现象如下:…...

PHP智慧门店微信小程序系统源码
🔍【引领未来零售新风尚】🔍 🚀升级启航,智慧零售新篇章🚀 告别传统门店的束缚,智慧门店v3微信小程序携带着前沿科技与人性化设计,正式启航!这个版本不仅是对过往功能的全面优化&a…...

SerDes介绍以及原语使用介绍(2)OSERDESE2原语仿真
文章目录 前言一、SDR模式1.1、设计代码1.2、testbench代码1.3、仿真分析 二、DDR模式下2.1、设计代码2.2、testbench代码2.3、仿真分析 三、OSERDES2级联3.1、设计代码3.2、testbench代码3.3、代码分析 前言 上文通过xilinx ug471手册对OSERDESE有了简单的了解,接…...

【稳定检索/投稿优惠】2024年教育、人文发展与艺术国际会议(EHDA 2024)
2024 International Conference on Education, Humanities Development and Arts 2024年教育、人文发展与艺术国际会议 【会议信息】 会议简称:EHDA 2024 大会时间:点击查看 截稿时间:点击查看 大会地点:中国北京 会议官网&#…...

Docker拉取失败,利用 Git将 Docker镜像重新打 Tag 推送到阿里云等其他公有云镜像仓库里
目录 一、开通阿里云容器镜像服务 二、Git配置 三、去DockerHub找镜像 四、编写images.txt文件 五、演示 六、其他注意事项 最近一段时间 Docker 镜像一直是 Pull 不下来的状态,想直连 DockerHub 是几乎不可能的。更糟糕的是,很多原本可靠的国内…...
【区分vue2和vue3下的element UI Breadcrumb 面包屑组件,分别详细介绍属性,事件,方法如何使用,并举例】
在 Vue 2 中,Element UI 提供了 el-breadcrumb 面包屑组件,而在 Vue 3 中,Element UI 的官方版本并没有直接更新以支持 Vue 3,但有一个类似的库叫做 Element Plus,它是为 Vue 3 设计的。 Vue 2 Element UI 在 Vue 2…...
gdb调试命令大全
基本命令 #gdb test test是要调试的程序,由gcc test.c -g -o test生成。进入后提示符变为(gdb) 。 start : 指令会执行程序至main() 主函数的起始位置,即在main() 函数的第一行语句处停止执行(该行代码尚未执行) cont…...

ESP32之arduino环境安装及点灯
目录 前言 前两天安装了VScode,奈何资源找的困难,于是咨询淘宝客服,他说arduino用的多,资源多.然后就安装了a…...

查看VUE中安装包依赖的版本号
查看VUE中安装包依赖的版本号 全部依赖包版本查看某个依赖的例:查看stompjs 应用命令npm ls stompjs 全部依赖包版本 使用npm命令 使用 npm ls 命令可以列出项目中所有已安装的依赖包及其版本。 使用 npm list --depth1 命令可以列出项目中直接依赖的包及其版本&a…...

博途通讯笔记1:1200与1200之间S7通讯
目录 一、添加子网连接二、创建PUT GET三、各个参数的意义 一、添加子网连接 二、创建PUT GET 三、各个参数的意义...
Kafka搭建(集群版)
Kafka单机版 部署前提 VMware环境 : 两台centos系统 Jdk包:jdk-8u202-linux-x64.tar.gz Kafka包:kafka_2.12-3.5.0.tgz Zookeeper包:apache-zookeeper-3.7.2-bin.tar.gz 百度网盘自取: 链接: https://pan.baidu.com/s/11EWuhBoSmH3musd_3Rgodw?pwde32t 提取码: e32t Kafka搭建…...
【康复学习--LeetCode每日一题】3115. 质数的最大距离
题目: 给你一个整数数组 nums。 返回两个(不一定不同的)质数在 nums 中 下标 的 最大距离。 示例 1: 输入: nums [4,2,9,5,3] 输出: 3 解释: nums[1]、nums[3] 和 nums[4] 是质数。因此答案是…...

【yolov8系列】ubuntu上yolov8的开启训练的简单记录
前言 yolov8的广泛使用,拉取yolov8源码工程,然后配置环境后直接运行,初步验证自己数据的检测效果,在数据集准备OK的情况下 需要信手拈来,以保证开发过程的高效进行。 本篇博客更注意为了方便自己使用时参考。顺便也记录…...
Scala学习笔记15: 文件和正则表达式
目录 第十五章 文件和正则表达式1- 读取行2- 从URL或者其它源读取3- 写入文本文件4- 序列化5- 正则表达式6- 正则表达式验证输入数据格式end 第十五章 文件和正则表达式 1- 读取行 在Scala中读取文件中的行可以通过不同的方法实现 ; 一种常见的方法是使用 scala.io.Source 对…...
外卖员面试现状
说明: 以下身份角色用符号代替 # 面试官 $ 求职者 # 看了您的简历你有两年半的送外卖经验,可以简单说一下您平时是怎么送外卖的吗? $ 我首先在平台接单然后到店里取餐,取到餐后到顾客留下的地址,再通知顾客取餐 # 你们也用电动…...
异步加载与动态加载
异步加载和动态加载在概念上有相似之处,但并不完全等同。 异步加载(Asynchronous Loading)通常指的是不阻塞后续代码执行或页面渲染的数据或资源加载方式。在Web开发中,异步加载常用于从服务器获取数据,而不需要用户等…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...

通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...

【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...

Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...