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

顺序表以及链表的应用及区别(包含OJ讲解)

前面我已经发过怎么实现链表以及顺序表,今天大概的总结一下。

顺序表:

1.能够随时的存取,比较方便。

2.插入删除时,需要挪动数据,比较麻烦,因为是连续存储。

3.存储密度相对于链表来说是比较高的(存储单个字符的时候)。

4.如果首次开辟的空间不够用,后续还要继续扩容空间。比较麻烦。

链表:

1.存储密度相比于顺序表比较低(存储单个字符时)。

2.插入删除数据时,不需要挪动数据,这个方便。

3.插入数据时,如果是尾插,则要遍历整个链表,比较麻烦。也就是不支持随机访问。

4.不存在空间不够的情况,只要插入数据就申请空间,不存在浪费空间。

综上所述:

如果题目要求的是频繁的插入数据或是删除数据,我们应该要选择链表,而如果题目要的是频繁的查找数据,我们则要的是顺序表。根据他们的优缺点来进行取舍。

应用:

它们应用的地方在数据结构中很广泛,比如后面的串,队列,栈等等都会运用到。所以,个人认为这个是学数据结构的基础。

栈:其实栈以用链表表示,也可以用顺序表表示,但是我们知道栈的使用规则是先使用高地址,后使用低地址,而且还是先进后出的(也是后进先出,表示方法:LIFO或FILO)。也就是说,可栈顶的元素是先出的,所以这样就行了我们所说的压栈,所以,再用链表表示时,我们只能用头插法和头删法,这样的是不用遍历链表的,时间复杂度是O(1).此种情况是不带头节点不循环的单链表。所以,我们选择顺序表来表示栈更好一点。直接用尾插,既不用遍历数组,也不用挪动数据,使用起来更加方便。

队列:队列是先进先出的,也就是FIFO。他其实也可以用这两种方法分别表示,如果用链表来表示的话,适合用尾插法,头删法,这样就可以保证FIFO。插入和删除的时间复杂度都是O(1)。复合队列的规则。如果用顺序表的话,不考虑循环队列,删除数据时,要把挪动数据,相对于链表来说是比较麻烦的(也可以不用挪动数据,但是这样就必须要挪动队列的头)。所以个人认为不是循环队列的话,还是用链表比较好。

串:

串的话个人认为两个表示方法没有什么区别,因为保存的是字符,所以用链表表示的话存储密度低,如果用顺序表的话,七朵多种用顺序表表示的方法,具体还是得看自己选哪一个,具体的哪几种方法就不想细说了,感兴趣的可以私聊我,共同探讨一下。

所以,综上所述:在链表和顺序表中如何选择,就看那个比较好,方便满足条件。

上面总结了顺序表和链表的应用,下面说说栈的应用:不用说其实大家首先想到应该就是递归了,因为递归很容易导致栈溢出,所以,首当其冲的就是递归了。其次就是上次我说的那个前/后缀表达式计算,下来就是中缀表达式如何转后/前缀表达式,都是可以运用栈思想的。还有就是括号的匹配,让我们看看下面的题:

就是匹配,核心思想就是创建栈,遇见左括号就压入栈中,直到遇见右括号就停止,然后是取出栈中的元素,跟这个右括号匹配,匹配成功就继续,不成功就输出false。下面是实现的代码:

 

总体实现的代码在上,有更好的方法希望大家评论区指出,这道题我用顺序表实现的栈,如果用链表也可以,不过此时就要写一个申请节点空间的函数,每次压栈的时候,都要调用次函数来申请节点,所以我就用了静态的顺序表来实现,直接一次性开劈大点 (浪费了很多空间)。

最后的总结:

链表的核心思想就是插入删除查找等,方法都是一样的。顺序表就更不用说了,大部分题型都可以用数组的方法来做。

最后,如果本篇文章对你有帮助的话就点一下赞,支持一下吧!!!!!

相关文章:

顺序表以及链表的应用及区别(包含OJ讲解)

前面我已经发过怎么实现链表以及顺序表,今天大概的总结一下。 顺序表: 1.能够随时的存取,比较方便。 2.插入删除时,需要挪动数据,比较麻烦,因为是连续存储。 3.存储密度相对于链表来说是比较高的&#…...

JVM简介

