java数据结构之List

List是java中重要的数据结构之一,这里介绍常用的3种实现方式:ArrayList、Vector、LinkedList。
类图如下:

可以看到,ArrayList、Vector、LinkedList都是AbstractList的实现。而AbstractList实现了List接口,并扩展自AbstractCollection。

其中,ArrayList和Vector底层使用了数组,LinkedList使用的是循环双向链表。这是2种完全不同的实现,所有这也决定了它们的适应的工作场景不同。

ArrayList和Vector的区别是对多线程的支持,ArrayList没有对任何一个方法做同步,因此不是线程安全的。而Vector中绝大多数方法都做了线程同步。所以在多线程环境中,建议使用Vector,反之则使用ArrayList。

ArrayList和Vector实现除了同步几乎一样,所以下面以ArrayList进行说明。

添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public boolean add(E e) {
// 确保内部数组有足够的空间
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将元素添加到数组的末尾
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 新的数组容量是原来数组的1.5倍
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先确保数组空间够用,否则会对数组进行扩容。新数组的长度是原数组的1.5倍。

通过代码可以知道,如果ArrayList内部数组的空间足够大,那么添加元素是很快的。在数组的容量不够时,会进行扩容,在扩容的过程中,会进行大量的数组的复制操作。

LinkedList的add操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}

将新的元素放到最后。并设置添加前的最后一个元素的下一个元素是要添加的元素。
可以看到,LinkedList不用担心容量的问题,添加的效率也是很高的,只是每次添加时会生成一个新的Node对象,会有一定的性能损耗。在ArrayList容量足够的情况下,ArrayList的速度是非常快的,是直接操作的数组。

添加操作性能测试

1.ArrayList的添加操作

1
2
3
4
5
long s = System.currentTimeMillis();
for (int i=0;i<5000000;i++) {
list.add(i);
}
System.out.println(System.currentTimeMillis() - s);

耗时:161ms.

2.LinkedList的添加操作

1
2
3
4
5
long s = System.currentTimeMillis();
for (int i=0;i<5000000;i++) {
linkedList.add(i);
}
System.out.println(System.currentTimeMillis() - s);

耗时:3476ms.

如果列表容量足够(不用扩容),添加元素到尾部,推荐使用ArrayList,效率高于LinkedList。

添加元素到任意位置

1.ArrayList

1
2
3
4
5
6
7
8
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

可以看到,ArrayList添加元素到指定位置时,会导致index之后的所有元素向后移动,如果数据量大而index比较小的话,产生的数组拷贝是非常多的。这样必然导致效率降低。所以,尽量将元素插入到列表的尾部,可以提高该方法的性能。

2.LinkedList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
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;
}
}

如果index=size,就跟add(E e)是一样的,添加在最后;否则调用linkBefore方法。
在linkBefore方法中,注意第2个参数node(index),该方法中,如果index在LinkedList的前半部分就在前半部分查找;否则在后半部分查找。所以,可以看到,如果index在靠近中间的位置,效率比较低。

添加元素到任意位置测试

1.ArrayList

1
2
3
4
5
long s = System.currentTimeMillis();
for (int i=0;i<50000;i++) {
list.add(0,i);
}
System.out.println(System.currentTimeMillis() - s);

耗时:236ms。

2.LinkedList

1
2
3
4
5
long s = System.currentTimeMillis();
for (int i=0;i<50000;i++) {
linkedList.add(i);
}
System.out.println(System.currentTimeMillis() - s);

耗时:5ms。

除了一些极端的情况(首尾),添加元素到列表任意位置,LinkedList效率高于ArrayList。所以如果有在任意位置插入元素的需求,可以考虑LinkedList。

删除任意位置的元素

ArrayList

1
2
3
4
5
6
7
8
9
10
11
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}

可以看到,跟add(index,E e)方法比较类似,在任意位置删除元素后,都需要进行数组的重组。而且,要删除的元素越靠前,开销越小;要删除的元素越靠后,开销越大。

LinkedList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}

注意remove方法中,最后调用了unlink方法,该方法中也查找了index位置的元素。代码同add(index,E)。
如果元素在前半段,则在链表的前半段循环查找;否则在链表的后半段循环查找。所以如果要删除的元素在前半段或后半段还好,如果在中间位置效率就比较低了(需要循环一半的链表)。

容量参数

在前面添加元素的地方说了,ArrayList和Vector在容量不够的情况下会进行扩容,新的容量是原来的1.5倍,扩容后会对之前的数据重组,所以性能损耗是比较大的。
在ArrayList和Vector的构造器中,有一个初始容量参数可指定列表的容量,如果在构造列表时预估数据量,将会避免进行列表扩容,从而可以提升效率。

列表遍历

分别使用ArrayList和LinkedList进行for循环、forEach循环、迭代器进行100万条数据的遍历测试。
测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for (int i=0;i<1000000;i++) {
list.add(i);
}
long s = System.currentTimeMillis();
for (int i=0;i<list.size();i++) {
list.get(i);
}
System.out.println("for循环耗时:" + (System.currentTimeMillis() - s) + "ms.");
s = System.currentTimeMillis();
Integer tmp = null;
for (Integer i:list) {
tmp = i;
}
System.out.println("forEach耗时:"+(System.currentTimeMillis() - s) + "ms.");
s = System.currentTimeMillis();
for (Iterator<Integer> iterator = list.iterator();iterator.hasNext();) {
tmp = iterator.next();
}
System.out.println("迭代器耗时:" + (System.currentTimeMillis() - s) + "ms.");

ArrayList测试结果:
for循环耗时:4ms.
forEach耗时:17ms.
迭代器耗时:10ms.

LinkedList测试结果:
forEach耗时:11ms.
迭代器耗时:15ms.
for循环耗时:无穷大,没法等到执行结束。

注意:上面代码在测试时将for循环放到最后,否则测试LinkedList时,看不到forEach和迭代器的执行结果。

可以看到,对于ArrayList来说,for循环的效率是最高的,forEach反而最低。LinkedList使用for循环完全没法忍受,原因可以看之前的LinkedList查找元素的部分,每次循环都会遍历一次列表。
编译后的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
long var8 = System.currentTimeMillis();
Integer tmp = null;
Iterator i;
Integer i1;
for(i = list.iterator(); i.hasNext(); i1 = (Integer)i.next()) {
;
}
System.out.println("forEach耗时:" + (System.currentTimeMillis() - var8) + "ms.");
var8 = System.currentTimeMillis();
for(i = list.iterator(); i.hasNext(); tmp = (Integer)i.next()) {
;
}
System.out.println("迭代器耗时:" + (System.currentTimeMillis() - var8) + "ms.");
var8 = System.currentTimeMillis();
for(int var9 = 0; var9 < list.size(); ++var9) {
list.get(var9);
}
System.out.println("for循环耗时:" + (System.currentTimeMillis() - var8) + "ms.");

forEach在编译时被优化为使用迭代器,但是多了一个赋值操作,所以比使用迭代器慢一点。

总结

要根据应用场景选择合适的List,否则会导致性能问题。同时也要注意ArrayList和Vector的容量,使用前如果能评估大小,最好初始化List时就指定,这样可以避免数组扩容,导致大量的数据拷贝,导致性能下降。

参考:《java程序性能优化——让你的java程序更快、更稳定》

Donny wechat
欢迎关注我的个人公众号
打赏,是超越赞的一种表达。
Show comments from Gitment