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

数据结构-链表-单链表(3)

目录

1. 顺序表的缺陷

2. 单链表

2.1 单链表的基本结构与接口函数

2.2 重要接口

创建新节点的函数:

2.2.1 尾插

2.2.2 头插

2.2.3 尾删

2.2.4 头删

2.2.5 查找

2.2.6 插入

2.2.7 删除

2.2.8 从pos后面插入

2.2.9 从pos后面删除

3. 链表的缺陷与优势:

4. 链表与顺序表比较

写在最后:


1. 顺序表的缺陷

为什么会有链表?

我们都有顺序表来存储数据了,

因为顺序表是有缺陷的:

1. 中间头部插入删除数据,需要挪动数据,效率低下。

2. 空间不够需要扩容,扩容会有一定的消耗,也可能会造成空间的浪费。

这时候,我们就要用到链表。

2. 单链表

链表是一种物理存储结构上非连续、非顺序的存储结构,

数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

如下图: 

2.1 单链表的基本结构与接口函数

基本结构:

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLNode;//打印链表
void SLPrint(SLNode* phead);//尾插
void SLPushBack(SLNode** pphead, SLDataType x);//头插
void SLPushFront(SLNode** pphead, SLDataType x);//尾删
void SLPopBack(SLNode** ppheadx);//头删
void SLPopFront(SLNode** pphead);//查找
SLNode* SLFind(SLNode* phead, SLDataType x);//插入
void SLInsert(SLNode** phead, SLNode* pos, SLDataType x);//删除
void SLErase(SLNode** phead, SLNode* pos);//从pos后面插入
void SLInsertAfter(SLNode* pos, SLDataType x);//从pos后面删除
void SLEraseAfter(SLNode* pos);

2.2 重要接口

创建新节点的函数:

//建立一个新节点(重复操作写成函数复用)
SLNode* BuyNewNode(SLDataType x)
{//malloc一个链表节点大小的空间SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));//检查if (newnode == NULL){perror("malloc::fail");return;}//赋值newnode->data = x;newnode->next = NULL;return newnode;
}

2.2.1 尾插

//尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{//检查二级指针pphead地址是否为空	//方便检查是否传空指针了assert(pphead);//创建节点SLNode* newnode = BuyNewNode(x);//如果链表为空if (*pphead == NULL){*pphead = newnode;}else//如果链表不为空{//找尾SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}//尾插tail->next = newnode;}
}

2.2.2 头插

//头插
void SLPushFront(SLNode** pphead, SLDataType x)
{//检查二级指针pphead地址是否为空	//方便检查是否传空指针了assert(pphead);//创建节点SLNode* newnode = BuyNewNode(x);//头插newnode->next = *pphead;*pphead = newnode;
}

2.2.3 尾删

//尾删
void SLPopBack(SLNode** pphead)
{//检查二级指针pphead地址是否为空	//方便检查是否传空指针了assert(pphead);//检查链表是否为空assert(*pphead);//头删的情况(链表只有一个数据)if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找尾SLNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}//尾删free(tail->next);tail->next = NULL;}
}

2.2.4 头删

//头删
void SLPopFront(SLNode** pphead)
{//检查二级指针pphead地址是否为空	//方便检查是否传空指针了assert(pphead);//检查链表是否为空assert(*pphead);//头删SLNode* cur = (*pphead)->next;free(*pphead);*pphead = NULL;*pphead = cur;
}

2.2.5 查找

//查找
SLNode* SLFind(SLNode* phead, SLDataType x)
{//创建指针遍历链表SLNode* cur = phead;//查找while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

2.2.6 插入

//插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{//检查查找的地址是否为空assert(pos);//pos的位置if (pos == *pphead){SLPushFront(pphead, x);}else//在链表中间{SLNode* prev = *pphead;//查找pos对应位置while (prev->next != pos){prev = prev->next;}//插入SLNode* newnode = BuyNewNode(x);prev->next = newnode;newnode->next = pos;}
}

2.2.7 删除

