数据结构:用实例分析ArrayList与LinkedList的读写性能

背景

ArrayList与LinkedList是Java编程中经常会用到的两种基本数据结构，在书本上一般会说明以下两个特点：

• 对于需要快速随机访问元素，应该使用ArrayList。
• 对于需要快速插入，删除元素，应该使用LinkedList。

该文通过实际的例子分析这两种数据的读写性能。

ArrayList

ArrayList是实现了基于动态数组的数据结构：

private static final int DEFAULT_CAPACITY = 10;
...
transient Object[] 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);
        }
    }

LinkedList

LinkedList是基于链表的数据结构。

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
...    
transient Node<E> first;
transient Node<E> last;
...
private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

实例分析

• 通过对两个数据结构分别增加、插入、遍历进行读写性能分析

1、增加数据

public class ArrayListAndLinkList {
    public final static int COUNT=100000;
    public static void main(String[] args) {

        // ArrayList插入
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Long start = System.currentTimeMillis();
        System.out.println("ArrayList插入开始时间：" + sdf.format(start));

        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(i);
        }

        Long end = System.currentTimeMillis();
        System.out.println("ArrayList插入结束时间：" + sdf.format(end));
        System.out.println("ArrayList插入" + (end - start) + "毫秒");


        // LinkedList插入
        start = System.currentTimeMillis();
        System.out.println("LinkedList插入开始时间：" + sdf.format(start));
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(i);
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList插入结束时间：" + sdf.format(end));
        System.out.println("LinkedList插入结束时间" + (end - start) + "毫秒");
     }
}

输出如下：
两者写入的性能相差不大！

2、插入数据

在原有增加的数据上，在index:100的位置上再插入10万条数据。

public class ArrayListAndLinkList {
    public final static int COUNT=100000;
    public static void main(String[] args) {

        // ArrayList插入
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Long start = System.currentTimeMillis();
        System.out.println("ArrayList插入开始时间：" + sdf.format(start));

        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(i);
        }
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(100,i);
        }

        Long end = System.currentTimeMillis();
        System.out.println("ArrayList插入结束时间：" + sdf.format(end));
        System.out.println("ArrayList插入" + (end - start) + "毫秒");


        // LinkedList插入
        start = System.currentTimeMillis();
        System.out.println("LinkedList插入开始时间：" + sdf.format(start));
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(i);
        }
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(100,i);
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList插入结束时间：" + sdf.format(end));
        System.out.println("LinkedList插入结束时间" + (end - start) + "毫秒");
     }
}

输出如下：
ArrayList的性能明显比LinkedList的性能差了很多。

看下原因：
ArrayList的插入源码：

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后续的数据上需要做逐一复制。

LinkedList的插入源码：

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++;
    }

LinkedList的插入原理：在原来相互链接的两个节点（Node）断开，把新的结点插入到这两个节点中间，根本不存在复制这个过程。

3、遍历数据

在增加和插入的基础上，利用get方法进行遍历。

public class ArrayListAndLinkList {
    public final static int COUNT=100000;
    public static void main(String[] args) {

        // ArrayList插入
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Long start = System.currentTimeMillis();
        System.out.println("ArrayList插入开始时间：" + sdf.format(start));

        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(i);
        }
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(100,i);
        }

        Long end = System.currentTimeMillis();
        System.out.println("ArrayList插入结束时间：" + sdf.format(end));
        System.out.println("ArrayList插入" + (end - start) + "毫秒");


        // LinkedList插入
        start = System.currentTimeMillis();
        System.out.println("LinkedList插入开始时间：" + sdf.format(start));
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(i);
        }
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(100,i);
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList插入结束时间：" + sdf.format(end));
        System.out.println("LinkedList插入结束时间" + (end - start) + "毫秒");

        // ArrayList遍历
        start = System.currentTimeMillis();
        System.out.println("ArrayList遍历开始时间：" + sdf.format(start));
        for (int i = 0; i < 2*COUNT; i++) {
            arrayList.get(i);
        }
        end = System.currentTimeMillis();
        System.out.println("ArrayList遍历开始时间：" + sdf.format(end));
        System.out.println("ArrayList遍历开始时间" + (end - start) + "毫秒");

        // LinkedList遍历
        start = System.currentTimeMillis();
        System.out.println("LinkedList遍历开始时间：" + sdf.format(start));
        for (int i = 0; i < 2*COUNT; i++) {
            linkedList.get(i);
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList遍历开始时间：" + sdf.format(end));
        System.out.println("LinkedList遍历开始时间" + (end - start) + "毫秒");

    }
}

输出如下：

两者的差异巨大：
我们看一下LInkedList的get方法：从头遍历或从尾部遍历结点

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
 ...
 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;
        }
    }

3.1、LinkedList遍历改进

我们采用迭代器对LinkedList的遍历进行改进：

...
		// LinkedList遍历
        start = System.currentTimeMillis();
        System.out.println("LinkedList遍历开始时间：" + sdf.format(start));
        Iterator<Integer> iterator = linkedList.iterator();
        while(iterator.hasNext()){
            iterator.next();
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList遍历开始时间：" + sdf.format(end));
        System.out.println("LinkedList遍历开始时间" + (end - start) + "毫秒");

再看下结果：
两者的遍历性能接近。

总结

• List使用首选ArrayList。对于个别插入删除非常多的可以使用LinkedList。
• LinkedList，遍历建议使用Iterator迭代器，尤其是数据量较大时LinkedList避免使用get遍历。