Java性能调优之ArrayList与LinkedList

2022-12-02 16:54:27

我们知道ArrayList与LinkedList相比，在插入删除元素方面，LinkedList比ArrayList要快，但真的是这样吗？

在我们对ArrayList与LinkedList进行遍历的时候用for循环好，还是迭代器好？

一、ArrayList

ArrayList的底层是数据，查询时可以通过下标快速的找到对应的元素。

进行插入操作时，如果是在队尾，则直接插入；在队中则需要先复制队中到队尾的元素，再插入元素；在对头则需要先复制对头到队尾的元素，再插入元素。

进行删除操作时，如果是在队尾，则直接删除；在队中则需要先删除元素，再复制队中到队尾的元素；在对头则需要先删除元素，再复制对头到队尾的元素。

二、LinkedList

LinkedList在jdk1.7之前是双向循环链表，在jdk1.7以后改成了双向非循环链表。

这样做有几个好处：

1.LinkedList是通过headerEntry实现的一个循环链表的。先初始化一个空的Entry，用来做header，然后首尾相连，形成一个循环链表。因此非循环链表能够少new一个Entry，减少为空校验，提高效率；

2.引入了first和last，有了更清晰的队头和队尾的概念；

3.循环链表在队头或队尾增删元素的时候需要维护两头的指针，而非循环链表只需要处理一头的first.previous/last.next就行，效率更高。

在查询时，LinkedList需要从头遍历到所需的元素；

在进行插入和删除操作时，如果是在队头或者队尾，可以直接操作元素进行删除；如果是在队中，则需要从头遍历到对应的元素，再进行操作。（离队头近，从队头开始遍历；离队尾近，从队尾开始遍历。）

三、ArrayList与LinkedList的比较

1.插入与删除比较

private static void addTailArray(int length){
        ArrayList<Integer> arrayList = new ArrayList<>(length);
        long startArrayTime = System.currentTimeMillis();
        for (int i = 0; i < length; i++) {
            arrayList.add(i);
        }
        long endArrayTime = System.currentTimeMillis();
        System.out.println("arrayList队尾插入元素程序运行时间：" + (endArrayTime - startArrayTime) + "ms");
    }

    private static void addHeadArray(int length){
        ArrayList<Integer> arrayList = new ArrayList<>(length);
        long startArrayTime = System.currentTimeMillis();
        for (int i = 0; i < length; i++) {
            arrayList.add(0,i);
        }
        long endArrayTime = System.currentTimeMillis();
        System.out.println("arrayList队头插入元素程序运行时间：" + (endArrayTime - startArrayTime) + "ms");
    }

    private static void addMiddleArray(int length){
        ArrayList<Integer> arrayList = new ArrayList<>(length);
        long startArrayTime = System.currentTimeMillis();
        for (int i = 0; i < length; i++) {
            arrayList.add(i / 2,i);
        }
        long endArrayTime = System.currentTimeMillis();
        System.out.println("arrayList队中插入元素程序运行时间：" + (endArrayTime - startArrayTime) + "ms");
    }

    private static void addTailLinded(int length){
        LinkedList<Integer> linkedList = new LinkedList<>();
        long startLinkedTime = System.currentTimeMillis();
        for (int i = 0; i < length; i++) {
            linkedList.add(i);
        }
        long endLinkedTime = System.currentTimeMillis();
        System.out.println("linkedList队尾插入元素程序运行时间：" + (endLinkedTime - startLinkedTime) + "ms");
    }

    private static void addHeadLinded(int length){
        LinkedList<Integer> linkedList = new LinkedList<>();
        long startLinkedTime = System.currentTimeMillis();
        for (int i = 0; i < length; i++) {
            linkedList.addFirst(i);
        }
        long endLinkedTime = System.currentTimeMillis();
        System.out.println("linkedList队头插入元素程序运行时间：" + (endLinkedTime - startLinkedTime) + "ms");
    }

    private static void addMiddleLinded(int length){
        LinkedList<Integer> linkedList = new LinkedList<>();
        long startLinkedTime = System.currentTimeMillis();
        for (int i = 0; i < length; i++) {
            linkedList.add(i / 2,i);
        }
        long endLinkedTime = System.currentTimeMillis();
        System.out.println("linkedList队中插入元素程序运行时间：" + (endLinkedTime - startLinkedTime) + "ms");
    }

我们可以发现，在插入方面的运行时间：

在队头插入：ArrayList大于LinkedList；

在队中插入：ArrayList小于LinkedList；

在队尾插入：ArrayList小于LinkedList。

队头是因为ArrayList比LinkedList多了一步复制元素，影响效率；队中是因为LinkedList每回都要从头遍历元素，比ArrayList的复制元素更影响效率；队尾是因为LinkedList比ArrayList多了一步new对象以及变换指针，所以效率慢一些。

大家可以发现，我在new ArrayList的时候初始化了大小。如果没有初始化大小，就会发生扩容，每回扩容都会复制元素，影响效率。但是随着队列的长度越来越大，以上的结果是不变的。因为ArrayList扩容为当前容量的一点五倍，而随着不断的扩容，ArrayList越来越大发生扩容的频率会变低。

删除的结果以及逻辑是一样的。

2.遍历比较

public static void main(String[] args) {
        int length = 100000;
        ArrayList<Integer> arrayList = new ArrayList<>(length);
        for (int i = 0; i < length; i++) {
            arrayList.add(i);
        }
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < length; i++) {
            linkedList.add(i);
        }

        long startArrayTime = System.currentTimeMillis();
        for (int i = 0; i < length; i++) {
            arrayList.get(i);
        }
        long endArrayTime = System.currentTimeMillis();
        System.out.println("arrayList的for循环运行时间：" + (endArrayTime - startArrayTime) + "ms");

        long startLinkedTime = System.currentTimeMillis();
        for (int i = 0; i < length; i++) {
            linkedList.get(i);
        }
        long endLinkedTime = System.currentTimeMillis();
        System.out.println("linkedList的for循环运行时间：" + (endLinkedTime - startLinkedTime) + "ms");

        Iterator<Integer> arrayIterator= arrayList.iterator();
        Iterator<Integer> linkedIterator = linkedList.iterator();

        long startArrayIteratorTime = System.currentTimeMillis();
        while (arrayIterator.hasNext()){
            arrayIterator.next();
        }
        long endArrayIteratorTime = System.currentTimeMillis();
        System.out.println("arrayList的for循环运行时间：" + (endArrayIteratorTime - startArrayIteratorTime) + "ms");

        long startLinkedIteratorTime = System.currentTimeMillis();
        while (linkedIterator.hasNext()){
            linkedIterator.next();
        }
        long endLinkedIteratorTime = System.currentTimeMillis();
        System.out.println("linkedList的for循环运行时间：" + (endLinkedIteratorTime - startLinkedIteratorTime) + "ms");
    }

我们可以发现：

ArrayList的for循环效率要远高于ListedList；

ArrayList的迭代器运行时间跟ListedList几乎一样。

所以ListedList最好用迭代器遍历，for循环每回都会从头开始遍历。

码农公寓

相关文章