ArrayList 可以完全替换数组吗？

手机游戏开发者 · 2024-9-3 06:07:24

前言

各人好，我是小彭。
在前面的文章里，我们学习了许多数据布局与算法头脑。在现实的业务开辟中，每每不需要我们手写数据布局，而是直接使用尺度库的数据布局 / 容器类。
在后续的文章里，我们将以 Java 语言为例，分析从 ArrayList 到 LinkedHashMap 等一系列尺度库容器类，末了再有一篇总结回首，请关注。
学习门路图：
1. 说一下 ArrayList 和 LinkedList 的区别？

1、数据布局： 在数据布局上，ArrayList 和 LinkedList 都是 “线性表”，都继续于 Java 的 List 接口。别的 LinkedList 还实现了 Java 的 Deque 接口，是基于链表的栈或队列，与之对应的是 ArrayDeque 基于数组的栈或队列；
2、线程安全： ArrayList 和 LinkedList 都不思量线程同步，不包管线程安全；
3、底层实现： 在底层实现上，ArrayList 是基于动态数组的，而 LinkedList 是基于双向链表的。究竟上，它们许多特性的区别都是由于底层实现差异引起的。好比说：
- 在遍历速率上： 数组是一块一连内存空间，基于局部性原理可以大概更好地掷中 CPU 缓存行，而链表是离散的内存空间对缓存行不友爱；
- 在访问速率上： 数组是一块一连内存空间，支持 O(1) 时间复杂度随机访问，而链表需要 O(n) 时间复杂度查找元素；
- 在添加和删除操作上： 如果是在数组的末了操作只需要 O(1) 时间复杂度，但在数组中心操作需要搬运元素，所以需要 O(n)时间复杂度，而链表的删除操作本身只是修改引用指向，只需要 O(1) 时间复杂度（如果思量查询被删除节点的时间，复杂度分析上依然是 O(n)，在工程分析上照旧比数组快）；
- 额外内存斲丧上： ArrayList 在数组的尾部增长了闲置位置，而 LinkedList 在节点上增长了前驱和后继指针。

2. ArrayList 源码分析

这一节，我们来分析 ArrayList 中告急流程的源码。
2.1 ArrayList 的属性

ArrayList 的属性很好明确，底层是一个 Object 数组，我要举手提问：

??♀️疑问 1： 为什么 elementData 字段不声明 private 关键字？
??♀️疑问 2： 为什么 elementData 字段声明 transient 关键字？
??♀️疑问 3： 为什么elementData 字段不声明为泛型范例 E？
??♀️疑问 4： 为什么 ArrayList 的最大容量是 Integer.MAX_VALUE，Long.MAX_VALUE 不行吗？
??♀️疑问 5： 为什么 ArrayList 的最大容量是 MAX_VALUE - 8，肯定会减 8 吗？

这些标题我们在分析源码的过程中回答。疑问这么多，ArrayList 刹时不香了。

ArrayList 可以完全替换数组吗？

所属分类: 问答交流

新帖推荐: 30日

推荐作品