meta|Java集合面试题看这篇就够了( 二 )

底层是链表。
数组天然支持随机访问，时间复杂度为 O(1) ，所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为 O(n) ，所以不支持快速随机访问。
ArrayList 实现了 RandomAccess 接口，就表明了他具有快速随机访问功能。RandomAccess接口只是标识，并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的！
4.说一说Vector 和 ArrayList 的区别？他们两个都实现了 List 接口。底层数据结构都是数组。
不同的是：

vector通过 remove 、 add 等方法加上 synchronized 关键字实现线程同步，所以是线程安全的。而ArrayLis是线程不安全的
由于vector使用了 synchronized 进行加锁，所以性能不如ArrayList
Vector 扩容时，如果未指定扩容递增值 capacityIncrement ，或该值不大于 0 时，每次扩容为原来的 2 倍，否则扩容量为 capacityIncrement 的值。 ArrayList每次扩容为旧容量的 1.5倍

5.说说ArrayList 的扩容机制？

当使用add方法的时候首先调用 ensureCapacityInternal 方法，传入 size+1 进去，检查是否需要扩容
如果空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA ，就初始化为默认大小10 ，获取“默认的容量”和要扩容的大小两者之间的最大值
和当前数组长度比较，如果 if (minCapacity - elementData.length > 0) 执行 grow 扩容方法
将数组扩容为原来的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1);
检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量
再检查新容量newCapacity 是否超出了ArrayList所定义的最大容量，若超出了，则调用 hugeCapacity() 来比较minCapacity和 MAX_ARRAY_SIZE ，如果minCapacity大于MAX_ARRAY_SIZE ，则新容量则为Interger.MAX_VALUE ，否则，新容量大小则为 MAX_ARRAY_SIZE（ MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 ）
ArrayList 中copy数组的核心就是 System.arraycopy 方法，将original数组的所有数据复制到copy数组中，这是一个本地方法

6.Array和ArrayList有何区别？

Array可以容纳基本类型和对象，而ArrayList只能容纳对象
Array是指定大小的， ArrayList 的容量是根据需求自动扩展
ArrayList提供了更多的方法和特性，比如：addAll() ， removeAll() ， iterator()等等

???面试官追问：什么时候更适合使用Array？
7.遍历一个List有哪些不同的方式？先说一下常见的元素在内存中的存储方式，主要有两种:

顺序存储 (Random Access)：相邻的数据元素在内存中的位置也是相邻的，可以根据元素的位置读取元素。
链式存储 (Sequential Access)：每个数据元素包含它下一个元素的内存地址，在内存中不要求相邻。例如LinkedList 。

主要的遍历方式主要有三种：
for
Iterator
foreach

代码如下：
public class TestLinkedList {

public static void main(String[
args) {

List<String> list = new ArrayList<>();