【集合】ArrayList

曾经终败给现在 2021-11-05 01:28 314阅读 0赞

主要对源码中几个常用的方法进行分析。ArrayList是基于数组实现的，当我们添加元素的时候，他可以替我们动态的为数组扩容。

# 1.源码 #

## 1.1属性 ##

/** * 默认初始容量。 */
        private static final int DEFAULT_CAPACITY = 10;
        /** * 当声明arrayList的时候，长度指定为0，就会使用这个数组 */
        private static final Object[] EMPTY_ELEMENTDATA = { };
        /** * 当new ArrayList();的时候就会把这个null元素的数组的引用给elementData， */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
        /** * 实际存储元素的数组 */
        transient Object[] elementData; // non-private to simplify nested class access
        /** * 这个是元素的个数 */
        private int size;

elementData使用transient来修饰，表示这个数组不参与序列化。

## 1.2 构造方法ArrayList() ##

当实例化一个对象的时候，刚开始会使用**DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA** 这个没有元素的数组。  
![在这里插入图片描述][20190808022048665.png]

## 1.3 构造方法ArrayList(int initialCapacity) ##

当initialCapacity大于0的时候，就会直接new 一个Object数组给elementData，可以看出来，ArrayList实际上是使用elementData来储存元素的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70]

## 1.4 添加元素方法add(E) ##

添加元素方法中主要有一个检查是否需要扩容的方法**ensureCapacityInternal(int)**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 3]  
add()方法：当容量不够用的时候就会进行自动扩容，扩容为原来的1.5倍。

## 1.5 删除元素方法remove(int) ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 4]  
可以看出删除方法的返回值是元素本身，而且**并没有缩小容量**

## 1.6 获取元素get(int) ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 6]  
首先检查坐标是否合法，然后按照下标返回元素

# 2.总结 #

简单的看一下源码，其中有一个变量modCount，这个是AbstractList中的元素，主要的作用就是有用来表示对list操作了多少次。这个可能是为了list做线程同步做准备。

## 2.1 ArrayList是怎么扩容的？ ##

通过看源码，可以知道，添加元素的时候首先检查是否需要扩容，当容量不够用的时候，就使用grow(int minCapacity)方法来进行扩容，新建一个容量为原来的1.5倍的新数组，然后将原来的数组元素通过Arrays.copyOf()这个方法复制到新的数组中。

## 2.2 ArrayList插入、删除、查询元素的时间复杂度各是多少？ ##

add(E):直接将元素反正最后不为空的位置，复杂度O(1)；  
remove(int):直接根据元素下标删除，然后将后面的元素向前移动一位，使用了System.arraycopy,复杂度O(n);  
get(int)：直接根据下标获取，复杂度O(1);

## 2.3 怎么求两个集合的并集、交集？ ##

并集使用**addAll(Collection)**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 7]  
交集使用**retainAll(Collection<?> c)**  
![在这里插入图片描述][20190815203243740.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 8]

还有什么下次在补充吧

[20190808022048665.png]: /images/20211104/66e64465bd3a493a9f3da969a6636c30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70]: /images/20211104/3d72adabbfb94cf795aafb4e355e7407.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 1]: /images/20211104/988d89d59b3642b8a59b2d5964fb658b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 2]: /images/20211104/4c49299cba7149de9123e8766e1f5d93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 3]: /images/20211104/e355cb242fd747c486f4414a69082041.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 4]: /images/20211104/cb39e55cc2c04a1dae5998006618afa1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 5]: /images/20211104/6d88b3ca08d44b48b95542413f33c5cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 6]: /images/20211104/2ab66db47f244d27ad355920043adfb9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 7]: /images/20211104/369ce501c589431599007b14e24c0e3c.png
[20190815203243740.png]: /images/20211104/7ee9e06343c14de1a8a37effed272b98.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70 8]: /images/20211104/a81b5e249eb44d0c96623486cea4c40e.png