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学习

Java每日一练(2017/7/31)

本期题目: (单选题)1、类Car里面有个方法run(),如果直接用Car.run(),则方法run前面必须用的关键词是? ( ) A class B fi...

2568
来自专栏用户画像

String s=new String("abc")创建了几个对象?

String str=new String("abc");   紧接着这段代码之后的往往是这个问题,那就是这行代码究竟创建了几个String对象呢?

601
来自专栏从零开始学 Web 前端

02 - JavaSE之基础及面向对象(补充)

933
来自专栏尾尾部落

普林斯顿大学算法公开课笔记——插入排序

现有一组数组 arr = [5, 6, 3, 1, 8, 7, 2, 4],共有八个记录,排序过程如下:

811
来自专栏java一日一条

Java面试题:栈和队列的实现

(5)设计含最小函数min()的栈,要求min、push、pop、的时间复杂度都是O(1)

341
来自专栏有趣的Python

6-Java常用工具类-集合排序

http://www.runoob.com/java/java-generics.html

603
来自专栏Java学习网

Java变量类型转换规则与注意事项

Java变量类型对于每个从事Java开发工作的人员来说再熟悉不过了,正如你所知,Java的数据类型分为三大类:布尔型、字符型和数值型,而其中数值型又分为整型和浮...

2076
来自专栏青枫的专栏

java基础学习_面向对象(上)02_day07总结

============================================================================= ==...

501
来自专栏Java Edge

Collections.sort()源码分析(基于JAVA8)java.lang.Object java.util.Collections简介Collections的sort方法代码:TimSort.

34212
来自专栏玄魂工作室

Python学习:类和实例

-----------------------------------------------------

883

扫码关注云+社区