数据结构(Java):LinkedList集合Stack集合

1、集合类LinkedList

1.1 什么是LinkedList

LinkedList的底层是一个双向链表的结构(故不支持随机访问):

在LinkedList中,定义了first和last,分别指向链表的首节点和尾结点。

每个节点中有一个成员用来存储数据,还有两个指针域next和prev分别存储下一个节点和上一个节点的地址。

LinkedList也实现了List接口。

1.2 LinkedList的有关方法

1.2.1 构造方法

第二个构造方法的使用和ArrayList是相同的,可以使用实现了Collection接口并且泛型上界为E的集合类来构造LinkedList。

1.2.2 常用方法

1.3 ArrayList和LinkedList的区别

最重要的区别就是 ArrayList底层结构是数组;而,LinkedList的底层结构是双向链表。


2、集合类Stack

Stack是Java为我们封装好的一个“栈”,要想学习Stack,我们需要想了解栈是什么。

2.1 栈

栈,是一种数据结构,是一种特殊的线性表,只允许在固定的一端(栈顶)进行元素的插入和删除操作,栈中的元素具有“先进后出”的特点。

元素进栈,成为压栈、入栈

元素出栈,称为出栈

2.1.1 栈的实现

数组、单链表、双链表都可以实现栈,但是哪一种更好呢?

我们知道,元素出栈和入栈,必须在栈顶操作,那么:

  • 对于数组,直接让size--或size++就可以,时间复杂度为O(1)。
  • 对于单链表,如果采用尾插法入栈(即首节点定义为栈底,尾结点定义为栈顶),那么入栈和出栈需要找到尾结点才能继续操作,时间复杂度为O(n)。即使定义了last指向尾结点,入栈可改善为O(1),而出栈依然为O(n)。但是,如果采用头插法入栈的话,入栈操作和出栈操作,均会改善为O(n)。
  • 对于双向链表,无论是入栈还是出栈,时间复杂度均为O(1)。

2.2 Stack的实现

我们上面提到数组、单链表头插入栈、双链表都可以很好的实现栈,

而集合类Stack的底层结构是数组。

2.3 Stack的常用方法

  • pop() 将栈顶的元素取出,即出栈,同时返回栈顶的元素。
  • peek() 仅仅获取栈顶的元素,不会将元素出栈
  • empty()是Stack特有的判断栈是否为空的方法;Stack继承下来的isEmpty()方法也具有相同的作用
  • LinkedList中也有栈相关的方法,故也可以使用LinkedList来构建栈

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

postgresql简单导出数据与手动本地恢复(小型数据库)

问题 需要每天手动备份postgresql。 步骤 导出数据 /opt/homebrew/opt/postgresql16/bin/pg_dump --file/Users/zhangyalin/backup_sql/<IP地址>_pg-2024_07_15_17_30_15-dump.sql --dbname<数据库名> --username<用户名> --host<IP地址> --port54…

Python array的特点及使用

1、Python array的特点及使用 1.1、python array为什么只能接收指定类型数据 array 模块提供了一种叫做 array 的数据结构&#xff0c;它表示一块连续的内存空间&#xff0c;所有的元素必须是相同的类型。这是因为在内存中&#xff0c;数组元素存储在连续的位置上&#xff0c…

【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 游乐园门票 (200分) - 三语言AC题解(Python/Java/Cpp)

&#x1f36d; 大家好这里是清隆学长 &#xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&#x1f497; 最新华为O…

数据结构java笔记

线性表 数组 物理地址连续、逻辑地址连续。数组长度是固定的&#xff0c;不能动态增长或缩小&#xff0c;数组中元素的类型相同&#xff08;适合用于元素个数固定&#xff0c;且快速用下标访问&#xff09; ArrayList&#xff08;动态数组&#xff09; 物理地址连续、逻辑地…

【C++练级之路】【Lv.26】类型转换

快乐的流畅&#xff1a;个人主页 个人专栏&#xff1a;《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火&#xff0c;在为久候之人燃烧&#xff01; 文章目录 一、C风格类型转换1.1 隐式类型转换1.2 显式类型转换 二、C风格类型转换2.1 static_cast2.2 dynamic_cast2.3…

【C++】—— 初识C++

【C】—— 初识C 一、什么是 C二、C 的发展历史三、C 版本更新四、C 的重要性五、C 在工作领域中的运用六、C 书籍推荐&#xff1a; 一、什么是 C C语言 是结构化和模块化的语言&#xff0c;适合处理较小规模的程序。对于复杂的问题&#xff0c;规模较大的程序&#xff0c;需要…

【eNSP模拟实验】单臂路由实现VLAN间通信

实验需求 如下图所示&#xff0c;辅导员办公室需要访问处在不同vlan的学生管理服务器的文件&#xff0c;那么如何实现两台终端相互通信呢&#xff1f;我们可以使用单臂路由的方式来实现。 单臂路由&#xff08;router-on-a-stick&#xff09;是指在路由器的一个接口上通过配置…

