ArrayList 和 LinkedList的執行效率比較

一、概念:

    一般我們都知道ArrayList＊ 由一個數組後推得到的 List。作為一個常規用途的對象容器使用，用於替換原先的 Vector。允許我們快速訪問元素，但在從列表中部插入和刪除元素時，速度卻嫌稍慢。一般只應該用ListIterator 對一個 ArrayList 進行向前和向後遍歷，不要用它刪除和插入元素；與 LinkedList 相比，它的效率要低許多LinkedList 提供優化的順序訪問性能，同時可以高效率地在列表中部進行插入和刪除操作。但在進行隨機訪問時，速度卻相當慢，此時應換用 ArrayList。

二、測試

    本來自己寫了一些測試類想測試下ArrayList和LinkedList的性能比較，發現怎麼寫都差強人意，今天在《Thinking in Java》中看到了這樣的一段代碼，個人覺得寫得不賴。

public class ListPerformance
{
    private static final int REPS = 100;

    private abstract static class Tester//內部抽象類，作為List測試。
    {
        String name;
        int size;

        Tester(String name, int size)
        {
            this.name = name;
            this.size = size;
        }

        abstract void test(List a);
    }

    private static Tester[] tests = {new Tester("get", 300)//一個測試數組，存儲get(隨機取)、iteration(順序遍歷)、insert(中間插入)、remove(隨機刪除)
    {
        void test(List a)
        {
            for (int i = 0; i < REPS; i++) {
                for (int j = 0; j < a.size(); j++) {
                    a.get(j);
                }
            }
        }
    }, new Tester("iteration", 300)
    {
        void test(List a)
        {
            for (int i = 0; i < REPS; i++) {
                Iterator it = a.iterator();
                while (it.hasNext()) it.next();
            }
        }
    }, new Tester("insert", 1000)
    {
        void test(List a)
        {
            int half = a.size() / 2;
            String s = "test";
            ListIterator it = a.listIterator(half);
            for (int i = 0; i < size * 10; i++) {
                it.add(s);
            }
        }
    }, new Tester("remove", 5000)
    {
        void test(List a)
        {
            ListIterator it = a.listIterator(3);
            while (it.hasNext()) {
                it.next();
                it.remove();
            }
        }
    },
                                     };

    public static void test(List a)
    {
        System.out.println("Testing " + a.getClass().getName());//輸出測試的類名稱
        for (int i = 0; i < tests.length; i++) {
            fill(a, tests[i].size);//填充空集合
            System.out.print(tests[i].name);
            long t1 = System.currentTimeMillis();
            tests[i].test(a);//進行測試
            long t2 = System.currentTimeMillis();
            System.out.print(":" + (t2 - t1)+" ms ");
        }
    }

    public static Collection fill(Collection c, int size)
    {
        for (int i = 0; i < size; i++) {
            c.add(Integer.toString(i));
        }
        return c;
    }

    public static void main(String[] args)
    {
        test(new ArrayList());
        System.out.println();
        test(new LinkedList());
    }

}

三、總結

    首先，真的誇一下，這段代碼寫得真是好啊，無論是內部類的應用還是對面向對象的認識，都考慮的恰到好處，哎，我什麼時候才能寫出這麼棒的代碼啊。

    測試結果每次都有些許的差異，但不難得出以下的結論：

        1、在 ArrayList 中進行隨機訪問（即 get()）以及迴圈反覆是最划得來的 。原因在於，ArrayList是基於數組而來的，所以每個元素都有其對應的index，所以隨機定位一個元素要快捷的多。

        2、在 LinkedList 中進行順序訪問、插入、刪除動作的話還是比較高效的。原因在於，插入、刪除的話對於LinkedList來說只需要改變其排列的一個node結點就可以了，而對於ArrayList來說刪除一個元素，需要不斷把後面的元素移到前面的位置上。

        3、至於順序訪問，之前一直認為ArrayList 基於數組排列，在記憶體中是連續排列的，應該會快得多，然後多次測試發現並不是想象的那樣，或者說ArrayList沒有表現出它該有的優勢，甚至還不如LinkedList的訪問速度。原因在於:LinkedList 提供了優化的順序訪問性能。