Java性能调优之ArrayList与LinkedList

我们知道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");
    }

Java性能调优之ArrayList与LinkedList

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

        在队头插入: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");
    }

        Java性能调优之ArrayList与LinkedList

        我们可以发现:

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

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

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

上一篇:C基础——文件I/O(2)


下一篇:2021-06-15