ArrayList 和 LinkedList区别 以及 ArrayList集合知识点总结
ArrayList和LinkedList的区别，各个基本操作的复杂度是多少，方法是什么，ArrayList的底层结构是什么，如果数组容量不够怎么办，扩容之后get的复杂度是多少…
**答：**ArrayList与LinkedList都是List接口的实现类， List是一个接口又继承了Collection接口。
ArrayList: get() 、add()、remove()
LinkedList: 独有方法addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast()
区别：
1、 底层实现角度。
ArrayList：是基于动态数组的数据结构；名称是elementData，类型是Object[]，所以ArrayList里面可以存放任意类型的元素
LinkedList：是基于双向循环链表的数据结构
2、 随机访问（索引）元素角度。get
ArrayList：数据存储是连续的，因此支持用下标来访问元素get(int index)，直接返回index位置上的元素，随机访问元素速度快 O(1)
LinkedList：需要通过for循环进行查找，虽然LinkedList已经在查找方法上做了优化，比如index < size / 2，则从左边开始查找，反之从右边开始查找，但是还是比ArrayList要慢。 O(N)
3、 插入，删除元素角度。 Add remove
ArrayList：想要在指定位置插入或删除元素时，主要耗时的是System.arraycopy动作，会移动index后面所有的元素，从而会重新调整索引顺序,调整索引顺序会消耗一定的时间，所以速度上就会比LinkedList要慢许多；O(N)
LinkedList：主耗时的是要先通过for循环找到index，再改变前后对象的引用，然后直接插入或删除，效率较高。O(N)
4、 初始容量，扩容角度。
ArrayList：默认初始化容量是10，当存储元素大小超过初始容量时，需要动态扩容为原来的1.5倍加1。如果设置后的新容量还不够，则直接新容量设置为传入的参数（也就是所需的容量），而后用Arrays.copyof()方法将元素拷贝到新的数组。从中可以看出，当容量不够时，每次增加元素，都要将原来的元 素拷贝到一个新的数组中，非常之耗时。
可以指定容量，避免扩容，
LinkedList：使用了链表的结构，因此不需要维护容量的大小。
5、 线程安全角度。
二者都是非线程安全的容器。
6、 实现栈和队列角度。
LinkedList要优于ArrayList。因为LinkedList是个双向链表，它同样可以被当作栈、队列或双端队列来使用（看图）。例如Queue queue=new LinkedList<>();
总结：当对数据的主要操作为索引或者只在集合末端增加、删除元素时候，使用ArrayList效率比较高。当对数据的主要操作为指定位置的插入或者删除操作时，使用LinkedList效率比较高。
————————————————————————————————————————————————
——————————————————————————————-—————————————————
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的底层是什么？
答：双向链表。
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)。
参考：https://www.cnblogs.com/lewis0077/p/5275061.html
https://blog.****.net/lz1170063911/article/details/79836582