【数据结构】链表篇

文章目录

  • 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)		只需修改指针指向
插入动态顺序表，空间不够时需要
扩容		没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率高低

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/391042.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

TiDB系列之：TiCDC同步TiDB数据库数据到Kafka集群Topic

TiDB系列之：TiCDC同步TiDB数据库数据到Kafka集群Topic

TiDB系列之&#xff1a;TiCDC同步TiDB数据库数据到Kafka集群Topic 一、Changefeed 概述Changefeed 状态流转操作 Changefeed 二、同步数据到Kafka创建同步任务&#xff0c;复制增量数据 KafkaSink URI 配置 kafka最佳实践TiCDC 使用 Kafka 的认证与授权TiCDC 集成 Kafka Connec…
阅读更多...
搭建高可用OpenStack（Queen版）集群（一）之架构环境准备

搭建高可用OpenStack（Queen版）集群（一）之架构环境准备

一、搭建高可用OpenStack&#xff08;Queen版&#xff09;集群之架构环境准备 一、架构设计 二、初始化基础环境 1、管理节点创建密钥对&#xff08;方便传输数据&#xff09; 所有控制节点操作 # ssh-keygen #一路回车即可 Generating public/private rsa key pair. Enter f…
阅读更多...
算法通关：016：设计循环双端队列

算法通关：016：设计循环双端队列

文章目录 题目思路代码运行结果问题为什么能直接调用方法名 题目 leetcode641 设计循环双端队列 思路 代码 import java.util.Deque; import java.util.LinkedList;/*** Author: ggdpzhk* CreateTime: 2024-08-03* 641 双端队列&#xff1a;利用双向链表和动态数组实现*/ pu…
阅读更多...
C#和S7-1200PLC S7.NET通信

C#和S7-1200PLC S7.NET通信

1、一步步建立一个C#项目 一步步建立一个C#项目(连续读取S7-1200PLC数据)_s7协议批量读取-CSDN博客文章浏览阅读1.7k次，点赞2次，收藏4次。这篇博客作为C#的基础系列，和大家分享如何一步步建立一个C#项目完成对S7-1200PLC数据的连续读取。首先创建一个窗体应用。_s7协议批量…
阅读更多...
【uniapp离线打包】（基于Android studio）

【uniapp离线打包】（基于Android studio）

文章目录 uniapp打包官方教程入口一、准备工作(工具三大件)Android Studio版本推荐 二、准备工作&#xff08;Android壳和uniapp包&#xff09;导入Android壳生成uniapp包将uniapp包导入android壳降低jdk版本 三、准备工作&#xff08;证书&#xff09;准备Android平台离线签名…
阅读更多...
SpringSecurity-1（认证和授权+SpringSecurity入门案例+自定义认证+数据库认证）

SpringSecurity-1（认证和授权+SpringSecurity入门案例+自定义认证+数据库认证）

SpringSecurity 1 初识权限管理1.1 权限管理的概念1.2 权限管理的三个对象1.3 什么是SpringSecurity 2 SpringSecurity第一个入门程序2.1 SpringSecurity需要的依赖2.2 创建web工程2.2.1 使用maven构建web项目2.2.2 配置web.xml2.2.3 创建springSecurity.xml2.2.4 加载springSe…
阅读更多...
50 选择结构

50 选择结构

常见的选择结构有单分支选择结构、双分支选择结构、多分支选择结构及嵌套的分支结构&#xff0c;也可以构造跳转表来实现类似的逻辑。循环结构和异常处理结构中也可以实现带有 else 子句&#xff0c;可以看作特殊形式的选择结构。 所有的 Python 合法表达式都可以作为条件表达…
阅读更多...
一篇文章让你搞懂原码，反码，补码！

一篇文章让你搞懂原码，反码，补码！

目录 1.机器数和机器数真值 1.1机器数 1.2机器数的真值 2.原码&#xff0c;反码&#xff0c;补码的计算方法 2.1原码 2.2反码 2.3补码 3.为什么要使用反码和补码&#xff1f; 3.1原码不能让符号位参与运算的问题&#xff1a; 3.2为了解决原码作减法&#xff0c;引入…
阅读更多...
SAP支出管理，企业成本控制的智能钥匙

SAP支出管理，企业成本控制的智能钥匙

在企业运营中&#xff0c;有效的支出管理是确保财务健康和提升竞争力的关键。SAP支出管理系统作为企业资源规划的核心组成部分&#xff0c;提供了一套全面的解决方案&#xff0c;帮助企业实现成本控制、风险管理和合规性监督。实现支出管理流程自动化&#xff0c;并主动管理更多…
阅读更多...
python爬虫预备知识三-序列化和反序列化

python爬虫预备知识三-序列化和反序列化

序列化和反序列化 序列化是为了将内存中的数据保存在磁盘上或者用于传输&#xff0c;实现程序状态的保存和共享。反序列化反之。 序列化后的变量再被反序列化回来之后&#xff0c;两者之间已经没有任何关系。 序列化后的文件是在不同程序或者说不同语言之间传递数据的关键方…
阅读更多...
分享5款.NET开源免费的Redis客户端组件库