//删除
void SLErase(SLNode** pphead, SLNode* pos)
{//检查二级指针pphead地址是否为空	//方便检查是否传空指针了assert(pphead);//检查查找的地址是否为空assert(pos);//检查链表是否为空(这里其实不断言也可以)assert(*pphead);//头删的情况if (*pphead == pos){SLPopFront(pphead);}else{//查找SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//删除prev->next = pos->next;free(pos);pos = NULL;}
}

2.2.8 从pos后面插入

//从pos后面插入
void SLInsertAfter(SLNode* pos, SLDataType x)
{//检查查找的地址是否为空assert(pos);//创建节点SLNode* newnode = BuyNewNode(x);//再pos后面插入newnode->next = pos->next;pos->next = newnode;
}

2.2.9 从pos后面删除

//从pos后面删除
void SLEraseAfter(SLNode* pos)
{//检查查找的地址和要删除的地址是否为空assert(pos);assert(pos->next);//在pos后面删除,prev记住要删除的节点,然后freeSLNode* prev = pos->next;pos->next = prev->next;free(pos->next);prev = NULL;
}

这就是单链表的基本框架和接口了,

如果感兴趣,你也可以使用接口函数玩一玩。

3. 链表的缺陷与优势:

但是链表是有缺陷的,

我们可以看到,

1. 链表想要访问一个节点,就得遍历链表,

2. 链表的尾删也需要遍历链表,

3. 而链表的优势是头删很方便是O(1)。

4. 链表与顺序表比较

我们就能跟顺序表比较一下,

1. 顺序表头插需要挪动数据是O(N),

2. 但是顺序表能随机访问。

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果喜欢本文的话,欢迎点赞和评论,写下你的见解。

如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。

之后我还会输出更多高质量内容,欢迎收看。

相关文章:

数据结构-链表-单链表(3)

目录 1. 顺序表的缺陷 2. 单链表 2.1 单链表的基本结构与接口函数 2.2 重要接口 创建新节点的函数&#xff1a; 2.2.1 尾插 2.2.2 头插 2.2.3 尾删 2.2.4 头删 2.2.5 查找 2.2.6 插入 2.2.7 删除 2.2.8 从pos后面插入 2.2.9 从pos后面删除 3. 链表的缺陷与优势&…...

【SpringBoot初级篇】JdbcTemplate常用方法

【SpringBoot初级篇】JdbcTemplate常用方法JdbcTemplate 查询JdbcTemplate 插入、更新、删除execute执行任意的SQLNamedParameterJdbcTemplate函数场景说明update(String sql, Nullable Object… args)增&#xff0c;删&#xff0c;改queryForObject(sql, Integer.class)查询返…...

React(三):脚手架、组件化、生命周期、父子组件通信、插槽、Context

React&#xff08;三&#xff09;一、脚手架安装和创建1.安装脚手架2.创建脚手架3.看看脚手架目录4.运行脚手架二、脚手架下从0开始写代码三、组件化1.类组件2.函数组件四、React的生命周期1.认识生命周期2.图解生命周期&#xff08;1&#xff09;Constructor&#xff08;2&…...

[教程]使用 Git 克隆指定分支

Git 是我们开发过程中经常使用到的版本管理工具,在平常情况下我们从远程克隆的时候会将整个库克隆下来&#xff0c;这会包括整个版本库的历史提交记录和远程库里的所有分支。但在一些情况下&#xff0c;比如我们并不需要查看历史提交记录而只是希望能够获取到最新的代码&#x…...

Redis实现服务注册与服务发现源码阅读(Go语言)

Redis实现服务注册与服务发现源码阅读 背景 近期在看开源项目CloudWeGo中看到目前GoLang微服务框架Hertz中支持通过Redis实现服务注册与服务发现功能。便想着阅读下源码 源码阅读 gut clone了hertz-contrib后看到在一级目录下有目前各种主流的服务注册与发现的实现方案。为…...

论文复现-3

模型构建中的运算 数据集是CONLL03 这个数据集共有4种实体类型&#xff0c;所以&#xff0c;在做实体描述的embedding时&#xff0c;得到的语义表示的Tensor大小为 &#xff1a; 4*max_len, 具体指的是&#xff1a; type_input_ids: torch.LongTensor None, type_attention_m…...

