【数据结构】链表篇
文章目录
- 1.链表的概念以及结构
- 2.链表的分类
- 2.1 单向或者双向
- 2.2 带头或者不带头
- 2.3 循环或者不循环
- 2.4 无头单向非循环链表和带头双向循环链表
- 3.单链表的实现
- 3.1 准备工作
- 3.2 节点的创建
- 3.3 单链表的释放
- 3.4 打印链表
- 3.5 单链表的尾插
- 3.6 单链表的尾删
- 3.7 单链表头删
- 3.8 单链表的头插
- 3.9 单链表的查找
- 3.10 在pos位置后插入
- 3.11 删除pos位置后的数据
- 4.代码整合
- 5.顺序表与链表的区别
1.链表的概念以及结构
概念:链表是一种物理储存结构上的非连续、非顺序的储存结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
- 链式结构在逻辑上是连续的,但是在物理上不一定连续
- 现实中的节点一般都是从堆上申请出来的
- 从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续
2.链表的分类
实际中链表的结构非常多样,以下情况组合起来就有8种链表。
2.1 单向或者双向
2.2 带头或者不带头
2.3 循环或者不循环
2.4 无头单向非循环链表和带头双向循环链表
虽然有这么多的链表结构,但是我们实际中最常用的还是两种结构。
无头单向非循环链表
带头双向循环链表
- 无头单向非循环链表:结构简单,一般不会单独用来存储数据,实际中更多的是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外在笔试中出现较多
- 带头双向循环链表:结构最复杂,一般用来单独存储数据。实际中使用的链表结构都是带头双向循环链表。另外这个结构虽然复杂,但是使用代码实现时反而简单。
3.单链表的实现
3.1 准备工作
定义结构体.
链表的节点只要两个值需要存储,一个是数据内容,一个是下一个节点的地址。
注意:为了更多的使用场景,我们可以定义一个宏去去替换数据类型。为了方便我就直接写int的。
typedef struct SListNode
{int data;struct SListNode* next;
}SL;
3.2 节点的创建
正常利用malloc创建就好,注意要检查内存是否开辟失败。
//动态申请一个节点
SL* BuySListNode(int x)
{SL* tmp = (SL*)malloc(sizeof(SL));if (tmp == NULL){perror("malloc");exit(-1);}tmp->data = x;tmp->next = NULL;return tmp;
}
3.3 单链表的释放
注意使用二级指针,因为我们传递的是一级指针的地址
SL* head = NULL;
DestoryList(&head);
释放时,为了释放当前节点,我们要在cur指向下一个节点时先保存一下该节点的地址。
//释放
void DestoryList(SL** head)
{SL* cur = (*head);while (cur){SL* prev = cur;cur = cur->next;free(prev);prev = NULL;}
}
3.4 打印链表
遍历打印就可以了,assert的目的是为了防止有人把空指针传进来。
//打印链表
void PrintList(SL** head)
{assert(head);//assert(*head);SL* cur = *head;while (cur){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
3.5 单链表的尾插
尾插有两种情况:
1.*head为空
直接让*head指向一个新的节点
2.*head不为空
找到当前链表的最后一个节点,然后将新创建的节点连接到后面
//单链表尾插
void PushBackList(SL** head,int x)
{assert(head);//防止有人把空指针传进来。if (*head == NULL){*head = BuySListNode(x);return;}SL* cur = *head;SL* tmp = BuySListNode(x);while (cur->next){cur = cur->next;}cur->next = tmp;
}
3.6 单链表的尾删
删除存在三种情况:
1.只有一个节点了
直接free释放,*head要置为NULL
2.不止一个节点
先找到第二个节点,然后释放第一个节点,将*head指向新的第一个节点。
3.没有节点
直接报错
//单链表尾删
void PopbackList(SL** head)
{assert(head);//防止有人把空指针传进来。assert(*head);SL* cur = *head;if (cur->next == NULL)//当剩下1个元素时,直接释放{free(cur);*head = NULL;return;}SL* prev = cur;while (cur->next){prev = cur;cur = cur->next;}free(cur);cur = NULL;prev->next = NULL;
}
3.7 单链表头删
删除存在三种情况:
1.只有一个节点了
直接free释放,*head要置为NULL
2.不止一个节点
找到最后一个节点和其前一个节点,找倒数第二个节点的目的是为了将next置为NULL
3.没有节点
直接报错
//单链表头删
void PopFrontList(SL** head)
{assert(head);//防止有人把空指针传进来。assert(*head);SL* cur = *head;if (cur->next == NULL)//当剩下1个元素时,直接释放{free(cur);*head = NULL;return;}SL* next = cur->next;free(cur);cur = NULL;*head = next;
}
3.8 单链表的头插
头插有两种情况:
1.*head为空
直接让*head指向一个新的节点
2.*head不为空
创建一个新的节点,找到当前链表的第一个节点,然后将新创建的节点的next指针指向第一个节点。然后让*head指向新的节点
//单链表头插
void PushFrontList(SL** head, int x)
{assert(head);if (*head == NULL){*head = BuySListNode(x);return;}SL* newnode = BuySListNode(x);newnode->next = *head;*head = newnode;
}
3.9 单链表的查找
找到返回节点,找不到返回NULL
//单链表的查找
SL* FindSlistNode(SL** head, int x)
{assert(head);assert(*head);SL* cur = *head;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
3.10 在pos位置后插入
既然要在pos节点后插入数据,那就要保证链表不为NULL,pos不为NULL
插入的逻辑就是尾插的逻辑,但是这里我们不在需要找节点位置了,已经给出pos节点了。
//在pos位置后插入
void InsertList(SL** head, SL* pos, int x)
{assert(head);assert(*head);assert(pos);SL* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}
3.11 删除pos位置后的数据
注意两种情况就行了。
//删除pos位置后的节点
void EraseList(SL** head, SL* pos)
{assert(pos);assert(head);assert(*head);if (pos->next == NULL)return;else{SL* next = pos->next->next;SL* tmp = pos->next;pos->next = next;free(tmp);tmp = NULL;}
}
4.代码整合
//list.h
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <assert.h>typedef struct SListNode
{int data;struct SListNode* next;
}SL;//动态申请一个节点
SL* BuySListNode(int x);//销毁链表
void DestoryList(SL** head);//打印链表
void PrintList(SL** head);//单链表尾插
void PushBackList(SL** head, int x);//单链表尾删
void PopbackList(SL** head);//单链表头删
void PopFrontList(SL** head);//单链表头插
void PushFrontList(SL** head, int x);//单链表的查找
SL* FindSlistNode(SL** head, int x);//在pos位置后插入
void InsertList(SL** head, SL* pos, int x);//删除pos位置后的节点
void EraseList(SL** head, SL* pos);//list.c
#include "list.h"SL* BuySListNode(int x)
{SL* tmp = (SL*)malloc(sizeof(SL));if (tmp == NULL){perror("malloc");exit(-1);}tmp->data = x;tmp->next = NULL;return tmp;
}void DestoryList(SL** head)
{SL* cur = (*head);while (cur){SL* prev = cur;cur = cur->next;free(prev);}}//打印链表
void PrintList(SL** head)
{//assert(*head);SL* cur = *head;while (cur){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}//单链表尾插
void PushBackList(SL** head,int x)
{if (*head == NULL){*head = BuySListNode(x);return;}SL* cur = *head;SL* tmp = BuySListNode(x);while (cur->next){cur = cur->next;}cur->next = tmp;
}//单链表尾删
void PopbackList(SL** head)
{assert(*head);SL* cur = *head;if (cur->next == NULL)//当剩下1个元素时,直接释放{free(cur);cur = NULL;*head = NULL;return;}SL* prev = cur;while (cur->next){prev = cur;cur = cur->next;}free(cur);cur = NULL;prev->next = NULL;
}//单链表头删
void PopFrontList(SL** head)
{assert(head);//防止有人把空指针传进来。assert(*head);SL* cur = *head;if (cur->next == NULL)//当剩下1个元素时,直接释放{free(cur);cur = NULL;*head = NULL;return;}SL* next = cur->next;free(cur);cur = NULL;*head = next;
}//单链表头插
void PushFrontList(SL** head, int x)
{assert(head);if (*head == NULL){*head = BuySListNode(x);return;}SL* newnode = BuySListNode(x);newnode->next = *head;*head = newnode;
}//单链表的查找
SL* FindSlistNode(SL** head, int x)
{assert(*head);SL* cur = *head;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//在pos位置后插入
void InsertList(SL** head, SL* pos, int x)
{assert(pos);SL* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}//删除pos位置后的节点
void EraseList(SL** head, SL* pos)
{assert(pos);assert(head);assert(*head);if (pos->next == NULL)return;else{SL* next = pos->next->next;SL* tmp = pos->next;pos->next = next;free(tmp);tmp = NULL;}
}//test.c
#include "list.h"//void test1()
//{
// SL* head = BuySListNode(1);
// PushBackList(&head, 2);
// PushBackList(&head, 3);
// PushBackList(&head, 4);
// PopFrontList(&head);
// PrintList(&head);
// PopFrontList(&head);
// PrintList(&head);
// PopFrontList(&head);
// PrintList(&head);
// PopFrontList(&head);
// PrintList(&head);
// DestoryList(&head);
//}
//
//void test2()
//{
// SL* head = BuySListNode(1);
// PushFrontList(&head, 4);
// PushFrontList(&head, 2);
//
// SL* tmp = FindSlistNode(&head, 1);
// printf("tmp:%d\n", tmp->data);
//
// tmp = FindSlistNode(&head, 100);
// if(tmp!=NULL)
// printf("tmp:%d\n", tmp->data);
// DestoryList(&head);
//
//}
//
//void test3()
//{
// SL* head = NULL;
// PushFrontList(&head, 4);
// PushFrontList(&head, 2);
// PushBackList(&head, 1);
// PushBackList(&head, 1);
// PushBackList(&head, 1);
// SL* tmp = FindSlistNode(&head, 2);
// InsertList(&head, tmp, 100);
// EraseList(&head, tmp);
// PrintList(&head);
// DestoryList(&head);
//
//}int main()
{test3();return 0;
}
5.顺序表与链表的区别
不同点 | 顺序表 | 链表 |
---|---|---|
存储空间上 | 物理上一定连续 | 逻辑上连续,但物理上不一定 连续 |
随机访问 | 支持O(1) | 不支持:O(N) |
任意位置插入或者删除 元素 | 可能需要搬移元素,效率低 O(N) | 只需修改指针指向 |
插入 | 动态顺序表,空间不够时需要 扩容 | 没有容量的概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
缓存利用率 | 高 | 低 |
相关文章:

【数据结构】链表篇
文章目录 1.链表的概念以及结构2.链表的分类2.1 单向或者双向2.2 带头或者不带头2.3 循环或者不循环2.4 无头单向非循环链表和带头双向循环链表 3.单链表的实现3.1 准备工作3.2 节点的创建3.3 单链表的释放3.4 打印链表3.5 单链表的尾插3.6 单链表的尾删3.7 单链表头删3.8 单链…...
Python SciPy介绍
在数据科学和工程领域,Python已经成为了一个不可或缺的工具,这主要得益于其强大的库和框架支持。其中,SciPy库作为Python科学计算的核心库之一,为研究人员、工程师和数据分析师提供了大量高效的算法和数学工具。本文将带您深入了解…...
docker镜像源
1、直接在服务器上创建这个文件,将镜像源配置在里面 /etc/docker/daemon.json {"registry-mirrors": ["https://do.nark.eu.org","https://dc.j8.work","https://docker.m.daocloud.io","https://dockerproxy.com&qu…...

【clion】clion打开文件目录卡死问题
巨卡,几乎无法打开,据说是fsnotifier64.exe 被限制了。删除 火绒就好了。 关闭windows defender 官方:关闭 Windows 安全中心中的Defender 防病毒保护 此时,删除火绒: 界面变这样了:...
[CR]厚云填补_GridFormer
GridFormer: Residual Dense Transformer with Grid Structure for Image Restoration in Adverse Weather Conditions Abstract 恶劣天气条件下的图像恢复是计算机视觉中的一个难点。在本文中,我们提出了一种新的基于变压器的框架GridFormer,它可以作为…...
PostgreSQL数据库内核(二):通过initdb传递guc参数
目录 增加guc参数 initdb参数传递 pg_ctl参数传递 参数验证 新增guc参数pg_test_parameter,支持从initdb和pg_ctl命令中传递/覆盖参数,使用场景是TDE透明加密指定算法或者某些定制化需求。 增加guc参数 pg源码是这样描述guc参数的:它是全局…...
rust常用的宏使用记录(九)
matches! 宏使用 matches! 是 Rust 标准库中一个非常有用的宏,它允许你方便地匹配一个表达式的结果是否符合某个模式。它的基本用法如下:matches!(expression, pattern) 这个宏返回一个布尔值,如果 expression 匹配 pattern,则返回…...

【Python机器学习】支持向量机——手写数字识别问题
基于SVM的数字识别步骤: 1、收集数据:提供的文本文件 2、准备数据:基于二值图像构造向量 3、分析数据:对图像向量进行目测 4、训练算法:采用两种不同的核函数,并对径向基核函数采用不同的设置来运行SMO算法…...

学习笔记-Cookie、Session、JWT
目录 一、验证码的生成与校验 1. 创建生成验证码的工具类 2. 写一个 Controller 3. 实现验证码验证 1. 获取验证码 2. 验证码请求过程 3. 验证码的校验 4. 原理说明 5. 验证 6. 总结 二、JWT登录鉴权 1. 为什么要做登录鉴权? 2. 什么是 JWT 3. JWT相比…...

题海战术,面试必胜秘诀
目录 1.Java 的优势是什么?2.什么是 Java 的多态特性?3.Java 中的参数传递是按值还是按引用?4.为什么 Java 不支持多重继承?5.什么是 Java 中的不可变类?总结 题目 来自面试鸭刷题神器 1.Java 的优势是什么? Java 的跨平台性、垃圾回收机制以及其强…...
设计模式详解(十九)——命令模式
命令模式简介 命令模式定义 命令模式(Command Pattern)是一种在面向对象程序设计中常用的行为型设计模式。命令模式的核心思想在于将请求封装成一个对象,从而使发出请求的责任和执行请求的责任分割开。它可以让请求发送者和请求接收者之间消…...

实战:MySQL数据同步神器之Canal
1.概叙 场景一:数据增量实时同步 项目中业务数据量比较大,每类业务表都达到千万级别,虽然做了分库分表,每张表数据控制在300W以下,但是效率还是达不到要求,为了提高查询效率,打算使用ES进行数…...
5.6软件工程-运维
运维 系统转换系统维护系统评价练习题 系统转换 新老系统的转换 系统转换是指:新系统开发完毕,投入运行,取代现有系统的过程,需要考虑多方面的问题,以实现与老系统的交接,有一下三种转换计划: …...
在JavaScript中如何确保构造函数只被new调用
构造函数是一个特殊的函数,用于初始化一个新创建的对象。它是在创建对象时自动调用的。构造函数通常用于为对象的属性赋值,或者执行其他必要的设置。 使用函数名大写字母开头,这是一种命名约定,用于区分构造函数和普通函数。如何…...

【数据结构算法经典题目刨析(c语言)】反转链表(图文详解)
💓 博客主页:C-SDN花园GGbond ⏩ 文章专栏:数据结构经典题目刨析(c语言) 目录 一、题目描述 二、思路分析 三、代码实现 一、题目描述: 二、思路分析 : 通过三个指针n1,n2,n3来实现链表的反转 1.首先初始化 n1为…...

机器学习之争:Python vs R,谁更胜一筹?
一、引言 随着人工智能和大数据的迅速发展,机器学习已成为现代科技的重要组成部分。在医疗、金融、零售、制造等多个领域,机器学习技术的应用无处不在。从数据分析到预测建模,再到深度学习,机器学习正在改变我们的工作和生活方式…...

Vulnhub靶机:JANGOW_ 1.0.1
目录 前言: 一、安装虚拟机Jangow:1.0.1靶机 二、Web部分 前言: 难度:简单,本文使用VirtualBox打开,下载地址: https://download.vulnhub.com/jangow/jangow-01-1.0.1.ova 一、安装虚拟机J…...
Python脚本实现USB自动复制文件
USB驱动器作为常见的数据存储设备,经常用于数据传输和备份。 然而,我们在手动处理文件复制可能效率低下且容易出错。 因此,我们可以利用Python编写脚本来自动化这一过程,提高效率和数据安全性。 准备工作 首先,我们需…...

【C++学习第19天】最小生成树(对应无向图)
一、最小生成树 二、代码 1、Prim算法 #include <cstring> #include <iostream> #include <algorithm>using namespace std;const int N 510, INF 0x3f3f3f3f;int n, m; int g[N][N]; int dist[N]; bool st[N];int prim() {memset(dist, 0x3f, sizeof di…...

第一个 Flask 项目
第一个 Flask 项目 安装环境创建项目启动程序访问项目参数说明Flask对象的初始化参数app.run()参数 应用程序配置参数使用 Flask 的 config.from_object() 方法使用 Flask 的 config.from_pyfile() 方法使用 Flask 的 config.from_envvar() 方法步骤 1: 设置环境变量步骤 2: 编…...

简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...