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

相关文章

来自专栏mwangblog

python函数

17620
来自专栏用户2442861的专栏

使用 RandomStringUtils 类来生成随机码/随机数 java生成指定范围的随机数

    /*         生成微信账号 8位的字符串 含有数字和字母      */     public String getRandomWei...

46620
来自专栏前端知识分享

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

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

10030
来自专栏zaking's

用js来实现那些数据结构02(数组篇02-数组方法)

    上一篇文章简单的介绍了一下js的类型,以及数组的增删方法。这一篇文章,我们一起来看看数组还有哪些用法,以及在实际工作中我们可以用这些方法来做些什么。由于...

426110
来自专栏老司机的技术博客

宝宝都能学会的python编程教程11:定义函数

定义函数 在Python中,定义一个函数要使用def语句,依次写出函数名、括号、括号中的参数和冒号:,然后,在缩进块中编写函数体,函数的返回值用return语句...

30850
来自专栏Python爬虫实战

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

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

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

vector

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

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

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

9730
来自专栏个人随笔

析构函数(C#)

 析构函数又称终结器,用于析构类的实例。 定义   析构函数(destructor) 与构造函数相反,当对象结束其生命周期时(例如对象所在的函数已调用完毕),系...

36070
来自专栏老司机的技术博客

人人都能学会的python编程教程11:定义函数

在Python中,定义一个函数要使用def语句,依次写出函数名、括号、括号中的参数和冒号:,然后,在缩进块中编写函数体,函数的返回值用return语句返回。

52280

扫码关注云+社区

领取腾讯云代金券