667知识点 | 经过三年实战检验的667知识清单

文章目录 前言第一章 信息与信息资源第二章 信息社会第三章 信息交流第四章 信息技术第五章 信息组织第六章 信息管理活动第七章 信息资源人文管理第八章 信息资源经济管理第九章 信息资源系统管理第十章 信息资源管理专门化前言 参考书目:《信息管理导论(第三版)》党跃武推…...

后端快速上手前端三剑客 HtmlCSSJavaScript

文章目录前言HTML1.基础标签2.多媒体标签&#xff1a;3.表格&列表&布局4.表单CSS1.简介2.导入方式3.选择器JavaScript1.简介2.引入方式3.基本语法4.对象(1) 基本对象(2) BOM对象(3) DOM对象5.事件前言 结构&#xff1a;HTML 表现&#xff1a;CSS 行为&#xff1a;Java…...

Cdiscount、Allegro如何利用测评补单自养号提升店铺权重和流量

Allegro成立于 1999 年是在波兰最受欢迎的电商平台&#xff0c;75%的波兰人都知道该网站&#xff0c;Allegro的品牌认知度在波兰高达98%。Allegro平台卖家的数量目前还是比较少的约为13万&#xff0c;最重要的就是中国卖家占比少&#xff0c;所以竞争也比较低&#xff0c;像是美…...

第16天-性能压测:压力测试,性能监控,优化QPS,Nginx动静分离

1.性能监控 1.1.JVM架构 运行时数据区&#xff1a; 方法区&#xff1a;最重要的内存区域&#xff0c;多线程共享&#xff0c;保存了类的信息&#xff08;名称、成员、接口、父类&#xff09;&#xff0c;反射机制是重要的组成部分&#xff0c;动态进行类操作的实现&#xff1b;…...

【python 基础篇 十一】python的函数-------函数的偏函数 高阶函数 返回函数 匿名函数 闭包

目录1.偏函数2.高阶函数3.返回函数4.匿名函数5.闭包1.偏函数 概念 ​ 当我们写一个参数比较多的函数时&#xff0c;如果有些参数&#xff0c;大部分场景下都是某一个固定值&#xff0c;那么为了简化使用&#xff0c;就可以创建一个新函数&#xff0c;指定我们要使用的函数的某个…...

妇女节到了,祝福所有女神 Happy Women‘s Day!

在每年&#xff13;月&#xff18;日人们庆祝妇女节 &#xff37;omens Day is cllebrated on March 8 every year.国际妇女节(IWD)&#xff0c;中国内地称“三八”国际劳动妇女节或国际劳动妇女节。是在每年的3月8日为庆祝妇女在经济、政治和社会等领域作出的重要贡献和取得的…...

etcd集群通过 Leader 写入数据,为什么K8s HA集群中讲每个 kube-apiserver 只和本机的 ETCD 通信

写在前面 对这个我不太明白&#xff0c;所有在 stackOverflow 的请教了大佬这里分享给小伙伴理解不足小伙伴帮忙指正 对每个人而言&#xff0c;真正的职责只有一个&#xff1a;找到自我。然后在心中坚守其一生&#xff0c;全心全意&#xff0c;永不停息。所有其它的路都是不完整…...

HTML 表单

HTML 表单和输入 HTML 表单用于收集不同类型的用户输入。 在线实例 创建文本字段 (Text field) 本例演示如何在 HTML 页面创建文本域。用户可以在文本域中写入文本。 创建密码字段 本例演示如何创建 HTML 的密码域。 &#xff08;在本页底端可以找到更多实例。&#xff09; …...

HTML、CSS学习笔记5(移动端基础知识、Flex布局)

一、移动端基础知识 1.PC端和移动端区别 移动端&#xff1a;手机版网页&#xff0c;手机屏幕小&#xff0c;网页宽度多数为100%&#xff0c;没有版心 PC端&#xff1a;电脑版网页&#xff0c;屏幕大&#xff0c;网页固定版心 PC端和移动端不是同一个网页 2.如何在电脑里面…...

