专栏首页开发之途Java集合框架源码解析之数组与链表

Java集合框架源码解析之数组与链表

本系列文章会陆续对 Java 集合框架(Java Collections Framework,JDK1.8)中的几个常用容器结合源码进行介绍,帮助读者建立起对 Java 集合框架清晰而深入的理解,也算是对自己所学内容的一个总结归纳

因为数组与链表是 Java 集合框架中很多地方都涉及到的知识点,此篇文章作为开头,就先对数组与链表这两种数据结构进行介绍

数组与链表是两种差别较大的数据结构,在内存空间上的存储方式也有很大区别

数组

假设现在有6个元素存放在数组中,则数组在内存中的存储结构就如下图所示

  1. 数组是一块连续的内存空间,包含的元素按照坐标索引依次排列,可以直接通过坐标定位到每一个数据的内存地址,例如可以直接通过坐标 3 获取到 element4,省去了链表中的遍历过程,因此随机读取数据的效率较高
  2. 相对应的,由于要求数组中的元素是连续的,在添加数据或移除数据时,有可能会导致大量数据在内存中的前后移动,因此数组在添加和移除数据时效率较低
  3. 数组在使用前需要先指定其空间大小,如果我们在使用前已知待存入的数据量,自然可以直接以此进行初始化而不会浪费内存空间,但实际数据量往往是未知的,通常会因为申请了较大的内存空间导致浪费或者是申请少了导致数据无法存放,而数组在声明空间大小后是无法再次修改的

在 ArrayList 与 HashMap 等容器类中,其底层实际用来存放数据的结构都是数组

链表

假设现在有4个元素依靠链表来存放,则链表在内存中的存储结构就如下所示

  1. 图中所展示的是一个双向链表,即每个结点除了要包含实际的数据外,还需要两个引用分别用于指向上一个结点(prev)和下一个结点(next),此外还需要有两个引用分别指向头结点(first)和尾结点(last),方便进行正向遍历和反向遍历
  2. 链表不要求有连续的内存空间,新添加的结点可以在内存中的任何位置,只要上一个结点保存有下一个结点的引用即可
  3. 由于链表的内存空间不是连续的,因为在随机访问数据时只能选择遍历整个链表,在最坏的情况下需要遍历整个链表。当然,可以根据实际情况来选择是正向遍历还是反向遍历,以此提高访问效率
  4. 在添加或移除元素时,只需要修改相邻结点对指定结点的引用即可,而不需像数组那样需要移动元素,因此链表在添加和移除元素时的效率较高
  5. 链表不需事先申请内存空间,根据实际使用情况可以进行动态申请

在 HashMap 中,其底层在存放数据时就使用到了链表

更详细的源码解析可以看这里:JavaLearn

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java集合框架源码解析之LinkedHashMap

    叶志陈
  • Android IPC机制(1)-序列化机制

    叶志陈
  • Flutter 实战 - 用贝塞尔曲线画一个带文本的波浪球 Widget

    flutter 中的自定义 Widget 算作是 flutter 体系中比较高阶的知识点之一了,相当于原生开发中的自定义 View,以我个人的感受来说,自定义 ...

    叶志陈
  • 大厂面试HashMap,很多人栽在了这儿

    Hashmap是Java中最常用的集合类型,使用非常广泛。不过,有些细节问题很多人没有关注过,这也使很多人在面试时栽了跟头!比如,阿里很多团队为了考察候选人的基...

    用户7927337
  • 【面试】我是如何面试别人List相关知识的,深度有点长文

    前几年易中天可谓非常的火,接受过很多采访。他的情况比较特殊,在武汉读高中时期,恰逢“知识青年上山下乡”活动,就到新疆去了。

    帅地
  • 我是如何面试别人List相关知识的

    ?先来点鸡汤 前几年易中天可谓非常的火,接受过很多采访。他的情况比较特殊,在武汉读高中时期,恰逢“知识青年上山下乡”活动,就到新疆去了。 在新疆生产建设兵团...

    Java团长
  • Java集合容器面试题(2020最新版)

    Java面试总结汇总,整理了包括Java基础知识,集合容器,并发编程,JVM,常用开源框架Spring,MyBatis,数据库,中间件等,包含了作为一个Java...

    Java架构师必看
  • 2019,UI设计师及程序员必备神器

    2019年将会是你全新起航的一年,相信你已经制定了很多规划,正在开启第一步的推动。

    奔跑的小鹿
  • 2019,UI设计师必备神器

    2019年将会是你全新起航的一年,相信你已经制定了很多规划,正在开启第一步的推动。

    极乐君
  • 银行业的大数据:银行如何从客户数据中获得更大的价值?

    ? 信息和数据将是每个行业的一个卓越的磨刀石。这是大数据时代,每一个专业的依赖于访问数据分析,海量数据管理和变更。大数据分析发现了更大的共振在银行和金融业的大...

    灯塔大数据

扫码关注云+社区

领取腾讯云代金券