分享5款.NET开源免费的Redis客户端组件库

前言 今天大姚给大家分享5款.NET开源、免费的Redis客户端组件库&#xff0c;希望可以帮助到有需要的同学。 StackExchange.Redis StackExchange.Redis是一个基于.NET的高性能Redis客户端&#xff0c;提供了完整的Redis数据库功能支持&#xff0c;并且具有多节点支持、异步编…
阅读更多...
[Git][分支管理][上]详细讲解

[Git][分支管理][上]详细讲解

目录 1.理解分支2.创建分支3.切换分支4.合并分支5.删除分支 1.理解分支 感性理解&#xff1a;分支可以理解为平行宇宙&#xff0c;但是在用户需要的时候&#xff0c;可以将两个平行宇宙合并&#xff0c;此时两个平行宇宙的效果将会"叠加"理性理解&#xff1a;每次提…
阅读更多...
TCP 和 UDP 之间的区别？

TCP 和 UDP 之间的区别？

从 连接&#xff0c;可靠性&#xff0c;传输方式等方面&#xff1a; TCP 是面向连接的协议&#xff0c;在发送数据的时候需要先通过 TCP 的三次握手&#xff0c;而 UDP 是无连接的协议&#xff0c;可以直接传输数据TCP 通过超时重传&#xff0c;流量控制和拥塞控制等方法保障了…
阅读更多...
使用JWT的SpringSecurity实现前后端分离

使用JWT的SpringSecurity实现前后端分离

1. SpringSecurity完成前后端完全分离 分析&#xff1a; 前后端分离&#xff1a;响应的数据必须为JSON数据&#xff0c;之前响应的是网页 需要修改的代码有&#xff1a; 登录成功需要返回json数据登录失败需要返回json数据权限不足时返回json数据未登录访问资源返回json数据 1.…
阅读更多...
二叉树的前序遍历 - 力扣（LeetCode）C语言

二叉树的前序遍历 - 力扣（LeetCode）C语言

144. 二叉树的前序遍历 - 力扣&#xff08;LeetCode&#xff09;(点击前面链接即可查看题目) 一、题目 给你二叉树的根节点 root &#xff0c;返回它节点值的 前序 遍历。 示例 1&#xff1a; 输入&#xff1a;root [1,null,2,3] 输出&#xff1a;[1,2,3]示例 2&#xff1a; …
阅读更多...
文心智能体【MBTI速测小精灵】：趣味速测，精准解析你的性格密码！

文心智能体【MBTI速测小精灵】：趣味速测，精准解析你的性格密码！

文章目录 一、文心智能体平台是什么&#xff1f;二、创建文心智能体智能体创建智能体调试分析智能体基础配置智能体高级配置智能体高级调试 三、文心智能体发布四、文心智能体体验总结 一、文心智能体平台是什么&#xff1f; AgentBuilder文心智能体平台是基于文心大模型的智能…
阅读更多...
适用于 Android 的 6 大视频恢复软件榜单 – 恢复您的珍贵回忆！

适用于 Android 的 6 大视频恢复软件榜单 – 恢复您的珍贵回忆！

失去珍贵的回忆可能是一种令人心碎的经历&#xff0c;尤其是在您的 Android 设备上拍摄视频时。无论是由于意外删除、格式化、系统崩溃还是任何其他不可预见的情况&#xff0c;丢失珍贵视频的想法都会造成巨大的痛苦。但不要担心&#xff01;在这篇博文中&#xff0c;我们将深入…
阅读更多...
临床随机对照试验中的分层问题及其解决方法

临床随机对照试验中的分层问题及其解决方法

在临床随机对照试验&#xff08;Randomized Controlled Trials, RCTs&#xff09;中&#xff0c;分层问题&#xff08;Stratification Issues&#xff09;是影响研究结果有效性的重要因素之一。RCTs是评估医疗干预效果的金标准&#xff0c;旨在通过随机分组和对照来消除干扰因素…
阅读更多...
在亚马逊云科技AWS上利用ElasticSearch和RAG搭建个性化推荐系统

在亚马逊云科技AWS上利用ElasticSearch和RAG搭建个性化推荐系统

简介&#xff1a; 小李哥将继续每天介绍一个基于亚马逊云科技AWS云计算平台的全球前沿AI技术解决方案&#xff0c;帮助大家快速了解国际上最热门的云计算平台亚马逊云科技AWS AI最佳实践&#xff0c;并应用到自己的日常工作里。 本次介绍用当下热门的RAG和大语言模型&#xf…
阅读更多...
[WUSTCTF2020]朴实无华1

[WUSTCTF2020]朴实无华1

打开题目 扫目录用dirsearch扫&#xff0c;为节省建议只扫常见的目录&#xff0c;配置是&#xff1a; ./dirsearch.py -e bak,zip,txt,tgz,php -u http:..... -s 3 -t 20 访问一下 根据提示&#xff0c;再访问一次 提示不在这&#xff0c;抓包看看 根据提示&#xff0c;改ge…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023