【Java学习笔记】2.Java 开发环境配置

Java 开发环境配置 在本章节中我们将为大家介绍如何搭建Java开发环境。 window系统安装java 下载JDK 首先我们需要下载 java 开发工具包 JDK&#xff0c;下载地址&#xff1a;https://www.oracle.com/java/technologies/downloads/&#xff0c;在下载页面中根据自己的系统选…...

MyBatis——进阶操作(2)

标签 if标签 当提交的表单中有些为非必填项&#xff0c;用户并没有上传这些属性的值&#xff0c;那么程序可以上传NUll&#xff0c;也可以用if标签判断用户有没有上传这个值 <if test"参数!null">操作 </if>其中test中填写一条语句&#xff0c;如果得…...

循环结构

循环结构循环结构一、课前问答二、while循环三、do-while循环四、for循环五、流程控制5.1 break5.2 continue循环结构 一、课前问答 1、switch支持的数据类型。 2、switch中break的作用。 3、多重if如果多个条件都成立&#xff0c;执行方式。 二、while循环 语法&#xff1a; …...

漫谈数据库表设计及索引设计

一.数据库表设计 在数据库表设计上有个很重要的设计准则&#xff0c;称为范式设计。 什么是范式设计&#xff1f; 范式来自英文Normal Form&#xff0c;简称NF。MySQL是关系型数据库&#xff0c;但是要想设计—个好的关系&#xff0c;必须使关系满足一定的约束条件&#xff0c…...

【JavaWeb】CSS基础知识:引入方式 + 选择器

CSS引入 CSS的引入有三种&#xff0c;三种的优缺点各不相同。 行内样式表 <!-- 行内样式表 --><!-- 相当于标签的一个属性 --><!-- 只对当前标签生效 --><!-- 优先级较高&#xff0c;会覆盖其他样式 --><p style"color: blue;">这是…...

02-前端-javaScript

文章目录JavaScript1&#xff0c;JavaScript简介2&#xff0c;JavaScript引入方式2.1 内部脚本2.2 外部脚本3&#xff0c;JavaScript基础语法3.1 书写语法3.2 输出语句3.3 变量3.3.1 全局变量var3.3.2 局部变量let3.3.3 常量const3.4 数据类型3.5 运算符3.5.1 \和区别 ▲3.5.2 …...

对链表学习的总结一

一,单链表结构定义 C/C++ 数组:一组具有相同类型数据的集合。结构体:不同类型数据的集合。 // Definition for singly-linked list. struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next...

toSring()还有个高级用法好用

Object.prototype.toString()能够很好的判断数据的类型及内置对象 typeof xxx:能判断出number,string,undefined,boolean,object,function(null是object)Object.prototype.toString.call(xxx):能判断出大部分类型Array.isArray(xxx):判断是否为数组var test= Object.…...

Linux--多线程(3)

目录1. POSIX信号量1.1 概念2. 基于环形队列的生产消费者模型2.1 环形队列的基本原理2.2 基本实现思想3. 多生产多消费1. POSIX信号量 1.1 概念 信号量本质是一个计数器&#xff0c;申请了信号量以后&#xff0c;可以达到预定临界资源的效果。 POSIX信号量和SystemV信号量相同…...

【spring】事务

概述 1、什么事务 事务是数据库操作最基本单元&#xff0c;逻辑上一组操作&#xff0c;要么都成功&#xff0c;如果有一个失败所有操 作都失败 2、事务四个特性&#xff08;ACID&#xff09; &#xff08;1&#xff09;原子性 &#xff08;2&#xff09;一致性 &#xff08;3…...

博通仍然是美股市场最好的芯片半导体股

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 博通(AVGO)是一家快速增长的半导体公司&#xff0c;并且有很高的股息分红&#xff0c;目前其股息收益率已经高出了平均水平3.2%&#xff0c;而且估值非常合理&#xff0c;仅为预期净利润的14倍。 虽然博通也受到了经济衰退影…...

java开发手册之异常日志

文章目录异常日志异常处理日志规约异常日志 异常处理 1.Java 类库中定义的一类 RuntimeException可以通过预先检查进行规避&#xff0c;而不应该通过 catch 来处理 比如&#xff1a;IndexOutOfBoundsException&#xff0c;NullPointerException 等等。 说明&#xff1a;无法通…...

P6专题:关于P6 EPPM和PPM的区别及选型

目录 引言 什么是 Primavera P6 项目管理&#xff1f; Primavera P6 PPM 关键点 Primavera P6 PPM 是独立工具还是企业工具&#xff1f; 什么是 Primavera P6 企业项目组合管理&#xff1f; 那么EPPM的windows-tool呢&#xff1f; P6 EPPM 适合谁&#xff1f; 更多对比…...

亿万级海量数据去重软方法

文章目录原理案例一需求&#xff1a;方法案例二需求&#xff1a;方法&#xff1a;参考原理 在大数据分布式计算框架生态下&#xff0c;提升计算效率的方法是尽可能的把计算分布式话、并行化&#xff0c;避免单节点计算过载&#xff0c;把计算分摊到各个节点。这样解释小白能够…...

记录--手摸手带你撸一个拖拽效果

这里给大家分享我在网上总结出来的一些知识&#xff0c;希望对大家有所帮助 前言 最近看见一个拖拽效果的视频(抖音&#xff1a;艾恩小灰灰)&#xff0c;看好多人评论说跟着敲也没效果&#xff0c;还有就是作者也不回复大家提出的一些疑问&#xff0c;本着知其然必要知其所以然…...

wordpress 标签 文章/附近的成人电脑培训班

今天线上业务遇到一个问题&#xff0c;因为一张模拟自增序列的表被锁住&#xff0c;涉及该表的业务受到影响。线上情况&#xff1a;1、这个表只有一个id字段。2、id字段为主键索引3、该表只有一行数据&#xff0c;记录全局最大id4、某业务存储过程操作会执行id1操作&#xff0c…...

不用ftp可以做网站吗/深圳百度推广关键词推广

Next.js 教程阐述标签式导航 Router模块进行跳转阐述 学完如何编写组件和页面后&#xff0c;下一步应该了解的就是路由体系&#xff0c;每个框架都有着不同的路由体系&#xff0c;本文先学习最基础的页面如何跳转。 页面跳转一般有两种形式&#xff1a; 第一种是利用标签 <…...

wordpress+主题页脚/网络营销策划书格式

文章目录1、文件和目录的默认权限2、umask 默认权限&#xff08;1&#xff09;查看系统的umask权限&#xff08;2&#xff09;用八进制数值显示umask权限&#xff08;3&#xff09;umask权限的计算方法&#xff08;4&#xff09;注意&#xff1a;umask 默认权限的计算绝不是数字…...

那些网站做汽车可靠性/站长之家ping检测

通过log打印出来的信息很快就一闪而过了&#xff0c;着实很郁闷。这里通过更改logcat的缓存数解决的&#xff0c;eclipse默认是5000&#xff0c;我将其改成了50000。 转载于:https://www.cnblogs.com/xiaofeng6636/p/4931913.html...

2012r2网站建设/网站如何优化排名

基于 Vue ElementUI 的web项目工程框架。专注于中台系统快速搭建&#xff0c;框架已在多个项目实战检验。 特色&#xff1a;搭载代码生成器&#xff0c;可生成底层api调用、vuex管理、模拟数据代码&#xff1b;内置常用超过80个基础UI组件&#xff1b;集成图表库、地图应用类库…...

广州网站建设第一公司/小说关键词提取软件

摘要&#xff1a;从零开始写爬虫&#xff0c;初学者的速成指南&#xff01; 本期我们来聊聊URL去重那些事儿。以前我们曾使用Python的字典来保存抓取过的URL&#xff0c;目的是将重复抓取的URL去除&#xff0c;避免多次抓取同一网页。爬虫会将待抓取的URL放在todo队列中&#x…...