【某大厂一面】数组和链表区别
在 Java 中,数组(Array
)和链表(LinkedList
)是两种常见的数据结构,它们在存储和操作方式上有显著的区别。了解它们的差异有助于选择适合特定应用场景的结构。下面是数组和链表之间的详细比较。
1. 存储结构
数组(Array)
- 连续内存空间:数组在内存中是一个连续的块,所有元素依次存储在一起。
- 固定大小:数组的大小在创建时就确定,不能动态调整。创建后不能改变大小(除非重新创建数组并拷贝内容)。
- 索引访问:数组支持通过索引直接访问任意位置的元素,时间复杂度为 O(1)。
链表(LinkedList)
- 非连续内存:链表中的元素(节点)并不保存在连续的内存位置。每个节点包含一个数据部分和一个指向下一个节点的引用(对于双向链表,还有指向前一个节点的引用)。
- 动态大小:链表的大小可以动态变化,不需要预先指定大小。可以在运行时不断添加或删除节点。
- 逐步访问:访问链表中的元素需要从头节点开始,逐一遍历节点,直到找到目标元素。时间复杂度是 O(n),其中 n 是链表的长度。
2. 内存使用
数组
- 内存分配:数组一次性分配连续的内存空间,内存效率较高。但如果数组大小太大,可能会浪费空间;如果大小过小,则可能需要重新分配新的更大数组。
- 固定大小:一旦数组的大小固定后,就无法扩展。如果数组大小不够,需要创建一个新的数组并将数据复制到新数组中。
链表
- 内存分配:链表的每个节点都是单独分配内存的,因此内存使用更加灵活。每次新增元素时,只需要分配一个节点的内存。
- 节点开销:每个节点除了存储数据外,还需要存储指向其他节点的引用,因此链表的内存开销比数组大,尤其是双向链表需要存储两个引用(前向引用和后向引用)。
3. 时间复杂度
数组
- 访问元素:由于数组支持通过索引直接访问元素,访问时间是常数时间,O(1)。
- 插入和删除:
- 在数组的 末尾 插入或删除元素时间复杂度是 O(1)。
- 在数组的 中间 插入或删除元素时,需要移动后续的元素,时间复杂度是 O(n)。
链表
- 访问元素:需要从头节点开始遍历,逐个节点查找目标元素,时间复杂度是 O(n)。
- 插入和删除:
- 在链表的 头部 插入或删除元素时间复杂度是 O(1)。
- 在链表的 中间 或 末尾 插入或删除元素也可以在 O(1) 时间完成,但需要先找到目标位置,找到位置的时间复杂度是 O(n)。
4. 使用场景
数组
-
优点:
- 直接的索引访问非常高效,适用于查找操作频繁的场景。
- 存储连续的元素,内存管理较简单。
- 适合元素个数已知且不经常变动的场景。
-
缺点:
- 大小固定,扩展困难(需要重新分配更大的数组)。
- 插入和删除操作较慢,特别是中间的插入和删除,需要大量元素移动。
- 随着元素增多,可能会浪费内存。
链表
-
优点:
- 动态大小,能方便地进行插入和删除操作,尤其是在头部或尾部插入删除。
- 不需要预先分配固定大小,内存使用更加灵活。
-
缺点:
- 访问速度较慢,需要逐一遍历节点,不能像数组那样通过索引直接访问。
- 每个节点需要额外存储指向下一个节点的引用,增加了内存开销。
5. 代码示例
数组示例
public class ArrayExample {public static void main(String[] args) {// 创建一个大小为 5 的数组int[] arr = new int[5];// 向数组中添加元素arr[0] = 10;arr[1] = 20;arr[2] = 30;arr[3] = 40;arr[4] = 50;// 通过索引访问元素System.out.println("Element at index 2: " + arr[2]);// 插入元素时需要重新分配数组(手动管理)}
}
链表示例(使用 LinkedList
类)
import java.util.LinkedList;public class LinkedListExample {public static void main(String[] args) {// 创建一个 LinkedListLinkedList<Integer> linkedList = new LinkedList<>();// 向链表中添加元素linkedList.add(10);linkedList.add(20);linkedList.add(30);// 访问链表中的元素System.out.println("First element: " + linkedList.get(0));// 插入元素linkedList.addFirst(5); // 在链表的头部插入元素linkedList.addLast(40); // 在链表的尾部插入元素System.out.println("Linked list: " + linkedList);// 删除元素linkedList.removeFirst(); // 删除头部元素linkedList.removeLast(); // 删除尾部元素System.out.println("After deletion: " + linkedList);}
}
6. ArrayList 和 LinkedList 的比较(Java 视角)
在 Java 中,ArrayList
和 LinkedList
都实现了 List
接口,但它们在底层实现上有所不同。ArrayList
使用数组作为存储结构,而 LinkedList
使用双向链表。
-
ArrayList:
- 支持通过索引快速访问元素。
- 插入和删除元素的时间复杂度通常为 O(n),特别是在中间位置。
-
LinkedList:
- 支持快速的插入和删除,特别是在头部或尾部。
- 访问元素时需要遍历链表,访问时间较慢。
7. 总结
特性 | 数组(Array) | 链表(LinkedList) |
---|---|---|
存储结构 | 连续的内存空间 | 每个节点包含数据和指向下一个节点的引用 |
大小 | 固定大小 | 动态大小 |
访问效率 | 快速 O(1) | 需要遍历,O(n) |
插入/删除效率 | 中间插入/删除 O(n),尾部 O(1) | 插入/删除 O(1)(头尾),查找 O(n) |
内存管理 | 静态分配,可能浪费空间 | 节点动态分配,内存使用灵活 |
使用场景 | 查找操作频繁,大小已知且不变的场景 | 插入/删除频繁,元素动态变化的场景 |
选择使用数组还是链表,取决于具体应用场景。如果需要频繁的随机访问,数组是更好的选择。如果需要频繁的插入和删除操作,链表会更高效。
小伙伴们在开发过程中有使用心得可以再评论区一块讨论
相关文章:
【某大厂一面】数组和链表区别
在 Java 中,数组(Array)和链表(LinkedList)是两种常见的数据结构,它们在存储和操作方式上有显著的区别。了解它们的差异有助于选择适合特定应用场景的结构。下面是数组和链表之间的详细比较。 1. 存储结构…...
MySQL常用数据类型和表的操作
文章目录 (一)常用数据类型1.数值类2.字符串类型3.二进制类型4.日期类型 (二)表的操作1查看指定库中所有表2.创建表3.查看表结构和查看表的创建语句4.修改表5.删除表 (三)总代码 (一)常用数据类型 1.数值类 BIT([M]) 大小:bit M表示每个数的位数,取值范围为1~64,若…...
深入 Rollup:从入门到精通(三)Rollup CLI命令行实战
准备阶段:初始化项目 初始化项目,这里使用的是pnpm,也可以使用yarn或者npm # npm npm init -y # yarn yarn init -y # pnpm pnpm init安装rollup # npm npm install rollup -D # yarn yarn add rollup -D # pnpm pnpm install rollup -D在…...
3.日常英语笔记
screening discrepancies 筛选差异 The team found some screening discrepancies in the data. 团队在数据筛选中发现了些差异。 Don’t tug at it ,or it will fall over and crush you. tug 拉,拽,拖 He tugged the door open with all his might…...
sqlite3 学习笔记
文章目录 前言SQL的概念与表格相关的操作i.创建表格(增)ii 删除表格(删)iii 更改表格(改)iv 查询表格(查) 与记录相关的操作i 插入记录ii 删除记录iii 查询记录iv 修改记录 Linux中使…...
C++ | 红黑树
前言 本篇博客讲解c中数据结构红黑树,看这篇博客之前请先去看: C | AVL树_c avl树能有重复节点吗-CSDN博客 💓 个人主页:普通young man-CSDN博客 ⏩ 文章专栏:C_普通young man的博客-CSDN博客 ⏩ 本人giee: 普通小青…...
使用Ollama 在Ubuntu运行deepseek大模型:以DeepSeek-coder为例
DeepSeek大模型这几天冲上热搜啦! 咱们来亲身感受下DeepSeek模型的魅力吧! 整个操作流程非常简单方便,只需要2步,先安装Ollama,然后执行大模型即可。 安装Ollama 在Ubuntu下安装Ollama非常简单,直接sna…...
詳細講一下RN(React Native)中的列表組件FlatList和SectionList
1. FlatList 基礎使用 import React from react; import { View, Text, FlatList, StyleSheet } from react-native;export const SimpleListDemo: React.FC () > {// 1. 準備數據const data [{ id: 1, title: 項目 1 },{ id: 2, title: 項目 2 },{ id: 3, title: 項目 3…...
《深度揭秘:TPU张量计算架构如何重塑深度学习运算》
在深度学习领域,计算性能始终是推动技术发展的关键因素。从传统CPU到GPU,再到如今大放异彩的TPU(张量处理单元),每一次硬件架构的革新都为深度学习带来了质的飞跃。今天,就让我们深入探讨TPU的张量计算架构…...
QT使用eigen
QT使用eigen 1. 下载eigen https://eigen.tuxfamily.org/index.php?titleMain_Page#Download 下载后解压 2. QT引入eigen eigen源码好像只有头文件,因此只需要引入头文件就好了 qt新建项目后。修改pro文件. INCLUDEPATH E:\222078\qt\eigen-3.4.0\eigen-3.…...
工业“MCU+AI”
随着工业4.0的推进,传统工业设备正向智能化和自动化方向转型。这要求设备具备更高的算力、更强的实时处理能力以及支持AI算法的能力,以应对工业机器人、电机控制、预测性维护等复杂应用场景。 近年来越来越多的芯片厂商纷纷推出工业“MCUAI”产品&#…...
【Linux】Linux C判断两个IPv6地址是否有包含关系
功能说明 要判断两个 IPv6 地址是否具有包含关系,包括前缀的比较,可以通过以下步骤实现: 解析 IPv6 地址和前缀:将两个 IPv6 地址和它们的前缀长度解析为二进制形式。生成掩码:根据前缀长度生成掩码。按位比较&#…...
多模态论文笔记——TECO
大家好,这里是好评笔记,公主号:Goodnote,专栏文章私信限时Free。本文详细解读多模态论文TECO(Temporally Consistent Transformer),即时间一致变换器,是一种用于视频生成的创新模型&…...
AI学习(vscode+deepseek+cline)
1、网页生成不成功时,直接根据提示让模型替你解决问题 2、http://localhost:3000 拒绝链接时,cmd输入命令InetMgr,网站右键新建-配置你的网页代码物理地址,这里我还输入本机登录名及密码了,并把端口地址由默认80修改为…...
物业软件推动物业行业数字化转型 实现高效管理和优质客户体验
内容概要 在当今高速发展的数字化时代,物业软件的出现不仅使物业管理变得更加高效,也为行业转型提供了强大的支持。通过整合多种功能,物业软件显著提升了管理效率和客户体验。例如,在线收费和停车管理功能,让业主享受…...
WGCLOUD使用手册 - 登录验证码如何设置
登录页面默认是不用输入验证码的,但是我们也可以根据自己的实际场景,配置登录页面显示验证码,要求用户输入 提示:您需要需要升级到v3.5.3或以上版本,才可以支持此功能 我们在server配置文件里找到配置项vercodeCheck&…...
C# 9.0记录类型:解锁开发效率的魔法密码
一、引言:记录类型的神奇登场 在 C# 的编程世界中,数据结构就像是构建软件大厦的基石,其重要性不言而喻。然而,传统的数据结构定义方式,尤其是在处理简单的数据承载对象时,常常显得繁琐复杂。例如…...
Python 函数魔法书:基础、范例、避坑、测验与项目实战
Python 函数魔法书:基础、范例、避坑、测验与项目实战 内容简介 本系列文章是为 Python3 学习者精心设计的一套全面、实用的学习指南,旨在帮助读者从基础入门到项目实战,全面提升编程能力。文章结构由 5 个版块组成,内容层层递进…...
Unbutu虚拟机+eclipse+CDT编译调试环境搭建
问题1: 安装CDT,直接Help->eclipse Market space-> 搜cdt , install,等待重启即可. 问题2:C变量不识别vector ’could not be resolved 这是库的头文件没加好,右键Properties->C Build->Enviroment,增加…...
项目部署(springboot项目)
1、安装Nginx,并开启 2、前端项目打包:npm run build:prod--->dist 3、后端项目打包:install--->xxx.jar 4、开放需要的端口号:比如我的后端项目端口号为8282,则需要防火墙和服务器同时开发8282端口 5、将di…...
Spring MVC拦截器
文章目录 1. 拦截器(interceptor)的作用2. 拦截器和过滤器区别3. 拦截器是快速入门 1. 拦截器(interceptor)的作用 Spring MVC 的拦截器类似于 Servlet 开发中的过滤器 Filter,用于对处理器进行预处理和后处理。 将拦截器按一定的顺序联结成一条链,这条…...
Nginx 路由匹配(Nginx Route Matching)
从小白到高手:深入Nginx 路由匹配 在现代互联网应用中,Nginx 作为一款高性能的 Web 服务器,因其灵活性和高效性而广泛应用于各类网站和服务。Nginx 的路由匹配规则是其核心功能之一,负责决定如何处理传入的请求。通过这些规则&am…...
基于RIP的MGRE实验
实验拓扑 实验要求 按照图示配置IP地址配置静态路由协议,搞通公网配置MGRE VPNNHRP的配置配置RIP路由协议来传递两端私网路由测试全网通 实验配置 1、配置IP地址 [R1]int g0/0/0 [R1-GigabitEthernet0/0/0]ip add 15.0.0.1 24 [R1]int LoopBack 0 [R1-LoopBack0]i…...
Spring Boot 中的事件发布与监听:深入理解 ApplicationEventPublisher(附Demo)
目录 前言1. 基本知识2. Demo3. 实战代码 前言 🤟 找工作,来万码优才:👉 #小程序://万码优才/r6rqmzDaXpYkJZF 基本的Java知识推荐阅读: java框架 零基础从入门到精通的学习路线 附开源项目面经等(超全&am…...
【Java基础-41.5】深入解析Java异常链:构建清晰的错误追踪体系
在Java编程中,异常处理是保证程序健壮性和可维护性的重要部分。然而,在实际开发中,异常往往不是孤立发生的,而是由一系列相关的异常引发的。为了更好地理解和处理这种复杂的异常场景,Java引入了 异常链(Exc…...
STM32使用VScode开发
文章目录 Makefile形式创建项目新建stm项目下载stm32cubemx新建项目IED makefile保存到本地arm gcc是编译的工具链G++配置编译Cmake +vscode +MSYS2方式bilibiliMSYS2 统一环境配置mingw32-make -> makewindows环境变量Cmake CmakeListnijia 编译输出elfCMAKE_GENERATOR查询…...
特权模式docker逃逸
目录 1.环境 2.上线哥斯拉 3.特权模式逃逸 1.判断是否为docker环境 2.判断是否为特权模式 3.挂载宿主机磁盘到docker 4.计划任务反弹shell 1.环境 ubuntu部署一个存在CVE-2017-12615的docker: (ip:192.168.117.147) kali(ip:192.168.117.128) 哥斯拉 2.上线哥斯拉…...
装出字符串中国第一个匹配项的下标
hello 大家好!今天开写一个新章节,每一天一道算法题。让我们一起来学习算法思维吧! function strStr(haystack, needle) {return haystack.indexOf(needle); }// 测试示例 const haystack "sadbutsad"; const needle "sad&q…...
从腾讯云数据仓库TCHouse安全地转移数据到AWS Redshift
实现从AWS Direct Connect连接到腾讯云数据仓库TCHouse-P、TCHouse-C或TCHouse-D,然后使用AWS Glue读取数据并在AWS Redshift中创建对应表并复制数据,需要按照以下步骤进行操作: 网络连接设置 AWS Direct Connect配置: 在AWS管理…...
DataComp:探索下一代多模态数据集
目录 一、TL;DR 二、方法 2.1 为什么要单独研究数据质量? 2.2 数据质量的研究范式 三、其他的工作(related work) 3.1 传统的做法 3.2 数据剪枝和去重(paper直接翻译) 四、DataComp的benchmark 4.1 竞赛条件限…...
【linux】Linux 常见目录特性、权限和功能
目录特性默认权限主要功能/用途/根目录,所有目录的起点755文件系统的顶层目录,包含所有其他子目录和文件/bin基础二进制命令目录(系统启动和修复必需的命令)755存放所有用户可用的基本命令(如 ls, cp, bash 等…...
基于SpringBoot电脑组装系统平台系统功能实现六
一、前言介绍: 1.1 项目摘要 随着科技的进步,计算机硬件技术日新月异,包括处理器(CPU)、主板、内存、显卡等关键部件的性能不断提升,为电脑组装提供了更多的选择和可能性。不同的硬件组合可以构建出不同类…...
Direct2D 极速教程(1) —— 画图形
极速导航 Direct2D 简介创建新项目:001-DrawGraphics弄一个白窗口在窗口上画图 Direct2D 简介 大家在学 WINAPI 的时候的时候有没有想过,怎么在一副窗口上画图呢?大家知道 Windows 系统是 GUI 图形用户界面 系统,以 Graphics 图形…...
DF 开发1
https://www.bilibili.com/video/BV1RFChYxEhJ/ 多个 workspace 图片上传 S3 上传大量文档 https://www.bilibili.com/video/BV1ySsEeUE6i 解决方案 返回 metadata https://www.bilibili.com/video/BV1t3e5eaENo 给出内容引用出处 模型负载均衡 可以以 ollama 在不同端口起服…...
[Computer Vision]实验二:图像特征点提取
目录 一、实验内容 二、实验过程及结果 2.1 Harris角点检测 2.2 SIFT算法 三、实验小结 一、实验内容 采用Harris与SIFT分别提取特征点及对应的描述子,对比两者的区别(特征点数量、分布、描述子维度、图像变化对二者的影响等)利用特征匹…...
在做题中学习(82):最小覆盖子串
解法:同向双指针——>滑动窗口 思路:题目要求找到s里包含t所有字符的最小子串,这就需要记录在s中每次查找并扩大范围时所包含进去的字符种类是否和t的相同,并且:题目提示t中会有重复字符,因此不能简单认…...
< OS 有关> BaiduPCS-Go 程序的 菜单脚本 Script: BaiduPCS-Go.Menu.sh (bdgo.sh)
目标: 使用 日本阿里云的 VPM 传输文件。 暂时方案: 使用 主机JPN 下载 https://huggingface.co/ 上模型从 JPN 放到 度狗上在家里从狗度下载 为了减少编程,尽量使用现在软件 ,就找到 GitHub - qjfoidnh/BaiduPCS-Go: iikira…...
redis缓存和springboot缓存包冲突怎么办
如果Redis缓存与Spring Boot缓存包发生冲突,可以采取以下几种解决方案: 排除Spring Boot缓存包:在pom.xml文件中排除Spring Boot的缓存依赖,以避免与Redis缓存冲突。例如: <dependency><groupId>org.spr…...
云计算技术深度解析与代码使用案例
云计算技术深度解析与代码使用案例 引言 随着信息技术的飞速发展,云计算作为一种革命性的技术,正在逐步改变我们的生活和工作方式。云计算不仅提供了前所未有的计算能力和存储资源,还以其灵活性和可扩展性,成为现代企业数字化转型的重要支撑。本文将深入探讨云计算的核心…...
【教学类-89-01】20250127新年篇01—— 蛇年红包(WORD模版)
祈愿在2025蛇年里, 伟大的祖国风调雨顺、国泰民安、每个人齐心协力,共同经历这百年未有之大变局时代(国际政治、AI技术……) 祝福亲友同事孩子们平安健康(安全、安全、安全)、巳巳如意! 背景需…...
React Router v6配置路由守卫
首先准备好以下页面 登录页:用户可以在此页面登录。 受保护页:只有登录的用户可以访问,否则会重定向到登录页。 公共页面:不需要鉴权,任何人都可以访问。 1. 安装依赖 首先,我们需要安装 react-router-do…...
双层Git管理项目,github托管显示正常
双层Git管理项目,github托管显示正常 背景 在写React项目时,使用Next.js,该项目默认由git托管。但是我有在项目代码外层记笔记的习惯,我就在外层使用了git托管。 目录如下 code 层内也有.git 文件,对其托管。 我没太在意&…...
Linux--权限
Linux系统的权限管理是保障系统安全的重要机制,以下详细讲解权限相关概念及操作指令: 一、基础权限机制 1. 权限的三元组,读(r)、写(w)、执行(x) 每个文件或目录有三组…...
第25章 项目启航前的密谈
在那弥漫着严谨与专注气息的会议室里,苏睿所长端坐在会议桌前,宛如一座沉稳的山峰,散发着一种让人安心的力量。他的神情认真而庄重,目光中透着几分感慨,仿佛在时光的长河中回溯着项目的点点滴滴。微微侧身看向东方艾艾…...
ModernBERT 为我们带来了哪些启示?
当谷歌在 2018 年推出 BERT 模型时,恐怕没有料到这个 3.4 亿参数的模型会成为自然语言处理领域的奠基之作。 六年后的今天,面对动辄千亿参数的大语言模型浪潮,Answer.AI、LightOn与 HuggingFace 联手打造的 ModernBERT 却选择了一条返璞归真的…...
【MySQL】--- 复合查询 内外连接
Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk (๑•́ ₃ •̀๑) 文章专栏: MySQL 🏠 基本查询回顾 假设有以下表结构: 查询工资高于500或岗位为MANAGER的雇员,同时还要满足他们的姓名首字母为…...
Android Studio打包APK
1.导出APK安装包 如果是首次打包,Create new 单击蓝色对话框右边文件夹📂图标 ,选择密钥保存路径,然后在下方File name对话框中填写您想要名称,再点击OK回到密钥创建对话框。 在此对话框中填写密码(Passwo…...
RKNN_C++版本-YOLOV5
1.背景 为了实现低延时,所以开始看看C版本的rknn的使用,确实有不足的地方,请指正(代码借鉴了rk官方的仓库文件)。 2.基本的操作流程 1.读取模型初始化 // 设置基本信息 // 在postprocess.h文件中定义,详见…...
Git常用命令集合
见过不少人、经过不少事、也吃过不少苦,感悟世事无常、人心多变,靠着回忆将往事串珠成链,聊聊感情、谈谈发展,我慢慢写、你一点一点看...... git init <directory》初始化本地仓库 git add <file> 添加文件到暂存区 git …...
【deepseek】deepseek-r1本地部署-第一步:下载LM Studio
要下载LM Studio,可以按照以下步骤进行: 一、访问LM Studio官方网站 打开必应(注意!百度无法打开官网),输入LM Studio的官方网址:LM Studio - Discover, download, and run local LLMs。进入L…...