ArrayList与List的层级关系及ArrayList解析

墨蓝 2024-02-21 11:42 86阅读 0赞

### List与ArrayList的关系 ###

### List ###

*  List是一个接口，不能直接实例化。如果要使用必须去实例化List的实现类——ArrayList和LinkedList
 *  站在数据结构的角度看，List就是一个线性表。常见的线性表：顺序表、链表、栈、队列等

#### 线性表 ####

*  线性表是n个具有相同特性的数据元素的有限序列。
 *  它在逻辑上是线性结构，但是在物理结构上不一定是连续的
 *  线性表在物理存储时，通常以数组和链式结构的形式存储

### List与ArrayList的关系 ###

*  从“List是一个接口”的方面来看，ArrayList是List接口的一个实现类
 *  从“List是一个线性表”的方面来看，ArrayList是一个以数组形式存储的线性表（这种线性表也被称为顺序表）

## ArrayList ##

### 关于ArrayList的说明 ###

*  ArrayList是以泛型方式实现的，使用时必须要先实例化
 *  ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
 *  ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
 *  ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
 *  ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
 *  和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList

### 认识ArrayList ###

#### 构造方法 ####

> 认识一个类一般都要从类的构造方法开始

构造方法有三种：1、无参构造；2、利用其他collection构建ArrayList；3、指定顺序表初始容量

以无参构造为例：

![832118dc9e1446b2a8729d7ab1eaa6a6.png][]

#### ArrayList中的方法（对部分方法进行解析） ####

![32912b0717194eac9b60e3a95deda944.png][]

##### Add方法 #####

![080924caa54645e88e5a315e475781d8.png][]

“先检测是否有可供插入的空间，然后将目前数组末尾的下一位下标的值设定为参数”

那么它是怎样检验是否可以插入的？

###### Add()中的ensureCapacityInternal ######

![1c65f19a10b6486d85c6ad8d3d43d54d.png][]

> ensureCapacityInternal()方法是为了确保 拿到的的数组容量满足使用。

我们通过源码了解到，ensureCapacityInternal中又有两个方法：ensureExplicitCapacity、calculateCapacity

先来看calculateCapacity

###### calculateCapacity()方法 ######

![99c63db5096b4300b6bc7f6667bcb47f.png][]

如果ArrayList的底层数组elementData为DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA（通过查看源码中的成员属性可以得知这是一个空数组）时，返回10（通过查看源码得知：当向起始的空数组中插入元素时，会给这个空数组赋予10个容量）和minCapacity（参数）的最大值，否则返回minCapacity的值（minCapacity被视为数组容量）

> 这个方法为了得知 需要的数组容量。

###### ensureExplicitCapacity()方法 ######

![aa448013c9c441baa77096d0b6deb2a1.png][]

如果当前需要的数组容量 比目前的数组长度大的话，需要进行扩容

> 这个方法是为了获得 符合要求的数组容量

###### grow()扩容方法 ######

![802c58d9b7a24fc8ac14be6fd9bc80d1.png][] 定义原来的数组长度为旧容量，将旧容量扩容1.5倍后于所需容量minCapacity比较，如果新容量小于mC，就将mC设置为新容量；如果新容量大于数组最大长度(MAX\_ARRAY\_SIZE)（这是一个常量），就进行一次判断（使用hugeCapacity方法判断）：如果需求容量小于0，抛出异常；如果需求容量比数组最大长度还要大，就将新容量定义为Integer的最大值，否则就将新容量定义为数组最大长度

###### 注：MAX\_ARRAY\_SIZE与MAX\_VALUE ######

![9b63370ba84f43008a568c8ba690fa27.png][]

![b095055f029349e1808d8c29473293ce.png][]

为什么会有MAX\_ARRAY\_SIZE的定义呢？

因为数组有点特殊性，数组对象要额外存储 数组元素长度 在头部，少了这8个长度可能与此有关。 尝试分配大于 MAX\_ARRAY\_SIZE 长度的数组会导致 OOM （换句话说，超过了该虚拟机的[数组长度][Link 1]限制）。

如果MAX\_ARRAY\_SIZE的长度还不够用，就直接将Integer的最大值给新数组（数组长度是个Integer类型-是一个整数）。至于会不会因为OOM报错那就不管了

#### remove()方法 ####

当我们使用remove方法时，会将我们传入的参数识别为一个下标，而不是我们所想的“一个对象”（例如“ArrayList.remove（0）” 删除0下标/删除数字0——“arraylist.remove(new Interger(0))”）——这是因为有两个remove方法，可以传一个下标，也可以传一个对象

#### subList()方法 ####

![251c50a2e46d48f0ad6dd39674d4ba99.png][]

> 从数组fromIndex下标开始，取出toIndex个元素放入subList数组中

![0ca235d5a395491dbad3eb1f7d9f460e.png][]

如果改变sub（从list中）截取出来的数组中的数据，将会一起改变list中的数据

![3103a4c6bb124180b0108b8abcbbabe9.png][]

“sub”和“list”共用一个elementData数组

### 遍历ArrayList的三种方法 ###

![801594dfb40d4f738759892f4cf0e05b.png][]

[832118dc9e1446b2a8729d7ab1eaa6a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/1cb784f4025f4d0d8d616c77c600c227.png
[32912b0717194eac9b60e3a95deda944.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/6a73ea87920b449fb192ce7ef14abc0b.png
[080924caa54645e88e5a315e475781d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/beb995cc87f24422b7f2ff96ea6d47c4.png
[1c65f19a10b6486d85c6ad8d3d43d54d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/a0c1fe51e51642e494a0303a72ed7eed.png
[99c63db5096b4300b6bc7f6667bcb47f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/8acfdba557434487bc100744518bbc93.png
[aa448013c9c441baa77096d0b6deb2a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/015d81bbba2641789eff894d40e1361f.png
[802c58d9b7a24fc8ac14be6fd9bc80d1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/2023d57280a84b4fae4ff4bbf351f09f.png
[9b63370ba84f43008a568c8ba690fa27.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/0a1e59bbdaeb456fa234cd8e2d65cf4f.png
[b095055f029349e1808d8c29473293ce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/b2672895ff624f0f893abe43dc0861bf.png
[Link 1]: https://so.csdn.net/so/search?q=%E6%95%B0%E7%BB%84%E9%95%BF%E5%BA%A6&spm=1001.2101.3001.7020
[251c50a2e46d48f0ad6dd39674d4ba99.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/6502fbc38d6b45d39eadbda3a76507df.png
[0ca235d5a395491dbad3eb1f7d9f460e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/f0a67609c983406799e70db692a49cd6.png
[3103a4c6bb124180b0108b8abcbbabe9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/ef8a6944dc8e4ef68cb0a62825e4a43b.png
[801594dfb40d4f738759892f4cf0e05b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/a31fadc3c699455c8dca50a8ff8737f7.png