ArrayList 概述

自己的理解，数据结构的出现必定是伴随的原有的数据结构进行升级而出现的。为什么会有arraylist呢？然后arraylist是一种以数组为底层的数据结构。那么数组的大小是不可变的，但是实际运用中我们经常要求可以改变，所以就衍生出arraylist这种集合。

ArrayList的基本特点

ArrayList结构

1.ArrayList 底层是一个动态扩容的数组结构

2.允许存放（不止一个） null 元素（hashmap只允许有一个null元素，hashtable不允许null元素）

3.允许存放重复数据，存储顺序按照元素的添加顺序

4.ArrayList 并不是一个线程安全的集合。如果集合的增删操作需要保证线程的安全性，可以考虑使用CopyOnWriteArrayList或者使用collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类.

扩容机制&add方法

由于arrayList是长度可变的，也就是说如果存放的元素大于数组长度就会进行扩容，那么扩容机制必定是伴随的add增加元素的方法进行的，我们来读一读arraylist中的add方法。

add方法

1.首先调用 ensureCapacityInternal方法，参数树size+1，也就是判断如果要添加这个元素，那么数组的元素就变成了size+1，是否可以存放的下呢？

判断是否为新建数组

2.判断数组是否为空，由于构造函数中如果是无参构造函数那么就会创建一个空的数组，如果是空的数组的话，就会将默认数组大小为10。然后进行调用扩容判断。

判断是否需要扩容

这里要注意的是为什么会有modcount这个变量呢？ 可以查阅资料，会发现原来他是迭代器中的一个变量，为什么arraylist是线程不安全的呢?其实可以这么认为含有modcount 的集合都是线程不安全的，因为如果我们在遍历的时候去修改数组就会导致线程不安全。如果这个集合进行了修改变动的话，modcount都必须要改变，所以modcount含义就是集合变动次数。是迭代器中的一种fail-fast机制。

3.如果数组的元素个数大于数组的长度就要进行扩容。

扩容机制

由此看来 ArrayList 的扩容机制的知识点一共又两个

1.每次扩容的大小为原来大小的 1.5倍 （当然这里没有包含 1.5倍后大于 MAX_ARRAY_SIZE 的情况）

2.扩容的过程其实是一个将原来元素拷贝到一个扩容后数组大小的长度新数组中。所以 ArrayList 的扩容其实是相对来说比较消耗性能的。

迭代器

迭代器 Iterator 模式是用于遍历各种集合类的标准访问方法。它可以把访问逻辑从不同类型的集合类中抽象出来，从而避免向客户端暴露集合的内部结构。

ArrayList底层是使用数组进行实现的，在使用下标进行访问时可以做到o(1)的时间复杂度，但是在进行插入删除时需要移动元素，同时当ArrayList底层数组空间不足时，需要扩充容量，（默认扩大为原来的1.5倍），这会进行元素的重新拷贝，所以不适合于频繁进行插入删除操作的情况。其扩容是用到System.arraycopy(a, 0, elementData, size, numNew);这么一个方法，也就是会新建一个数组然后进行复制。

总结：

1.ArrayList 底层是一个动态扩容的数组结构,每次扩容需要增加1.5倍的容量

2.ArrayList 扩容底层是通过Arrays.CopyOf和System.arraycopy来实现的。每次都会产生新的数组，和数组中内容的拷贝，所以会耗费性能，所以在多增删的操作的情况可优先考虑 LinkList 而不是 ArrayList。

3.ArrayList 的 toArray 方法重载方法的使用。

4.允许存放（不止一个） null 元素，

5.允许存放重复数据，存储顺序按照元素的添加顺序

6.ArrayList 并不是一个线程安全的集合。如果集合的增删操作需要保证线程的安全性，可以考虑使用CopyOnWriteArrayList或者使collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类.

ArrayList集合知识点总结

ArrayList是一个动态数组，查询快、增删慢。ArrayList是线程不安全的，运行效率快，允许元素为null。

