Java集合——Array、ArrayList、LinkedList

1. ArrayList和Array的区别

1. 大小和自动扩容

Array：创建时指定大小，大小固定。若数组被创建，其大小不能更改

ArrayList：动态数组实现，可以动态增长或缩小。在不断添加元素时，ArrayList会自动进行扩容

2. 支持泛型

Array不支持泛型，ArrayList可以指定存储的元素类型

3. 存储对象

Array可以存储基本类型数据，也可以存储对象

ArrayList之恶能存储对象，对于基本类型数据需要使用对应的包装类(Integer、Double等)

4. 集合功能

Array是一个简单的数据结构，不提供额外的方法进行元素的增删改查操作

ArrayList是集合框架的一部分，提供了丰富的增删改查方法等

2. ArrayList和LinkedList的区别及其底层实现

ArrayList

基于动态数组，提供快速的随机访问和非常快的遍历操作

1. 随机访问：时间复杂度为O(1)

2. 增删元素：在末尾加元素很快，但在其他地方操作可能需要移动后续元素，时间复杂度O(n)

3. 有扩容开销

使用场景：需要频繁访问元素，且增删操作主要在列表末尾进行，选择ArrayList

LinkedList

基于双向链表，每个元素包含前后元素的引用

1. 随机访问：效率较低，因为需要从头或从尾开始链接遍历，复杂度为O(n)

2. 增删元素：在列表任意位置增删元素都很快，这只需要改变几个引用指针，是O(1)复杂度

特殊方法：提供了额外的方法，如addFirst()，addLast()，removeFirst(),removeLast()

使用场景：需要频繁增删元素但访问不是那么常见，选择LinkedList

3. ArrayList扩容机制

1. ArrayList初始化容量默认为10

2. 添加元素到ArrayList时，ArrayList会判断是否达到了最大大小Integer.MAX_VALUE，若达到则不再扩容，否则扩容

3. 扩容计算：grow()

4. 若新容量满足需求，调用Arrays.copyof方法，实现扩容。若不满足，则新容量大小为当前所需的容量+1