今天来学习ArrayList相关内容作为面试必问的知识点来深入了解一波

思维导图

ArrayList就是动态数组是List接口的可调整大小的数组实现除了实现List接口之外该类还提供了一些方法来操纵内部使用的存储列表的数组大小。

它的主要底层实现是数组Object[]

数组的特点大家都知道遍历查询速度快——数组在内存是连续空间可以根据地址索引的方式快速获取对应位置上的元素。

但是它的增删速度慢——每次删除元素都需要更改数组长度、拷贝以及移动元素位置。

ArrayList类架构图

RandomAccess、Cloneable、Serializable

与ArrayList类似的是LinkedList但是LinkedList底层是链表它的数组遍历速度慢但增删速度很快。

2ArrayList构造方法

无参构造使用默认的size为10的空数组在构造方法中没有对数组长度进行设置会在后续调用add方法的时候进行扩容。

无参构造

里面是一个赋值操作右边是一个空容量数组左边则是存储数据的容器以下是参照源码分析

//默认空容量数组长度为0

DEFAULTCAPACITY_EMPTY_ELEMENTDATA

transient

参数大于0elementData初始化为initialCapacity大小的数组参数等于0elementData初始化为空数组参数小于0抛出异常

Collection类型构造

将一个参数为Collection的集合转变为ArrayList(实际上就是将集合中的元素换为了数组的形式)如果传入的集合为null会抛出空指针异常。

c.toArray()可能不会正确地返回一个

Object[]数组那么使用Arrays.copyof()方法。

如果集合转换成数组之后数组长度为0那就直接使用自己的空成员变量初始化elementData。

上面的构造方法理解起来比较简单无参构造和初始化容量构造的目的都是初始化底层数组elementData(this.elementDataXXX)

无参构造方法会将elementData初始化一个空数组插入元素时扩容将会按默认值重新初始化数组有参构造方法会将elementData初始化为参数值大小0的数组

如果在构造

elementData如果不指定初始化值在第一次添加元素值时会使用默认的容量大小

elementData

一般情况下我们用默认的构造方法即可。

上面说到使用无参构造时会调用add方法并进行扩容下面来看看add方法以及扩容的细节。

3添加add()方法分析

我们看到add方法中在添加元素之前会先判断size的大小所以我们来看看ensureCapacityInternal方法的细节之处

private

DEFAULTCAPACITY_EMPTY_ELEMENTDATA)

出较大值

ensureExplicitCapacity(minCapacity);

add

进第1个元素时minCapacity为(size101)1在Math.max()方法比较后minCapacity

为10。

然后紧接着调用ensureExplicitCapacity更新modCount的值并判断是否需要扩容。

接下来看ensureExplicitCapacity方法

private

//判断新容量-最大数组大小是否0,如果条件满足就计算出一个超大容量if

(newCapacity

调用数组工具类方法,创建一个新数组,将新数组的地址赋值给elementData

elementData

{rangeCheckForAdd(index);//1检测是否需要扩容ensureCapacityInternal(size

1);

modCount!!//2将index及其之后的元素都向后移一位System.arraycopy(elementData,

index,

{//这里判断的indexsizeindex小于0超出指定范围就报错if

(index

IndexOutOfBoundsException(outOfBoundsMsg(index));

import

ArrayList();list.add(海心焰);//在index为1的位置处添加数据list.add(1,玄黄炎);System.out.println(list);}

}运行结果

c);这个方法的描述是按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。

运行结果

c);这个方法和上面的方法都是把一个集合中的元素添加到另外一个集合中去不同的在于上面的方法是默认添加至目标集合的尾部而此方法是包含索引的也就是在指定位置开始插入元素。

运行结果

若值newCapacity比传入值minCapacity还要小则使用传入minCapacity若newCapacity比设定的最大容量大则使用最大整数值

比方说现在需要往数组里添加10w条数据我们来看看前后的时间变化

ArrayList底层是数组实现的那么每次添加数据时会不断地扩容这样的话会占内存性能低所以导致时间很长。

我们可以用ArrayList的指定初始化容量的构造方法来解决性能低的问题。

5.3ArrayList在增删元素的时候是怎么进行的还有为何很慢

在前面我们说过它有按照索引添加也有直接添加的。

在这之前需要校验长度问题ensureCapacityInternal如果长度不够则需要进行扩容操作。

如果后面的数据量级过大在100万条数据中新增一个元素后面的元素都要拷贝以及移动位置所以说效率很低。

ArrayList线程是不安全的。

线程安全的数组容器是Vector它的原理是把所有的方法都加上synchronized。

我们来测试一下先准备一个线程任务类

可以看到会报异常错误有的线程还是为null这说明ArrayList线程是不安全的。

Vector集合

或者我们可以直接加synchronized关键字把不安全的线程变成安全的

加关键字synchronized

线程安全就是多线程访问时采用了加锁机制当一个线程访问该类的某个数据时进行保护其他线程不能进行访问直到该线程读取完其他线程才可使用。

不会出现数据不一致或者数据污染。

线程不安全就是不提供数据访问保护有可能出现多个线程先后更改数据造成所得到的数据是脏数据。

List接口下面有两个实现一个是ArrayList另外一个是Vector。

从源码的角度分析因为Vector的方法前加了synchronized关键字。

Items[Size]

0注意哦我们假设的是添加一个元素是要两个步骤哦而线程A仅仅完成了步骤1所以线程B也将元素存放在位置0。

然后线程A和线程B都继续运行都增加

Size

底层数据结构ArrayList底层使用的是数组LinkedList底层使用的是双向链表

插入和删除元素操作ArrayList采用的是数组存储所以插入和删除元素是跟元素的位置有关系。

LinkedList采用的是链表存储删除元素是不受元素位置影响的如果是要在指定位置i插入和删除的话add(int

indexE

随机访问ArrayList对于随机元素访问的效率明显比LinkedList高。

随机访问就是通过元素的索引来获取元素也就是set和get(int

线程不安全ArrayList和LinkedList都是不同步的也就是说都是线程不安全的。

接口实现ArrayList实现了RandomAccess可以支持随机元素访问而LinkedList实现了Deque可以当做队列使用

内存空间占用情况ArrayList的空间占用主要体现在list列表的末尾会有一定的容量空间它的优势在于内存的连续性CPU的内部缓存结构会缓存连续的内存片段可以大幅度降低内存的性能开销提高效率LinkedList的空间占用体现在每一个元素都需要消耗空间内存要存放前驱后继等数据。

当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能

当操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,使用LinkedList会更好。