集合作为一种存储数据的容器，是我们日常开发中使用最频繁的对象类型之一，JDK为开发者提供了一系列的集合类型，不同的集合类型采用不同的数据结构实现，所以，他们的应用场景也有所不同。今天咱们一起分析下ArrayList
list接口和类的实现关系
如图：ArrayList、Vector、LinkedList集合继承了AbstractList抽象类，AbstractList实现了List接口同时也继承了AbstractCollection 抽象类。
ArrayList是怎么实现的呢？
ArrayList的底层是通过数组实现的，咱们一起了解下数组的数据结构
数组(Array)是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。
注意定义中的几个关键字，线性表，连续的内存空间，相同类型的数据
线性表：线性表就是数据排成一条线一样的结构，每个线性表上的数据最多只有前和后两个方向，链表，队列，栈都属于线性表，而二叉树，堆属于非线性表，因为他们数据之间不只是简单的前后关系。
连续内存空间和相同数据类型的数据保证了数组“随机访问”的特性。
创建一个长度为10的int类型的数组
int[] a=new int[10]，计算机给数组a[10]，分配了一块连续的内存空间1000~1039，其中，内存块的首地址为base_address = 1000。
计算机需要随机访问数组中的某个元素时，它会通过下面的寻址公式，计算出该元素存的内存地址：
a[i]_address=base_address+i*data_type_size
其中data_type_size表示数组中每个元素的大小。此数组为int类型，所以data_type_size的大小为4个字节。例如寻找第三个元素的内存地址为：
a[2]_address=1000+2*4
a[2]_address=1008
所以，根据数组下标随机访问的时间复杂度为O(1)。
数组虽然查询元素速度很快，但是它“插入”和“删除”非常低效，当然也有优化的办法。
由于数组在内存中是一段连续的内存空间，所以在插入或者删除元素时，为了保持内存的数据的连续性，需要对后面元素进行搬移操作。
数组插入数据
在数组末尾插入数据，不需要移动数据，插入数据的时间复杂度为O(1)在数组的开头插入数据，那所有的数据都需要一次往后移动一位，所以最坏的时间复杂度是O(n)因为每个位置插入元素的概率是一样的，所以平均时间复杂度为(1+2+…n)/n=O(n)如果为有序数组，我们在某个位置插入一个新元素，必须按照刚才的方法，搬移插入后的数据。如果是无序数组，只是作为存储数据的容器，那么数据的插入删除可以优化。
将一个新的元素x插入到数组某一个位置k，可以将k位置的数据移动到数组尾部，将x插入。这样在特定场景下，在k位置插入一个元素的时间复杂度就会下降到O(1)删除数据与插入数据的时间复杂度基本类似
删除数组中的数据，可以先将数据标记为删除状态，当数组没有更多空间存储数据时，我们再触发执行一次正在的删除操作，这样就大大减少了删除操作导致的数据搬移。数组的数据结构就介绍到这里，接下来一起看ArrayList
ArrayList实现了List接口，继承了AbstractList抽象类，底层是数组实现的，并且实现了自增扩容数组大小。ArrayList实现了Cloneable接口和Serializable接口，可以实现克隆和序列化ArrayList实现了RandomAccess接口，这个接口是一个空接口，没有实现，它是一个标志接口，只要实现该接口的List类，都能实现快速随机访问。ArrayList属性主要由数组长度size，对象数组elementData，初始化容量default_capacity等组成，其中初始化容量默认为10。ArrayList被关键字transient修饰，我们都知道，被transient关键字修饰的字段都不会被序列化，但是ArrayList实现了序列化接口，这是为什么呢。ArrayList是基于数组实现的，由于ArrayList的数组是基于动态扩增的，所以并不是所有被分配的内存空间都存储了数据，如果采用外部序列化法实现数组的序列化，会序列化整个数组，ArrayList为了避免这些没有存储数据的内存空间被序列化，内部提供了两个私有方法writeObject和readObject来自我完成序列化和反序列化，从而节约了空间和时间。ArrayList 构造函数
ArrayList有三个构造函数
创建ArrayList对象时，传入一个初始化值默认创建一个空数组对象传入一个集合类型进行初始化当新增元素时，如果存储的元素已经超过了其已有大小，它会计算元素大小后再进行动态扩容，数组的扩容会导致整个数组进行一次内存复制，所以，我们在初始化一个ArrayList是，如果能确定ArrayList的大小，最好通过构造函数设定大小，减少数组扩容次数。
ArrayList 新增元素
新增元素的方法有两种
将元素添加到数组末尾添加元素到任意位置
两个方法的相同之处在于，添加元素之前都会先确认容量大小，如果容量够大，不用进行扩容，如果容量不够大，就会安按照原来数组的1.5倍大小进行扩容。扩容之后需要将数组复制到新的分配的内存地址。
两个方法的不同之处是，添加元素到任意位置，会导致在该位置后面的所有元素都需要重新排列，而将元素添加到数组末尾，在没有发生扩容的前提下，是不会有元素复制排序过程的。
ArrayList 删除元素
ArrayList在每一次有效的删除元素操作之后，都要进行数组的重组，删除元素位置越靠前，数组重组的开销越大。
ArrayList 遍历元素
由于ArrayList是基于数组实现的，所以在获取元素的时候是非常快捷的。
