List源码分析
java.util
接口 List<E>
所有超级接口:
Collection<E>, Iterable<E>
所有已知实现类:
AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector
List接口在java.util包里,继承Collection<E>超级接口
主要分析一下:ArrayList、LinkedList、Vector
|
ArrayList |
LinkedList |
Vector |
数据结构 |
Object[] size |
Node<E> first Node<E> last size |
Object[] size |
初始值 |
10 |
0 |
10 |
是否有序 |
有序可重复 |
有序可重复 |
有序可重复 |
安全性 |
不安全 |
不安全 |
线程安全 |
扩容方案 |
每次ADD扩容0.5倍 可指定长度 |
自增长 |
容量不够时2倍扩容 可指定长度 |
性能分析 |
查找快,增删慢 |
查找慢,增删快 |
查找快,增删慢 |
是否可变 |
不可变 |
不可变 |
可变 |
1,ArrayList
Add():添加方法
对于每次ADD都扩容,官方文档解释如下:
The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
意为:分担时间开销
Remove():删除方法
Get():查找方法
直接通过数组下标读取。
由上述代码分析可见:
ArrayList频繁的数组拷贝操作性能低下。add/remove慢,查找快。
使用建议:
- 创建线程安全的List方式如下:
List list = Collections.synchronizedList(new ArrayList(...));
- 指定list大小
在知道List大小情况下,建议在创建时指定list大小,方法为ensureCapacity(int minCapacity)
- 遍历方式
ArrayList继承AbstractList接口,实现RandomAccess接口,使用for循环遍历,效率高于Iterator
AbstractList接口是对“随机访问”数据存储(如数组)支持
RandomAccess接口是List 实现所使用的标记接口,用来表明其支持快速(通常是固定时间)随机访问。
2,LinkedList
链表的数据结构:
Node(prev) |
item |
Node(next) |
Add():添加方法
Remove():删除方法
Get():查找方法
使用二分法遍历查找。
由上述代码分析可见:
LinkedList使用链表数据结构。add/remove较快,查找慢。
- 创建线程安全的List方式如下:
List list = Collections.synchronizedList(new LinkedList(...));
- 遍历方式
LinkedList继承AbstractSequentialList接口,实现Deque接口,使用Iterator循环遍历,效率高于for
AbstractSequentialList接口是对“连续访问”数据存储(如链接列表)支持的
Deque接口是双端队列,一个线性 collection,支持在队列两端插入和移除元素。
3,Vector
Add():添加方法
容量不够时按照当前数组长度的2倍进行扩容。
Remove():删除方法
同ArrayList
Get():查询方法
同ArrayList
使用建议:
- 线程安全,方法均加了synchronized关键字
注意,因为vector提供set方法修改值,导致在iterator时会造成不安全。
- 指定向量大小
在知道向量大小情况下,建议在创建时指定向量大小,方法为ensureCapacity(int minCapacity)
- 遍历方式
vector继承AbstractList接口,实现RandomAccess接口,使用for循环遍历,效率高于Iterator