ArrayList 知识点

知识点

数组是一种用连续空间来存储相同数据类型的线性数据结构。

ArrayList 的底层是使用动态的数组实现的。

ArrayList 的初始化容量是0，只有第一次添加的时候才会为10.

ArrayList 在进行扩容的时候都是上一次大小的1.5倍，每次扩容都需要拷贝数组。

ArrayList 添加元素的步骤

• 确保数组的容量能够放下元素（计算size + 1 是否比当前数组的长度大，是的话进行扩容）
• 将数组的 size + 1 的下标指向需要添加的这个元素。

如何实现数组跟List之间的转换

数组转换为List： 使用Arrays.asList();这个方法

List转换为数组： 使用List.toArray(); 这个方法

使用Arrays.asList() 转换的List，会受原先数组数据变动的影响。因为List的存储数据的数组指向了原先数组。

使用toArray() 转换的数组，不会受原先List数据变动的影响。因为底层实现的原理是将List的数据拷贝到数组。

ArrayList 和 LinkedList 的区别

1、底层的实现

ArrayList 的底层是基于动态数组去实现的。

LinkedList 的底层是基于双向链表实现的。

2、操作数据的效率

底层数据结构

ArrayList的底层是使用动态数组实现的。

LimkedList的底层是使用双向链表实现的。

操作数据效率

• ArrayList 可以使用下标进行查询数据，LinkedList 不支持下标查询。
• 查询未知下标：ArrayList需要遍历，链表也需要遍历，时间复杂度都是O(n)
• 新增跟删除：ArrayList尾部增删，时间复杂度都是O(1)。其他部分增删需要挪动数组，时间复杂度是O(n)
• 新增跟删除：LinkedList 头尾部增删，时间复杂度是O(1)，其他部门都需要遍历数组，时间复杂度是O(n)

内存空间占用

ArrayList的底层是使用数组实现的，内存连续，节省内存。

LinkedList的底层是使用双向链表实现的，每个节点需要多俩个指针，更占用内存。

线程安全

ArrayList 和 LinkedList 都是非线程安全的

能够实现线程安全的方案：

1、尽量声明为局部变量

2、使用Collections.synchronizedList()，底层是加锁，相对应性能降低。