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

Posted on Edited on In Views:

声明：本文使用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
72
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