一、什么是JVM JVM是Java Virtual Machine(Java虚拟机)的缩写,JVM是一种用于计算设备的规范,它是一个虚构出来的计算机,是通过在实际的计算机上仿真模拟各种计算机功能来实现的。 Java语言的一个非常重要的特点就是与平…...

Leetcode.1653 使字符串平衡的最少删除次数

题目链接 Leetcode.1653 使字符串平衡的最少删除次数 Rating &#xff1a; 1794 题目描述 给你一个字符串 s&#xff0c;它仅包含字符 a和 b​​​​ 。 你可以删除 s中任意数目的字符&#xff0c;使得 s平衡 。当不存在下标对 (i,j)满足 i < j&#xff0c;且 s[i] b的同…...

leetcode 71~80 学习经历

leetcode 71~80 学习经历71. 简化路径72. 编辑距离73. 矩阵置零74. 搜索二维矩阵75. 颜色分类76. 最小覆盖子串77. 组合78. 子集79. 单词搜索80. 删除有序数组中的重复项 II小结71. 简化路径 给你一个字符串 path &#xff0c;表示指向某一文件或目录的 Unix 风格 绝对路径 &am…...

使用metrics-server监控k8s的资源指标

首先&#xff0c;欢迎使用DHorse部署k8s应用。 k8s可以通过top命令来查询pod和node的资源使用情况&#xff0c;如果直接运行该命令&#xff0c;如下所示。 [rootcentos05 deployment]# kubectl top pod W0306 15:23:24.990550 8247 top_pod.go:140] Using json format to …...