1. ArrayList与LinkedList的区别有哪些？

答：ArrayList的底层数据结构为数组，增删慢、查询快，线程不安全，效率高。

LinkedList的底层数据结构为链表，增删快、查询慢，线程不安全，效率高。

2. ArrayList与Vector的区别？

答：Vector底层数据结构为数组，增删慢、查询快，线程安全，效率低，每次扩容为原来数组的2倍。

ArrayList底层数据结构为数组，增删慢、查询快，线程不安全，效率高，每次扩容为原来数组的1.5倍。

3. ArrayList的底层是数组，数组的名称是什么？类型是什么？

答：名称是elementData，类型是Object[]，所以ArrayList里面可以存放任意类型的元素。

4. ArrayList底层数组的默认初始化容量是多少？当超出这个大小时，每次扩容是多少？

答：默认初始化容量是10。当超出这个大小时，每次扩容1.5倍。

5. LinkedList的底层是什么？

答：双向链表。（hashmap是使用单向链表）

6. ArrayList里面可以存null吗？

答：可以。

7. ArrayList的底层是数组，它和数组有什么区别吗？

答：ArrayList区别于数组的地方在于能够自动扩展大小，每次扩容1.5倍。

8. 当向ArrayList集合中添加元素时需要调用add()方法，add()方法的执行流程是怎样的？

答：调用add()方法时，add()方法首先调用ensureCapacityInternal()来判断elementData数组容量是否足够，ensureCapacityInternal()之所以能够判断，是因为它内部调用了ensureExplicitCapacity()方法，这个方法才是真正判断elementData数组容量是否够用的关键方法。如果容量足够，则直接将元素添加到ArrayList中；如果容量不够，则ensureExplicityCapacity()方法内部会调用grow()方法来对数组进行扩容。扩容成功之后，再将元素添加到ArrayList扩容之后的新数组中。

注意：如何扩容呢？会先创建一个原来数组1.5倍大小的新数组，然后将数据拷贝到新数组中。

9. 在调用ArrayList的remove(int index)方法时，执行流程是怎样的？

答：首先判断index是否合理，如果合理的话，会调用System.arraycopy()方法把指定下标到数组末尾的元素向前移动一个单位，并且会把数组最后一个元素设为null。这样是为了方便GC回收。

10. ArrayList在调用get(int index)方法查询的时候，执行流程是怎样的？

答：首先判断index是否合理，然后调用elementData()方法，elementData()方法返回根据index查到的具体的元素。注意：这里的返回值都经过了向下转型（Object -> E）。

11. ArrayList的大小是如何自动增加的？你能分享一下你的代码吗？

答：当向ArrayList中增加一个对象的时候，Java首先会判断ArrayList的底层数组elementData是否还有足够的空间来存储这个对象，如果有，就直接存，如果没有，就会基于原有的数组扩容出一个1.5倍的新数组，并将数据全部复制到新数组中。

请注意这样一个情况，新建了一个数组，旧数组的对象被复制到了新的数组中，并且现有的数组引用指向新的数组。

12. 什么情况下你会使用ArrayList？什么情况下你会选择LinkedList？

答：当对数据的主要操作为索引或只在集合的末端增加、删除数据时，使用ArrayList效率比较高；当对数据的操作主要为指定位置的插入或删除操作时，使用LinkedList效率比较高。

13. 在ArrayList的增、删、改、查中，什么地方会修改modCount？

答：增如果导致扩容，则会修改modCount；删一定会修改modCount；改和查一定不会修改modCount。

14. 为什么ArrayList在增、删的时候效率低？

答：因为在增、删的过程中会涉及到数组的复制，效率低。

15. ArrayList的时间复杂度是多少？

答：当修改、查询或者只在数组末尾增、删时，时间复杂度为O(1)；对指定位置的元素进行增、删时，时间复杂度为O(n)。