数据结构:数组和链表的区别(数组和链表的优缺点 & 数组和链表的适用场景)
大家好,又见面了,我是你们的朋友全栈君。
数组和链表是两种基本的数据结构,他们在内存存储上的表现不一样,所以也有各自的特点
数组
一、数组的特点
1.在内存中,数组是一块连续的区域 2.数组需要预留空间 在使用前需要提前申请所占内存的大小,这样不知道需要多大的空间,就预先申请可能会浪费内存空间,即数组空间利用率低 ps:数组的空间在编译阶段就需要进行确定,所以需要提前给出数组空间的大小(在运行阶段是不允许改变的) 3.在数组起始位置处,插入数据和删除数据效率低。 插入数据时,待插入位置的的元素和它后面的所有元素都需要向后搬移 删除数据时,待删除位置后面的所有元素都需要向前搬移 4.随机访问效率很高,时间复杂度可以达到O(1) 因为数组的内存是连续的,想要访问那个元素,直接从数组的首地址处向后偏移就可以访问到了 5.数组开辟的空间,在不够使用的时候需要扩容,扩容的话,就会涉及到需要把旧数组中的所有元素向新数组中搬移 6.数组的空间是从栈分配的
二、数组的优点
随机访问性强,查找速度快,时间复杂度为O(1)
三、数组的缺点
1.头插和头删的效率低,时间复杂度为O(N) 2.空间利用率不高 3.内存空间要求高,必须有足够的连续的内存空间 4.数组空间的大小固定,不能动态拓展
链表
一、链表的特点
1.在内存中,元素的空间可以在任意地方,空间是分散的,不需要连续 2.链表中的元素都会两个属性,一个是元素的值,另一个是指针,此指针标记了下一个元素的地址 每一个数据都会保存下一个数据的内存的地址,通过此地址可以找到下一个数据 3.查找数据时效率低,时间复杂度为O(N) 因为链表的空间是分散的,所以不具有随机访问性,如要需要访问某个位置的数据,需要从第一个数据开始找起,依次往后遍历,直到找到待查询的位置,故可能在查找某个元素时,时间复杂度达到O(N) 4.空间不需要提前指定大小,是动态申请的,根据需求动态的申请和删除内存空间,扩展方便,故空间的利用率较高 5.任意位置插入元素和删除元素效率较高,时间复杂度为O(1) 6.链表的空间是从堆中分配的
二、链表的优点
1.任意位置插入元素和删除元素的速度快,时间复杂度为O(1) 2.内存利用率高,不会浪费内存 3.链表的空间大小不固定,可以动态拓展
三、链表的缺点
随机访问效率低,时间复杂度为0(N)
综上:
对于想要快速访问数据,不经常有插入和删除元素的时候,选择数组
对于需要经常的插入和删除元素,而对访问元素时的效率没有很高要求的话,选择链表
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/147966.html原文链接:https://javaforall.cn
相关文章
- 微服务(十三)——Nacos入门&Cloud Alibaba
- Log4j2 Demos(基础/时间&大小回滚/定期删除/日志脱敏)「建议收藏」
- CVPR2022Mask Modeling在视频任务中也有效?复旦&微软提出Video版本BEVT,在多个视频数据集上SOTA!
- nvPress内容管理系统的介绍&搭建
- 00SEC-D&D数据泄露报警日报【第9期】
- 00SEC-D&D数据泄露报警日报【第10期】
- 零零信安-D&D数据泄露报警日报【第18期】
- 08Prism WPF 入门实战 - Cmd&EeventAggregator
- H3C路由交换 Smart Link & Monitor Link
- ognl表达式编写-Struts2框架(二):封装方法&其他介绍&注入方式详解
- 性能(第2集)第14讲LoadRunner负载均衡&多场景运行时间设置
- 数据宝典:数据架构 & 数据模型 & 数据管理(PPT)
- netbios amp DDOS攻击.c
- AMP与Oracle结合提升数据库性能($amp oracle)
- Js&Vbs正则表达式替换重复的字符
- 使用C#开源文件实时监控工具Tail&TailUI介绍