数据结构(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/791819.html

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

相关文章

视频压缩电脑软件,视频压缩电脑怎么操作

在数字媒体时代,视频文件的大小往往让人头疼。如何在不损失画质的情况下压缩视频,成为了许多创作者和普通用户的需求。本文将为你详细介绍电脑压缩软件,让你轻松应对视频压缩任务。 1.下载并安装视频压缩软件。 2.打开软件,选择视…

[leetcode] shortest-subarray-with-sum-at-least-k 和至少为 K 的最短子数组

. - 力扣&#xff08;LeetCode&#xff09; class Solution { public:int shortestSubarray(vector<int>& nums, int k) {int n nums.size();vector<long> preSumArr(n 1);for (int i 0; i < n; i) {preSumArr[i 1] preSumArr[i] nums[i];}int res n…

机遇与挑战并存 券商国际化战略布局关键要素

引言 在全球金融市场不断开放和技术快速进步的背景下&#xff0c;越来越多中资背景的券商开始寻求国际化发展。富途和老虎证券作为先行者&#xff0c;展示了中国券商在出海过程中的巨大潜力和成功经验。鉴于中资在海外设立券商的成功&#xff0c;不少公司也有意愿在海外设立券…

爆款文案管理系统设计

设计一个爆款文案管理系统&#xff0c;目标是帮助营销团队高效地创建、管理并分析吸引人的文案&#xff0c;以提升产品或服务的市场吸引力和销售转化率。以下是一些关键功能和设计考量点&#xff1a; 1. 用户友好界面 简洁直观的界面&#xff1a;确保系统界面清晰&#xff0c…

抖音短视频矩阵管理系统搭建全攻略:功能详解与实战应用

在短视频时代&#xff0c;抖音已经成为众多企业、网红、个人创作者不可或缺的传播平台。然而&#xff0c;如何高效管理多个抖音账号&#xff0c;实现内容、数据、粉丝的全方位掌控&#xff0c;成为了摆在大家面前的一道难题。本文将为大家深入解析抖音短视频矩阵管理系统的搭建…

项目管理工具评测:2024年国内外最顶级的10款项目管理工具排行

国内外涌现出众多优秀的项目管理工具&#xff0c;它们各自在功能、易用性、集成能力等方面展现出独特优势。以下是国内外顶级的10款项目管理工具&#xff1a; 一、进度猫 推荐理由&#xff1a;进度猫以其直观的任务管理和进度跟踪功能&#xff0c;成为许多团队和项目的首选…

C++入门 模仿mysql控制台输出表格

一、 说明 控制台输出表格&#xff0c;自适应宽度 二、 源码 #include <iostream> #include <map> #include <string> #include <vector>using namespace std;void printTable(vector<vector<string>> *pTableData) {int row pTableDa…

Leetcode104.求二叉树的最大深度

题目描述 递归法 class Solution {public int maxDepth(TreeNode root) {if (root null) { //帮助下面的else语句判空return 0;} else {int leftHeight maxDepth(root.left);int rightHeight maxDepth(root.right);/*** 要注意的点* 1. 这个return是写在else语句里面的&am…

ABeam News | FY25 ABeam德硕大中华区入社式,飞往崭新航向!

FY25 ABeam大中华区入社式 7月1日&#xff0c;51名 ABeam大中华区新生在艾宾信息技术开发&#xff08;上海&#xff09;有限公司大连分公司&#xff08;以下简称TDC&#xff09;报到&#xff0c;我们为他们的到来准备了隆重的入社仪式&#xff0c;并举办了热情而又温馨的欢迎晚…

通过图像高频信息保留图像细节,能保留多少细节-Comfyui

&#x1f9e8;前情提要 如果还不了解comfyui中图像高频信息保留细节的内容&#xff0c;可以参考上一篇文章&#xff1a; 图像中高频信息、低频信息与ComfyUI中图像细节保留的简单研究-CSDN博客 这次主要是简单测试下保留图像细节&#xff0c;能保留到什么程度&#xff1b; …

JavaScript(7)——数组

JavaScript中数组的用法与Java差不多&#xff0c;但还是有一些区别 声明数组 语法: let 数组名 [数据1,数据2,数据...] let arr new Array(数据1,数据2,...数据n) 添加数据 数组.push()方法将一个或多个元素添加到数组末尾&#xff0c;并返回该数组新长度 <script>…

【AI大模型新型智算中心技术建设白皮书 2024】

文末有福利&#xff01; 一、新算效——重塑计算架构 1.1 下一代 AI 芯片设计思路 以 GPU 为 代 表 的 高 性 能 并 行 计 算 芯 片 架 构 和 以 针 对 AI 领 域 专 用 加 速&#xff08;DSA, Domain Specific Architecture&#xff0c;DSA&#xff09;为代表的芯片架构是目…

麦克风领夹式的哪个牌子最好,无线领夹麦克风十大品牌

在直播和自媒体行业迅速崛起的今天&#xff0c;无线麦克风因其便携性和实用性成为了视频制作和直播带货中不可或缺的工具。面对市场上从几十元到几千元不等的无线麦克风&#xff0c;作为一位资深直播运营专家&#xff0c;我深知选择合适的设备对于提升直播质量和观众体验的重要…

排序相关算法--1.插入排序+冒泡排序回顾

1.基本分类 2.插入排序 特点&#xff1a;有实践意义&#xff08;例如后期快排的优化&#xff09;&#xff0c;适应性强&#xff0c;一般不会到时间复杂度最坏的情况。 将第一个元素视为已经排好序的序列。取出下一个元素&#xff0c;在已经排好序的序列中从后往前比较&#xf…

3SRB5016-ASEMI逆变箱专用3SRB5016

编辑&#xff1a;ll 3SRB5016-ASEMI逆变箱专用3SRB5016 型号&#xff1a;3SRB5016 品牌&#xff1a;ASEMI 封装&#xff1a;SGBJ-5 批号&#xff1a;2024 现货&#xff1a;50000 最大重复峰值反向电压&#xff1a;1600V 最大正向平均整流电流(Vdss)&#xff1a;50A 功…

C 语言中如何实现字符串的拼接?

&#x1f345;关注博主&#x1f397;️ 带你畅游技术世界&#xff0c;不错过每一次成长机会&#xff01; &#x1f4d9;C 语言百万年薪修炼课程 【https://dwz.mosong.cc/cyyjc】通俗易懂&#xff0c;深入浅出&#xff0c;匠心打磨&#xff0c;死磕细节&#xff0c;6年迭代&…

GB28181设备如何添加

简介 此篇描述视频网关&#xff08;中间件&#xff09;接入大华、海康、ONVIF设备&#xff08;NVR、摄像头&#xff09;、GB28181设备步骤和流程。 阅读本文档之前建议先阅览视频网关&#xff08;中间件&#xff09;用户使用手册。 接入方式和说明 视频网关&#xff08;中间…

捷配笔记-如何设计PCB板布线满足生产标准?

PCB板布线是铺设连接各种设备与通电信号的路径的过程。PCB板布线是铺设连接各种设备与通电信号的路径的过程。 在PCB设计中&#xff0c;布线是完成产品设计的重要步骤。可以说&#xff0c;之前的准备工作已经为它做好了。在整个PCB设计中&#xff0c;布线设计过程具有最高的极限…

网关、DHCP协议、ip地址、子网掩码简单介绍

参考文章&#xff1a;https://baike.baidu.com/item/%E7%BD%91%E5%85%B3/98992?frge_ala https://baike.baidu.com/item/DHCP%E6%9C%8D%E5%8A%A1%E5%99%A8/9956953?fromModulelemma_inlink https://blog.csdn.net/weixin_58783105/article/details/135041342 https://blog.cs…

【C++深度探索】全面解析多态性机制(一)

hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#xff1a;大耳朵土土垚的博客 &#x1…