数据结构 – 链表和数组的区别[通俗易懂]

数据结构 – 链表和数组的区别[通俗易懂]文章目录数据结构-链表和数组的区别1、在内存上2、时间复杂度3、链表的结构4、各自的优缺点5、为什么使用较常用的是单头链表数据结构-链表和数组的区别1、在内存上数组是连续内存,因为是静态分配,所以不可扩容链表是非连续内存,动态分配,也没有顺序,它通过链表中的next指针保存逻辑顺序2、时间复杂度查找时间复杂度1、数组使用下标定位,1次就可以找到,O(1)2、链表需要循环去找,最大需要N次,O(N)插入删除时间复杂度1、数组插入删除需要移动其它元素,复杂度

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

数据结构 – 链表和数组的区别


1、在内存上

数组是连续内存,因为是静态分配,所以不可扩容
链表是非连续内存,动态分配,也没有顺序,它通过链表中的 next 指针保存逻辑顺序

2、时间复杂度

查找时间复杂度
1、数组使用下标定位,1次就可以找到 ,O(1)
2、链表需要循环去找,最大需要N次,O(N)

插入删除时间复杂度
1、数组插入删除需要移动其它元素,复杂度 O(N)
2、链表插入删除不需要移动其它元素,复杂度 O(1)

3、链表的结构

常用的链表结构有两种
1、只带有 next 指针的单头链表
2、既带有 next 指针,又带有父指针的双头链表

4、各自的优缺点

数组优缺点
优点
1、查找速度快

缺点
1、数组插入删除效率低
2、内存连续,容易造成内存碎片
3、不能动态扩容

链表优缺点
优点
1、插入删除效率高

缺点
1、查找效率低

5、为什么使用较常用的是单头链表

为什么大多数情况下单头链表比双头链表用的更多,虽然双头链表更具有优势,因为双头链表需要比单头链表更大的内存空间
而一般情况下,我们会选择用时间换空间

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/219101.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Java 编码转换_java 判断文件编码

    Java 编码转换_java 判断文件编码中文各种编码间互相转换,非常有用哦,借鉴了公司的资料,转载本人不负任何责任,呵呵主要是用hcutf8.txt里面的内容根据转码替换,呵呵packageencoding;importjava.io.BufferedReader;importjava.io.InputStream;importjava.io.InputStreamReader;importjava.io.Unsupporte

  • C# 处理透明问题[通俗易懂]

    C# 处理透明问题[通俗易懂]privatevoidpictureBox1_Click(objectsender,EventArgse){ImageImageimage;Imageimage=System.Drawing.Image.FromFile(@”D:\black.png”);Bitmapbitmap=newBitmap(Imageimage);bitmap..

  • oracle import/export 命令[通俗易懂]

    oracle import/export 命令[通俗易懂]exp/imp实例   exphelp=y查看帮助exp1、expusr/pwd@sid file=c:\tb.dump tables=tb1  如果是导出多个表,tables=(tb1、tb2)2、expusr/pwd@sid file=c:\tb.dump –全部导出3、expusr/pwd@sid file=c:\tb.dump owne

  • 哪些软件是python编写出来的_用Python编程需要什么软件?

    哪些软件是python编写出来的_用Python编程需要什么软件?用Python编程需要什么软件?Python编程是一门适合新手入门的编程语言,现在有不少程序员业余时间学习Python编程语言,学习Python找到好工具会大大提高学习的效率。好用的Python编程软件能将工作效率多倍速提升。今天小编就介绍一些Python编程软件供大家参考:一、终端:UptermUpterm简单好用,它是一个全平台的终端,可以说是终端里的IDE,有着强大的自动补全功能。二、交互式…

  • Java优化_解决if嵌套过多

    Java优化_解决if嵌套过多文章目录 一、使用策略模式 二、其他方案 1.分解条件表达式 2.合并重复的条件判断 3.提前判断返回 4.引入断言工具类 5.善用 Optional 6.使用枚举 7.枚举多态 8.类多态 9

  • 运行时异常和非运行时异常(一般异常)的区别

    运行时异常和非运行时异常(一般异常)的区别一,异常的概念Java异常类层次结构图:Throwable:有两个重要的子类:Exception(异常)和Error(错误),二者都是Java异常处理的重要子类,各自都包含大量子类。Error(错误):是程序无法处理的错误,表示运行应用程序中较严重问题。大多数错误与代码编写者执行的操作无关,而表示代码运行时JVM(Java虚拟机)出现的问题。例如,Java虚拟机运行错误(V…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号