Java面試崗常見問題之ArrayList和LinkedList的區別

Posted on by

1.ArrayList和LinkedList是什麼？

在我看來，要想搞清楚ArrayList和LinkedList有什麼區別，首先一定得要知道這兩個東西到底是什麼。因為在我看來，通常拿來被比較有區別的東西，它們大體上一定存在很多相似的地方。為瞭剖析本質，我們直接看看它們的源碼聲明。

 Arraylist：

 LinkedList：

可以看出ArrayList和LinkedList都是List接口下的實現類，而List接口可以說是集合類中最常用的接口瞭，它是一個元素有序、可以重復、可以為null的集合。而且List接口的元素，都可以直接通過下標索引獲取。既然如此，那麼說明ArrayList和LinkedList都具有上述的功能，那他們使用起來的效率到底有什麼區別呢？

2.ArrayList和LinkedList性能比較               

1.插入效率比較

因為上面我們已經提到過這兩者都是主要用來存儲元素的集合類，那我們可以使用較大的數據量，來測試一下它們插入的效率如何      

//插入到頭部
public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
 
        long time1 = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list1.add(0,i);
        }
        long time2 = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list2.add(0,i);
        }
        long time3 = System.currentTimeMillis();
        //ArrayList的插入時間
        System.out.println(time2-time1);//58746
        //LinkedList的插入時間
        System.out.println(time3-time2);//124
    }
     //插入到尾部
     public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
 
        long time1 = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list1.add(i);
        }
        long time2 = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list2.add(i);
        }
        long time3 = System.currentTimeMillis();
        //ArrayList的插入時間
        System.out.println(time2-time1);//23
        //LinkedList的插入時間
        System.out.println(time3-time2);//140
    }

大傢發現沒有，當插入100萬個元素到頭部時，LinkedList的速率竟然是ArrayList五千倍之多，當我們插入100萬個元素到尾部時，但是又發現ArrayList的速率比LinkedList還快，這是為什麼呢？

其實做這個實驗，是為瞭打消許多人的誤區——LinkedList的插入效率一定比ArrayList要高。沒錯，理論上確實是如此，因為Arraylist的底層是數組實現，而LinkedList的底層為雙向鏈表。在初學數據結構時鏈表的插入效率高於數組這是我們就學習過的知識，可實際上在這裡其實當數據量越來越大時，ArrayList的插入和刪除效率是比LinkedList越來越高的，這涉及到數組和鏈表在元素操作上的問題。但其實在元素量較少時，兩者的效率幾乎所差無幾。        

2.查詢效率比較

我們向ArrayList和LinkedList同時插入10萬條數據，然後去索引每個下標，測試一下兩者的查詢效率如何        

 public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
        //先放入一百萬個元素
        for (int i = 0; i < 100000; i++) {
            list1.add(i);
            list2.add(i);
        }
        long time1 = System.currentTimeMillis();
        for (int i = 0; i <list1.size() ; i++) {
            list1.get(i);
        }
        long time2 = System.currentTimeMillis();
        for (int i = 0; i <list2.size() ; i++) {
            list2.get(i);
        }
        long time3 = System.currentTimeMillis();
        System.out.println(time2-time1);//1
        System.out.println(time3-time2);//5479
    }

從測試的結果來看，並沒有出乎我們的意外，因為ArrayList的底層為數組實現，對於任何一個下標的索引都是O(1)的時間復雜度。而LinkedList的底層為雙向鏈表，對於查詢索引需要從頭部或者尾部去遍歷找到下標。   

3.刪除效率比較

我們同樣向ArrayList和LinkedList放入100萬個元素，然後同樣測試從頭部刪除和從尾部刪除有什麼區別，來測試一下他們的刪除效率。

從尾部刪除：

public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
        //先放入一百萬個元素
        for (int i = 0; i < 1000000; i++) {
            list1.add(i);
            list2.add(i);
        }
        long time1 = System.currentTimeMillis();
        for (int i = 1000000; i >0 ; i--){
            list1.remove(i-1);
        }
        long time2 = System.currentTimeMillis();
        for (int i = 1000000; i >0 ; i--) {
            list2.remove(i-1);
        }
        long time3 = System.currentTimeMillis();
        //ArrayList的刪除時間
        System.out.println(time2-time1);//8
        //LinkedList的刪除時間
        System.out.println(time3-time2);//18
    }

從頭部刪除：

public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
        //先放入一百萬個元素
        for (int i = 0; i < 1000000; i++) {
            list1.add(i);
            list2.add(i);
        }
        long time1 = System.currentTimeMillis();
        for (int i = 1000000; i >0 ; i--){
            list1.remove(0);
        }
        long time2 = System.currentTimeMillis();
        for (int i = 1000000; i >0 ; i--) {
            list2.remove(0);
        }
        long time3 = System.currentTimeMillis();
        System.out.println(time2-time1);//55962
        System.out.println(time3-time2);//14
    }

       大傢發現瞭嗎，從尾部刪除的時候，ArrayList的速度比LinkedList快，而從頭部刪除後，ArrayList就不知道被LinkedList甩瞭幾條街去瞭。其實刪除同插入其實是一樣的，再次實踐一次是想讓大傢加深印象，能走出誤區。

4.實驗總結

       之所以會做這幾個實驗，不僅僅是為瞭讓大傢更加深刻的去認識ArrayList和LinkedList，也是想讓大傢走出一些誤區，比如什麼LinkedList插入刪除一定比ArrayList快啊，ArrayList查詢一定比LinkedList快啊，從理論上來說確實如此，但通過實驗以後，我們應該這樣表達：

       1.在數據量不大時，ArrayList和LinkedList的查詢效率其實所差無幾，隻有在數據量較大時，ArrayList會對比出優勢

       2.在插入和刪除上，LinkedList並不一定ArrayList效率更好，這與數據量以及插入和刪除的位置都是有關系的        

3.面試標準回答

       1.ArrayList底層為數組實現，LinkedList底層為雙向鏈表實現。ArrayList隻能作為列表使用，LinkedList還能作為隊列，因為實現瞭Deque接口。

       2.LinkedList在數組中的開銷更大，因為它不僅需要存儲元素，還需要保存前後結點的地址，而ArrayList更加輕量級。

       3. 在插入和刪除效率上，理論上LinkedList優於ArrayList，但這還與數據量與處理的位置有關系，但查詢的效率上ArrayList更占有優勢   

如果兄弟們在實際使用時實在糾結用哪個，那就無腦使用Arraylist吧，別問，問就是它更好用！      

到此這篇關於Java面試崗常見問題之ArrayList和LinkedList的區別的文章就介紹到這瞭,更多相關Java ArrayList和LinkedList的區別內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：