【Copula】考虑风光联合出力和相关性的Copula场景生成(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

【java基础】泛型程序设计基础

文章目录泛型是什么自定义泛型类自定义泛型方法类型变量的限定总结泛型是什么 泛型类和泛型方法有类型参数&#xff0c;这使得它们可以准确地描述用特定类型实例化时会发生什么。在没有泛型类之前&#xff0c;程序员必须使用Objct编写适用于多种类型的代码。这很烦琐&#xff…...

【省选模拟测试23 T1直径】更好的做法

题目大意和普通做法 省选模拟测试23 T1直径 题解 对于上文中有三个儿子的根节点的树&#xff0c;其直径数量为abbccaabbccaabbcca。那么对于上文中有nnn个儿子的根节点的树&#xff0c;其直径数量为多少呢&#xff1f; 每个儿子所在子树中的点与其他儿子所在子树中的点都能组…...

SpringCloud基础(3)-微服务远程调用

SpringCloud基础1. 微服务的远程调用2. Eureka注册中心1. 搭建Eureka服务注册中心1. 微服务的远程调用 服务提供者&#xff1a;一次业务中被其它服务调用的一方&#xff1b; 服务消费者&#xff1a;一次业务中调用其它服务的一方&#xff1b; 2. Eureka注册中心 记录所有服务…...

10.单点登录原理及JWT实现

单点登录原理及JWT实现 一、单点登录效果 首先我们看通过一个具体的案例来加深对单点登录的理解。案例地址&#xff1a;https://gitee.com/xuxueli0323/xxl-sso?_fromgitee_search 把案例代码直接导入到IDEA中 然后分别修改下server和samples中的配置信息 在host文件中配置 …...

图表控件LightningChart.NET 系列教程(十一):LightningChart 组件——添加至 Blend WPF 项目

LightningChart.NET 是一款高性能 WPF 和 Winforms 图表,可以实时可视化多达1万亿个数据点。可有效利用CPU和内存资源&#xff0c;实时监控数据流。同时&#xff0c;LightningChart使用突破性创新技术&#xff0c;以实时优化为前提&#xff0c;大大提升了实时渲染的效率和效果&…...

libGDX:灯光效果实现一(实现一个点光源)

国内的libGDX文章很少&#xff0c;特别是libGDX实现灯光效果&#xff0c;所以就开始总结灯光效果的实现 绿色的框 是为了方便看到Body位置&#xff0c;使用Box2DDebugRenderer渲染的 工欲善其事&#xff0c;必先利其器&#xff0c;工具集合 gdx-setup.jar 1. 从libGDX官网下载…...

Java生态/Redis中如何使用Lua脚本

文章目录一、安装LUA1&#xff09;简单使用二、lua语法简介1、注释1&#xff09;单行注释2&#xff09;多行注释2、关键字3、变量1&#xff09;全局变量2&#xff09;局部变量4、数据类型1&#xff09;Lua数组2&#xff09;字符串操作5、if-else6、循环1&#xff09;for循环1&g…...

网络编程 socket 编程(一)

1. C/S 架构 C/S 架构即客户端/服务端架构&#xff0c;B/S 架构&#xff08;浏览器与服务端&#xff09;也是 C/S 架构的一种。 C/S 架构与 socket 的关系&#xff1a;学习 socket 可以完成 C/S 架构的开发。 2. osi 七层 一个完整的计算机系统由硬件、操作系统以及应用软件…...

【SpringCloud】SpringCloud教程之Nacos实战(一)

目录Nacos是什么&#xff1f;一.Nacos下载二.安装Nacos三.Nacos原理四.Nacos快速入门五.Nacos服务多级存储模式六.Nacos根据集群设置负载均衡1.根据同集群优先访问2.根据权重配置负载均衡七.Nacos的环境隔离八.Nacos和Eureka的区别前提&#xff1a;以订单服务和用户服务为例&am…...

高通Android 12/13 默认应用程序授予权限

1、一提到权限很多Android开发者都会想到 比如拨打电话 读取手机通讯录 定位 这些都是需要申请权限&#xff0c;Google Android 6.0之后&#xff08;sdk 23&#xff09; 需要app动态申请权限 或者权限组 2、我这里打个比方 比如需要在fm应用 默认打开mic权限 3、我们需要知道…...

代码随想录|day6|哈希表篇-- 242.有效的字母异位词 、349. 两个数组的交集 、202. 快乐数、1. 两数之和

总链接https://docs.qq.com/doc/DUEtFSGdreWRuR2p4?u329948d2f0044f34b7cbe72503f0b572 242.有效的字母异位词 链接&#xff1a;代码随想录 class Solution { public:bool isAnagram(string s, string t) {//两种做法&#xff0c;一种是int f[26]的数组,一种是map /*第一种&a…...

k8s学习之路 | Day20 k8s 工作负载 Deployment(下)

文章目录3. HPA 动态扩缩容3.1 HPA3.2 安装 metrics-server3.3 验证指标收集3.4 扩缩容的实现3.5 增加负载3.6 降低负载3.7 更多的度量指标4. 金丝雀部署4.1 蓝绿部署4.2 金丝雀部署4.3 金丝雀部署的实现5. Deployment 状态与排查5.1 进行中的 Deployment5.2 完成的 Deployment…...

考研复试——操作系统

文章目录操作系统1. 操作系统的特征&#xff1a;2. 进程与线程的关系以及区别3. 简述进程和程序的区别4. 进程的常见状态&#xff1f;以及各种状态之间的转换条件&#xff1f;5. 进程的调度算法有哪些&#xff1f;6. 什么是死锁&#xff1f;产生条件&#xff1f;如何避免死锁&a…...

Java ~ Collection/Executor ~ LinkedBlockingDeque【源码】

一 LinkedBlockingDeque&#xff08;链接阻塞双端队列&#xff09;类源码及机制详解 类 LinkedBlockingDeque&#xff08;链接阻塞双端队列&#xff09;类&#xff08;下文简称链接阻塞双端队列&#xff09;是BlockingDeqeue&#xff08;阻塞双端队列&#xff09;接口的唯一实现…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

机器学习的数学基础:线性模型

线性模型 线性模型的基本形式为&#xff1a; f ( x ) ω T x b f\left(\boldsymbol{x}\right)\boldsymbol{\omega}^\text{T}\boldsymbol{x}b f(x)ωTxb 回归问题 利用最小二乘法&#xff0c;得到 ω \boldsymbol{\omega} ω和 b b b的参数估计$ \boldsymbol{\hat{\omega}}…...

Windows 下端口占用排查与释放全攻略

Windows 下端口占用排查与释放全攻略​ 在开发和运维过程中&#xff0c;经常会遇到端口被占用的问题&#xff08;如 8080、3306 等常用端口&#xff09;。本文将详细介绍如何通过命令行和图形化界面快速定位并释放被占用的端口&#xff0c;帮助你高效解决此类问题。​ 一、准…...

云原生安全实战:API网关Envoy的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关 作为微服务架构的统一入口&#xff0c;负责路由转发、安全控制、流量管理等核心功能。 2. Envoy 由Lyft开源的高性能云原生…...