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 条评论
登录 后参与评论

相关文章

来自专栏技术之路

实例化和具体化详解

primer Plus在解释具体化和实例化看的有点乱,分解出来备忘 在代码中包含函数模板本身并不会生成函数定义,它只是用于生成函数定义的方案 编译器使用模板为我...

1905
来自专栏老九学堂

必看 | 新人必看的Java基础知识点大梳理

各位正在认真苦学Java的准大神,在这烈日炎炎的夏季里,老九君准备给大家带来一个超级大的“冰镇西瓜,”给大家清凉一下,压压惊。但这个大西瓜可不是一般的大西瓜,是...

3548
来自专栏我是业余自学C/C++的

vector

1574
来自专栏C/C++基础

Google C++编程风格指南(三)之作用域的相关规范

C++在C的基础上引入了名字空间机制,使C中作用域的级别从原有的文件域(全局作用域)和局部域(函数作用域和代码块作用域)中间增加了名字空间域和类域。

823
来自专栏前端知识分享

第205天:面向对象知识点总结

JSON全称为JavaScript对象简单表示法(JavaScript Object Notation)

833
来自专栏微信公众号:Java团长

探究Java虚拟机栈

Java 虚拟机的内存模型分为两部分:一部分是线程共享的,包括 Java 堆和方法区;另一部分是线程私有的,包括虚拟机栈和本地方法栈,以及程序计数器这一小部分内...

952
来自专栏软件开发 -- 分享 互助 成长

C++中变量自动初始化的问题

C++中有一些变量在如果没有赋初值会被编译器自动赋值为0,但有的变量又不会这样,而得到一个随机数,下面具体讨论一下: 首先看一下C++中的几个存储区: 1、栈区...

1737
来自专栏鬼谷君

迭代器和生成器

1274
来自专栏Python爬虫实战

Python指南:Python的8个关键要素

大家好,从本文开始将逐渐更新Python教程指南系列,为什么叫指南呢?因为本系列是参考《Python3程序设计指南》,也是作者的学习笔记,希望与读者共同学习。

1402
来自专栏博岩Java大讲堂

Java虚拟机--对象的建立你的对象如何创建?

3066

扫码关注云+社区