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

相关文章

来自专栏一个会写诗的程序员的博客

Spring Reactor 项目核心库Reactor Core

Non-Blocking Reactive Streams Foundation for the JVM both implementing a Reactiv...

2102
来自专栏张善友的专栏

LINQ via C# 系列文章

LINQ via C# Recently I am giving a series of talk on LINQ. the name “LINQ via C...

2605
来自专栏一个爱瞎折腾的程序猿

sqlserver使用存储过程跟踪SQL

USE [master] GO /****** Object: StoredProcedure [dbo].[sp_perfworkload_trace_s...

1940
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

5226
来自专栏芋道源码1024

熔断器 Hystrix 源码解析 —— 断路器 HystrixCircuitBreaker

本文主要基于 Hystrix 1.5.X 版本 1. 概述 2. HystrixCircuitBreaker 3. HystrixCircuitBreaker....

5237
来自专栏魂祭心

原 canvas绘制clock

3924
来自专栏大内老A

The .NET of Tomorrow

Ed Charbeneau(http://developer.telerik.com/featured/the-net-of-tomorrow/) Exciti...

30510
来自专栏闻道于事

js登录滑动验证,不滑动无法登陆

js的判断这里是根据滑块的位置进行判断,应该是用一个flag判断 <%@ page language="java" contentType="text/html...

6498
来自专栏我和未来有约会

Silverlight第三方控件专题

这里我收集整理了目前网上silverlight第三方控件的专题,若果有所遗漏请告知我一下。 名称 简介 截图 telerik 商 RadC...

3945
来自专栏菩提树下的杨过

Flash/Flex学习笔记(23):运动学原理

先写一个公用的小球类Ball: package{ import flash.display.Sprite; //小球 类 public class B...

25110

扫码关注云+社区