小型医疗门诊挂号收费后台系统源码 医院管理系统后台thinkphp内核源码(带微信登录)

源码简介&#xff1a; 好用的小型医疗门诊后台管理系统的源码&#xff0c;就是那种医院管理用的&#xff0c;核心是用thinkphp做的。这个系统源码啊&#xff0c;功能多&#xff0c;用起来也方便。它还支持第三方配置和微信登录。 这玩意儿是基于ThinkPHP搞出来的医疗门诊系统…

AJAX知识点(详解)

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 非常期待和您一起在这个小…

Flowable-流程图标与流程演示

BPMN 2.0是业务流程建模符号2.0的缩写。它由Business Process Management Initiative这个非营利协会创建并不断发展。作为一种标识&#xff0c;BPMN 2.0是使用一些符号来明确业务流程设计流程图的一整套符号规范&#xff0c;它能增进业务建模时的沟通效率。目前BPMN2.0是最新的…

持续集成01--Git版本管理及基础应用实践

前言 本系列文章旨在深入探讨持续集成/持续部署&#xff08;Continuous Integration/Continuous Deployment, CI/CD&#xff09;流程中的各个环节&#xff0c;而本篇将聚焦于Git版本管理及其基本应用。通过本文&#xff0c;读者将了解到Git的基本原理、安装配置、基本命令以及如…

高校动作捕捉与数字人开发实训室方案:助推高校开设虚拟数字人微专业

目前一些学校除了传统的实训室建设之外&#xff0c;部分院校会建设一些“微专业”&#xff0c;专业方向与AIGC以及虚拟数字人有关&#xff0c;通过引进一些虚拟数字人以及全身动作捕捉设备相关的产品和系统工具&#xff0c;进行设计课程方案&#xff0c;比如虚拟人直播&#xf…

Vue3学习体验(一)

搭建工程 使用vue-cli脚手架创建vue3工程 vue create vue3-app-vue-cliVue-cli官网&#xff1a;https://cli.vuejs.org/zh/guide/installation.html 使用vite搭建vue3工程 npm init表示临时的下载vite应用来创建vue3工程&#xff0c;工程名称为vue3-app-vite npm init vit…

银河麒麟高级服务器操作系统V10加固操作指南

1:检查系统openssh安全配置: 2:检查是否设置口令过期前警告天数: 3:检查账户认证失败次数限制: 修改/etc/pam.d/system-auth文件中deny的参数即可 4:检查是否配置SSH方式账户认证失败次数限制:

SAP DR创建借项凭证简介

DR创建借项凭证简介 创建借项凭证请求的详细步骤1. 进入创建销售订单的界面2. 选择销售凭证类型3. 输入销售组织数据4. 输入客户和参考数据5. 添加项目明细6. 检查和保存创建实际的借项凭证借项凭证后台配置定义凭证类型定义项目类别定义销售开票类型借项凭证请求的业务意义跟踪…

@RequestBody注解的使用及源码解析

前言 RequestBody 注解是我们进行JavaEE开发&#xff0c;最常见的几个注解之一&#xff0c;这篇博文我们以案例和源码相结合&#xff0c;帮助大家更好的了解 RequestBody 注解 使用案例 1.自定义实体类 Data NoArgsConstructor AllArgsConstructor public class User {priv…

非对称加解密和签名

非对称加解密特点 一对密钥&#xff0c;公钥和私钥。私钥自己持有&#xff0c;公钥公开给通信的对方。 如果公钥用作加密&#xff0c;那么私钥用作解密。 如果私钥用做加密&#xff0c;那么公钥用作解密。 如果数据量少可用非对称加密算法直接加密。 如果数据量大&#xff0c;…

【双色转模拟调光磁吸灯应用方案】调光线性度好 调光频率1K以上都兼容 LED护眼教室黑板灯降压恒流驱动IC芯片FP7195

文章目录 前言 一、行业要求和痛点 1、设计空间小&#xff0c;双路调光调色不容易排布 2、磁场对调光的影响 二、FP7195如何解决这些要求和痛点 1、FP7195实际应用双色温调光电路框架 2、FP7195的转模拟调光技术 总结 前言 磁吸灯作为一种时尚、实用的家居装饰灯具&#xff0c;…

javaweb学习

javaweb就是实现浏览器和服务器之间的交互 1、服务器配置 Run->Edit Configurations&#xff0c;点击右上角的号&#xff0c;选择Tomcat Server的local&#xff1a; 选择server下的Configure...&#xff0c;在弹出的界面里点击有上角的号&#xff0c;选择自己解压的合适的t…

220V降压5ⅤIC-AH8652

220V降压至5V的IC - AH8652 在电子设计中&#xff0c;电压转换是一个常见的需求&#xff0c;尤其是在需要将高电压转换为低电压以供电给微电子设备时。AH8652是一款专为降压转换设计的集成电路&#xff0c;它能够将220V的交流输入电压转换为稳定的5V直流输出&#xff0c;非常适…