ArrayList的底层数据结构是什么？

ArrayList的底层数据结构是数组。

在之前的文章《数据结构之数组》中我们说过，在各类开发语言中都提供了对数组进行操作的容器类，java中针对数组的容器类就是ArrayList。

关于数组的相关介绍请查看《数据结构之数组》这篇文章，今天我们主要通过查询、插入、删除操作来聊下数组的容器类ArrayList是怎么来操作数组的。Jdk版本为1.8.0_172。

插入

ArrayList的插入方法有：

add(E element) 在数组末尾新增一个元素。

add(int index,E element) 在指定位置新增一个元素。

addAll(Collection<?extends E> c) 在数组末尾新增一个元素的集合。

addAll(int index, Collection<?extends E> c) 在指定位置新增一个元素的集合。

我们以add(int index,E element)为例，来看看ArrayList是怎么实现的，下面是ArrayList的源码：

其中1、rangeCheckForAdd方法是用来校验传入的数组下标是否有越界的，源码如下：

2、ensureCapacitylnternal方法作用是当数组长度不够时，对数组进行扩容。扩容算法为：newCapacity=oldCapacity+(oldCapacity>>1))（扩容为原来的1.5倍）。数组最大长度为：Integer.MAX VALUE=0x7fffffff。

3、扩容完成后System.arraycopy方法则是将指定位置后的数据整体往后挪动一位。

4、elementData[index]=element;是在数组的指定位置插入一位。

5、size++则是数组内存放的数据个数加1。

剩下的add、addAll方法处理逻辑和上述方法的处理逻辑类似。

查询

ArrayList的查询方法为public E get（int index），源码如下：

查询方法就很简单了，只有两行代码，第一行是判断传入的数组下标是否越界，源码如下：

注意，这里传入的数组下标是和数组内实际存在的数据个数进行对比的，不是与数组的长度进行对比的，因此即使数组的长度为10，如果数组内只存了5个数据，使用get（8）时也会报数组下标越界的错误。如下：

而如果直接使用数组，则不会出现此错误，如下：

删除

ArrayList的删除方法有：

remove(int i) 删除指定位置的元素

remove(Object o) 删除遇到的第一个指定元素

removeAll(Collection<?> c) 删除指定集合内的所有元素

removelf(Predicate<?superE> filter) 删除满足特定条件的所有元素。

删除方法的内核其实也是数组内元素的移动，需要注意的是：

1、remove(Object o)是删除遇到的第一个指定元素，如果集合内有重复元素，则只删除第一个。如下：

关键源码为：

2、removeAll(Collection<?>c）是删除指定集合内的所有元素，如果集合内有重复元素，也会把重复元素全部删除，如下：

关键源码：

今天我们聊到了ArrayList的底层数据结构是数组。同时了解了ArrayList作为数组的容器，是如何操作数组的。经过上面的源码分析，大家会发现，ArrayList可以自行的去动态扩容，但是动态扩容时需要将原数组内容完全的复制到新的数组中，这是非常消耗性能的操作。所以，如果事先能确定需要存储的数据大小，最好在创建ArrayList的时候事先指定数组的大小。