0%

Java集合框架 —— ArrayList 和 LinkedList 的区别

声明:本文使用JDK1.8

先看下List在Collection中的框架图:

ArrayList源码分析

大家基本都知道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
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
61
62
63
64
65
66
67
68
69
70
71
private static final int DEFAULT_CAPACITY = 10;//初始容量为10
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//ArrayList扩容函数方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// 计算当前ArrayList大小
int oldCapacity = elementData.length;
//这里我们可以看出,ArrayList每次扩容是增加50%,oldCapacity >> 1是指往左移一位,也就是除以2
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);
}
//根据下标index获取元素值
public E get(int index) {
rangeCheck(index);//检查小标是否越界
return elementData(index);
}
//将index位置的值设为element,并返回原来的值
public E set(int index, E element) {
rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
//向数组中末尾增加一个元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//向指定位置index处增加element
public void add(int index, E element) {
rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!
//将index以及index之后的数据复制到index+1的位置往后,即从index开始向后挪了一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//根据指定的index,删除元素
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; // clear to let GC do its work

return oldValue;
}

LinkedList源码分析

来看下LinkedList的部分源码,底层是基于双向链表的数据结构。
定义:

1
2
3
4
5
6
package java.util;public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
}

方法:

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
Node<E> node(int index) {
// assert isElementIndex(index);

if (index < (size >> 1)) {//如果index<(size/2),则从前找
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;
}
}
//直接删除某个元素
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//根据下标查询某个元素
public E get(int index) {
checkElementIndex(index);//检查下标是否越界
return node(index).item;//可以看第一个node的方法,其中有查询
}
//设置index位置处的值为element
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
//在下标index位置处新增element
public void add(int index, E element) {
checkPositionIndex(index);

if (index == size)//index是末尾,则在末尾新增一个
linkLast(element);
else //这里的插入需要先去查询相应的位置,这会导致性能降低
linkBefore(element, node(index));
}

ArrayList和LinkedList区别

平时在看博客的时候,网上很多博客都说,ArrayList基于数组的数据机构,LinkedList是基于链表的数据结构,所以有以下几种特性:
1、对于随机查询,ArrayList比LinkedList快
2、对于插入或者删除,LinkedList由于是链表,所以是比ArrayList性能更好。
通过两者的源码比较,我们发现对于随机查找,ArrayList直接根据下标index查询相对于的值,而LinkedList虽然源码对其做了部分优化,index小于(size/2),从前往后找,否则从后往前找,即使这样,还是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
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
public static void main(String[] args) {
List<Integer> array = new ArrayList<>();
LinkedList<Integer> linked = new LinkedList<>();
//首先分别给两者插入10000条数据
for (int i = 0; i < 100000; i++) {
array.add(i);
linked.add(i);
}
//获得两者随机访问的时间
System.out.println("array get cost time:" + getTime(array));
System.out.println("linked get cost time:" + getTime(linked));

//获得在中间插入数据的时间
System.out.println("array insert in first cost time:" + insertArrayListAtFirstTime(array));
System.out.println("linked insert cost in first time:" + insertLinkedListAtFirstTime(linked));

//获得在中间插入数据的时间
System.out.println("array insert in middle cost time:" + insertInMiddleTime(array));
System.out.println("linked insert cost in middle time:" + insertInMiddleTime(linked));

//获得尾部插入数据的时间
System.out.println("array insert at last cost time:" + insertAtLastTime(array));
System.out.println("linked insert cost at last time:" + insertAtLastTime(linked));
}

//头插
public static long insertArrayListAtFirstTime(List<Integer> list) {
int num = 100000;
long time = System.currentTimeMillis();
for (int i = 1; i < num; i++) {
list.add(0, i);
}
return System.currentTimeMillis() - time;
}

//头插
public static long insertLinkedListAtFirstTime(LinkedList<Integer> list) {
int num = 100000;
long time = System.currentTimeMillis();
for (int i = 1; i < num; i++) {
list.addFirst(i);
}
return System.currentTimeMillis() - time;
}

//中间插入数据
public static long insertInMiddleTime(List<Integer> list) {
int num = 10000000; //表示要插入的数据量
long time = System.currentTimeMillis();
for (int i = 1; i < num; i++) {
list.add(list.size() >> 1, i);
}
return System.currentTimeMillis() - time;
}

//尾插
public static long insertAtLastTime(List<Integer> list) {
int num = 1000000; //表示要插入的数据量
long time = System.currentTimeMillis();
for (int i = 1; i < num; i++) {
list.add(i);
}
return System.currentTimeMillis() - time;
}

public static long getTime(List<Integer> list) {
long time = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
int index = Collections.binarySearch(list, list.get(i));
if (index != i) {
System.out.println("ERROR!");
}
}
return System.currentTimeMillis() - time;
}

这个是运行时间:

1
2
3
4
5
6
7
8
9
10
11
array get cost time:6
linked get cost time:4170

array insert in first cost time:2927
linked insert cost in first time:4

array insert in middle cost time:1887
linked insert cost in middle time:124

array insert at last cost time:23
linked insert cost at last time:92

这里我们可以看出,对于大数据的随机查询,ArrayList比较快。对于插入,需要区分头插、中间插入和尾插的区别:

  • 头插:ArrayList 需要做大量的位移和复制操作,而LinkedList的优势就体现出来了,耗时只是实例化一个对象,相对来说,LinkedList 在大量插入的情况下,相对较快。
  • 中间插入:ArrayList 中间插入,首先我们知道他的定位时间复杂度是O(1),比较耗时的点在于数据迁移和容量不足的时候扩容。LinkedList 中间插入,链表的数据实际插入时候并不会怎么耗时,但是它定位的元素的时间复杂度是O(n),所以这部分以及元素的实例化比较耗时。
  • 尾插:ArrayList 不需要做位移拷贝也就不那么耗时了,而 LinkedList 则需要创建大量的对象。所以这里ArrayList尾插的效果更好一些。

不过我们从源码比较知道LinkedList性能比较差的原因是因为在中间插入的时候,性能耗在了查询相应的位置上面了,如果只是直接在首插入的话,性能还是ArrayList快。

Reference

客官,赏一杯coffee嘛~~~~