Fork me on GitHub

ArrayList、LinkedList和Vector分析

前言

List家族常用的类有3个,ArrayList、LinkedList、Vector。

ArrayList和Vector的底层是基于数组实现的,LinkedList的底层是基于链表实现的。

三者的比较如下:

  1. ArrayList和LinkedList不是线程安全的,Vector是线程安全的。
  2. 对于随机访问(get和set),ArrayList的性能要优于LinkedList。
  3. 对于add和remove操作,LinkedList和ArrayList性能差距不是很大。
  4. 三者均实现了Collection接口。

分析

UML图

三者与其他类的继承实现关系UML图如下。

ArrayList:

upload successful

LinkedList:

upload successful

Vector:

upload successful

源码分析

核心实现

ArrayList是基于数组实现。

1
2
transient Object[] elementData;
private int size;

LinkedList是基于链表实现。

1
2
3
transient int size = 0;
transient Node<E> first;
transient Node<E> last;

Vector是基于数组实现。

1
2
3
protected Object[] elementData;
protected int elementCount;
protected int capacityIncrement;

核心参数

ArrayList 可以设置初始大小(由于数组实现的原因),不设置默认为10。

LinkedList不需要设置参数(由于使用链表实现,无界)。

Vector不仅可以设置初始大小,还可以设置容量增幅。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//ArrayList传参构造函数
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);
}
}
//LinkedList构造函数
public LinkedList() {
}
//Vector传参构造函数
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}

关于初始化大小和扩容机制下面讲。

核心方法

我们主要分析get、set、add、remove这几个方法。对于ArrayList和Vector,还要分析扩容方法。

get、set方法

ArrayList get,set方法:

1
2
3
4
5
6
7
8
9
10
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

Vector get,set方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);

return elementData(index);
}
public synchronized E set(int index, E element) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);

E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

二者的逻辑一样,get方法判断是否下标越界,不越界返回index下的数值。set方法判断是否越界,不越界将新值放到指定下标上。它俩的区别在与synchronized关键字,正好说明了Vector是线程安全的。

LinkedList get,set方法:

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 get(int index) {
checkElementIndex(index);
return node(index).item;
}
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
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的get方法会先检查是否越界,不越界返回指定下标node的item值。
set方法也是先检查越界情况,不越界将该点的node的item赋为新值。取node指定位置上的值时要循环遍历,所以对于随机的get,set,ArrayList的性能要优于LinkedList的。

add、remove方法

ArrayList add、remove方法:

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
34
35
36
37
38
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
public E remove(int index) {
Objects.checkIndex(index, size);

modCount++;
E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work

return oldValue;
}

Vector add、remove方法:

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
public synchronized boolean add(E e) {
modCount++;
add(e, elementData, elementCount);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
elementCount = s + 1;
}
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);

int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // Let gc do its work

return oldValue;
}

它们里面有add、remove方法不止一个,我们只拿一个来举例。

可以看到,Vector和ArrayList十分相近了,除了synchronized关键字。

add方法当elementData.length和elementCount相等时(容量满),会执行扩容操作,并将元素放到指定位置。

remove方法先判断下标是否越界,不越界会删除指定位置的元素,并且将数组重新拷贝合并。

同时它们有一个计数器modCount,在HashMap那边已经讲过,是用来fast-fail的,当多个线程同时操作,modCount不一致,就会抛出异常。

LinkedList的add、remove方法:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public void add(int index, E element) {
checkPositionIndex(index);

if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
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++;
}
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++;
}
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;
}

可以看到,LinkedList的add方法开始也会校验指针位置,然后如果在末尾,就在链表最后面添加节点,否则就插入到链表指定位置上。

remove方法校验指针位置后,会删除指定位置上的node。

上面可以看到,对于add和remove,ArrayList数组要进行扩容或者删除部分长度,执行Sysetm.arraycopy方法,这是要消耗一些性能的,对于LinkedList,不需要维护容量问题,但是每次新增或者删除时,都会创建或删除一个Node对象,也是要消耗一些性能的。

扩容方法

对于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
private static final int DEFAULT_CAPACITY = 10;
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}

Vector扩容方法:

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
public Vector() {
this(10);
}
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity <= 0) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}

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,如果不传入初始容量,默认为10。容量达到最值,执行扩容,每次扩容 int newCapacity = oldCapacity + (oldCapacity >> 1);

默认原容量的1.5倍。

Vector,如果不传入初始容量和自增容量,默认初始容量也为10.扩容时执行
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);

默认为原容量的2倍。

两者的最大值容量均为Integer.MAX_VALUE.

LinkedList由于是链表实现,没有容量限制。无需扩容。

代码

我们从代码的角度比较下ArrayList和LinkedList,Vector。

我们构建一个有200W数据的ArrayList和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 static void main(String[] args){
List<Integer> list = new ArrayList();
//List<Integer> list = new LinkedList<Integer>();
//Vector<Integer> list=new Vector<>();
for (int i = 0; i < 2000000; i++) {
list.add(i);
}

Integer tmp;
long start=System.currentTimeMillis() ; //ForEach
for(Integer s:list){
tmp=s;
}
System.out.println("foreach spend:"+(System.currentTimeMillis()-start));
start = System.currentTimeMillis();
for(Iterator<Integer> it = list.iterator(); it.hasNext();){
tmp=it.next();
}
System.out.println("Iterator spend;"+(System.currentTimeMillis()-start));
start=System.currentTimeMillis();
int size=list.size();
for(int i=0;i<size;i++){
tmp=list.get(i);
}
System.out.println("for spend;"+(System.currentTimeMillis()-start));
}

某一次的结果:

数组forEach遍历Iterator遍历for遍历
ArrayList9ms9ms12ms
LinkedList17ms16ms???
Vector44ms55ms41ms

由于for循环遍历是随机访问,故LinkedList在数据量很大的情况下时间消耗会很长,基本不能接受。由于Vector线程安全,synchronized,故其整体效率会比ArrayList低些。在实际开发中,应用的ArrayList还是比较多的。

结语

以上就是对ArrayList、LinkedList、Vector的全部分析。对于不同的应用场景,合理的选择List的类型也是至关重要的。三种List都是比较基础的知识,应当学习和掌握。




-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

SakuraTears wechat
扫一扫关注我的公众号
您的支持就是我创作的动力!
0%