1 概述
List 接口规定它的实现类需要有以下特性
- 是一个有序集合
- 可以包含多个相同的元素
- 访问指定位置的元素
- Java 集合框架实现List接口的有三个常用类ArrayList, LinkedList 和 Vector
2 ArrayList
-
ArrayList的底层实际上是在维护一个数组,由于数组的内存是连续的,所以可以很方便地通过索引index来访问指定位置的元素。
-
数组在初始化的时候长度固定了,所以如何设置数组的长度成了一个问题。ArrayList提供了一个构造器来设置初始值。如果不传入这个值,会把elementData初始化为ArrayList里维护的一个空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
-
添加的元素超过当前数组的长度是不可避免的,那么当前数组容量不够的时候,就需要一个更长的数组。第一个问题就是新数组的长度怎么定呢?
- 定小了,很容易达到下一次饱和,就需要不停开辟新的数组,拷贝数组。
- 定得太大了,申请了一大片内存很可能根本用不到,浪费!
-
ArrayList提供的扩容策略是
- 首先保证当前操作需要的最小容量 minCapacity
- 然后假定我需要扩容的容量是 newCapacity = oldCapacity + (oldCapacity << 1) 也就是 现有容量的1.5倍
- 取两个值更大的那个 newCapacity = max(minCapacity, newCapacity)
- 再与数组理论上允许的最大值 MAX_ARRAY_SIZE(等于Integer.MAX_VALUE - 8) 比较, 如果minCapacity比MAX_ARRAY_SIZE还大,直接把容量扩充到Integer.MAX_VALUE
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
- 总之,由于数组的特性,ArrayList 在访问元素的时候可以通过内存地址偏移量快速访问。在执行需要改变数组结构的操作时,性能就比较差。
3 LinkedList
- LinkedList的底层维护的是一个双向链表,检索指定位置的元素时必须从头开始访问或从尾部开始遍历(会先判断离头近还是离尾巴近, get(index)方法实际调用了下面这个方法
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
- 双向链表在添加和插入元素的时候特别方便,只要维护前后节点就好了。所以LinkedList的添加和插入性能好。
4 Vector
Verctor 就是一个线程安全的ArrayList, 每个接口都使用了synchronized关键字修饰。
5 ListIterator
ListIterator是一个为List定制的接口,继承自Iterator。ListIterator 额外定义了hasPrevious()和previous()方法,所以可以从后往前迭代。
6 总结
- ArrayList, LinkedList 和 Vector 都实现了List接口
- Vector通过synchronized关键字修饰方法,是线程安全的。ArrayList和LinkedList不是线程安全的。
- ArrayList在通过索引访问get(index)和修改set(index, e)时性能比LinkedList要好,在执行需要改变数组结构的操作比如插入,删除和容量不足时的添加操作时性能比LinkedList要差。