Java数据结构之——List
2017年07月28日 02:09
阅读 820
|
ArrayList |
LinkedList |
|
描述 |
可变数组 |
链表 |
|
底层结构 |
数组: private transient Object[] elementData; |
双向循环链表: E item; Node<E> next;
Node<E> prev; |
|
特性 |
序列化 |
支持 |
支持 |
线程安全性 |
1非线程安全 |
1 非线程安全 |
|
随机访问 |
支持,下标快速访问O(1) |
需要遍历O(n) |
|
Null值 |
允许 |
允许 |
|
空间(capacity) |
默认容量 |
10 |
由于链表的特性,LinkedList支持在任意位置插入数据,无需动态扩容 |
增长方式 |
数据copy |
||
增长动因 |
旧空间无法满足新加元素后总长度 |
||
增量计算 |
int newCapacity = (oldCapacity * 3)/2 + 1; 即为原来的1.5倍 |
||
性能优化点 |
空间大小 |
如果预先知道数组大小,初始化时设置合适的大小,避免因数组扩容导致数据拷贝 |
|