ArrayList LinkedList Vector 面试题

1. ArrayList的数据结构是如何实现的？

ArrayList底层维护了一个可动态扩容的数组，它的增删改查就是对数组的增删改查。
有以下特性：

1. 快速查找（时间复杂度O(1)）
2. 容量动态增加（每次数组长度扩容为原来的1.5倍）

   2. ArrayList 实现了哪些接口，继承了什么类？

   ArrayList 继承了AbstractList类，实现了List、RandomAccess、Cloneable、Serializable接口。

   RandomAccess 快速访问标记接口，表示查找速度O(1) Cloneable 接口，实现了Cloneable接口，调用clone()方法产生深拷贝（克隆的对象与原对象地址值不同） Serializable接口，可序列化

3. ArrayList的初始容量，扩容方式？

• 如果是空参构造的ArrayList对象，底层数组会在第一次add()值时扩容到默认大小10。
• 如果是有参构造的ArrayList对象：

如果参数设置大于0，则会在构造方法中就创建对应大小的数组；
如果参数设置小于等于0，与空参构造同。

• 当使用add方法添加或插入元素之前会先检测数组长度：

如果数组长度为0，则扩容到10；
如果数组长度不为0，则扩容到原来1.5倍；
如果扩容后的数组长度>Integer.MAX_VALUE-8，则将其扩容到Integer.MAX_VALUE。

• 扩容的底层实现是使用Arrays.copyOf()方法，实现浅拷贝——新建一个原数组大小1.5倍大小的数组，将原数组的数据拷贝到新数组中。

4. ArrayList如何尽量避免数组扩容？

预估要保存元素的数量

• 利用有参构造，在构造ArrayList对象的时候就指定容量大小；
• 利用ArrayList的 ensureCapacity( int minCapacity)方法，实时地指定容量大小；

5. ArrayList的remove()方法是如何实现的？

remove()方法有两个重载方法，分别是根据index和根据对象删除元素。

• 根据index删除元素：
  1. 首先判断index是否超出size范围，没有超出就获取该元素；
  2. 然后将该元素右边所有的元素向左复制（System.arraycopy(…)）；
  3. 并将size-1，将最后一个元素位置置空；
  4. 返回被删除元素。
• 根据Object删除元素：
  1. 判断输入对象，如果不为空就从头遍历；
  2. 使用equals方法判断两个元素是否相等，如果相等就调用fastRemove(index)方法；
  3. fastRemove(index)方法与remove(index)类似；
  4. 返回True/False；

6. ArrayList和LinkedList线程是否安全

ArrayList和LInkedList线程写操作不安全，会触发ConcurrentModificationException异常，只能在单线程的环境下使用。
多线程的环境有如下两个方法：
1.使用 Collections.synchronizedList(new 【ArrayList<>()】**【LinkedList<>()】**)获取一个线程安全的List类对象；
2.使用 new CopyOnWriteArrayList<>() 创建一个线程安全的List类对象；

CopyOnWrite 指写入时复制，COW 计算机程序设计领域的一种优化策略；
多线程调用List时，写入会覆盖，容易造成数据问题，所以写入时要避免覆盖；
读写分离；
CopyOnWrite 底层使用的是Lock 而不是 synchronized，所以效率比Vector要高（Vector底层使用的是synchronized）；

7. 快速失败机制

快速失败是指某个线程在迭代集合类的时候，不允许其他线程修改该集合类的内容，不然会出现ConcurrentModificationException异常，这个时候该迭代器就快速失败了。
值得注意的是：用iterator迭代Collection的时候，iterator就是另起的一条线程，此时如果用Collection.remove()的方法，则是从主线程中对Collection进行修改，故触发了快速失败。而使用迭代器自带的iterator.remove()则不会造成快速失败。

8. ArrayList什么时候用到了浅复制？

1.动态扩容的时候调用Arrays.copyOf()方法实现浅复制；
2.插入元素的时候调用System.arraycopy()方法实现了浅复制;
3.删除元素的时候调用System.arraycopy()方法实现了浅复制。
使用浅复制的操作复杂度会较高，所以ArrayList不适合插入或删除元素。

9. LinkedList的数据结构是如何实现的

双向链表。
特性：
在头尾添加元素的时间复杂度是O(1);
涉及到查找节点的操作时间复杂度为O(n);

10. LinkedList的增删改查

● 链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作。对比ArrayList是通过System.arraycopy完成批量增加的。增加一定会修改modCount。
● 查找node：通过下标获取某个node 的时候会判断index处于size的前半段还是后半段，然后从头或从尾进行遍历，以提高查询效率
● 删：会修改modCount。 按下标删，也是先根据index找到Node，然后去链表上unlink掉这个Node。 按元素删，会先去遍历链表寻找是否有该Node，如果有，去链表上unlink掉这个Node。
● 改：先根据index找到Node，然后替换值。改不修改modCount。
● 它的CRUD操作里，都涉及到根据index去找到Node的操作（ node(int index) ）。

11. LinkedList的add(E e) 与 offer(E e)的区别

JDK1.8中，offer(E e) 的方法体直接返回了一个 add(e)，所以两者没有区别。只是在作为队列的时候添加元素没有一个统一的命名方式，有些用add，有些用offer，所以就保留了几个相同功能但不同名的方法。

12. ArrayList 与 Vector的异同

相同点：

1. ArrayList和Vector都实现了List、RandomAccess、Cloneable、Serializable接口，继承了AbstractList抽象类；
2. ArrayList和Vector底层实现都是数组，都利用Arrays.copyOf()和System.arraycopy()方法浅复制。

不同点：

1. ArrayList是线程不安全的，Vector是线程安全的，Vector的所有操作方法都用了synchronized修饰；
2. ArrayList的默认扩容方式是将数组增大到原数组的1.5倍大小，Vector则是将数组增大到原数组的2倍大小；
3. Vector可以设定每次扩容的增加量（capacityIncrement），ArrayList不能；
4. Vector可以实时指定数组大小（多砍少补），ArrayList不能；

由于ArrayList是线程不安全的，所以在单线程操作时效率会比Vector效率高，如果是多线程访问，需要使用Vector。

13. ArrayList 和 LinkedList的异同

相同点：

1. 都实现了List、Cloneable、Serializable接口
2. 线程都不安全

不同点：

1. ArrayList的底层实现是数组，是顺序存储接口；LinkedList的底层实现是双向链表，是链式存储结构；
2. ArrayList可以进行快速查找(get,set)，查找时间复杂度为O(1)；LinkedList只能遍历查找，时间复杂度为O(n)；
3. ArrayList插入和删除元素会伴随浅拷贝，效率低；LinkedList插入删除元素效率高；
4. ArrayList的主要内存开销在于为List列表预留空间；LinkedList开销在于存储节点信息和指针信息。