数据结构笔记第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开发中,异步加载常用于从服务器获取数据,而不需要用户等…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...
