Java面試崗常見問題之ArrayList和LinkedList的區(qū)別

更新時間：2022年01月23日 14:53:35 作者：執(zhí)?梗

ArrayList和LinkedList作為我們Java中最常使用的集合類，很多人在被問到他們的區(qū)別時，憋了半天僅僅冒出一句：一個是數(shù)組一個是鏈表。這樣回答簡直讓面試官吐血。為了讓兄弟們打好基礎(chǔ)，我們通過實際的使用測試，好好說一下ArrayList和LinkedList的區(qū)別這道經(jīng)典的面試題

1.ArrayList和LinkedList是什么？

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

Arraylist：

LinkedList：

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

2.ArrayList和LinkedList性能比較

1.插入效率比較

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

//插入到頭部
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
    }

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

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

2.查詢效率比較

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

 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
    }

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

3.刪除效率比較

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

從尾部刪除：

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
    }

大家發(fā)現(xiàn)了嗎，從尾部刪除的時候，ArrayList的速度比LinkedList快，而從頭部刪除后，ArrayList就不知道被LinkedList甩了幾條街去了。其實刪除同插入其實是一樣的，再次實踐一次是想讓大家加深印象，能走出誤區(qū)。

4.實驗總結(jié)

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

1.在數(shù)據(jù)量不大時，ArrayList和LinkedList的查詢效率其實所差無幾，只有在數(shù)據(jù)量較大時，ArrayList會對比出優(yōu)勢

2.在插入和刪除上，LinkedList并不一定ArrayList效率更好，這與數(shù)據(jù)量以及插入和刪除的位置都是有關(guān)系的

3.面試標準回答

1.ArrayList底層為數(shù)組實現(xiàn)，LinkedList底層為雙向鏈表實現(xiàn)。ArrayList只能作為列表使用，LinkedList還能作為隊列，因為實現(xiàn)了Deque接口。

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

3. 在插入和刪除效率上，理論上LinkedList優(yōu)于ArrayList，但這還與數(shù)據(jù)量與處理的位置有關(guān)系，但查詢的效率上ArrayList更占有優(yōu)勢

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

到此這篇關(guān)于Java面試崗常見問題之ArrayList和LinkedList的區(qū)別的文章就介紹到這了,更多相關(guān)Java ArrayList和LinkedList的區(qū)別內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: