快捷導(dǎo)航

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

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

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

1.ArrayList和LinkedList是什么？

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

Arraylist：

LinkedList：

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

2.ArrayList和LinkedList性能比較

1.插入效率比較

因?yàn)樯厦嫖覀円呀?jīng)提到過這兩者都是主要用來存儲(chǔ)元素的集合類，那我們可以使用較大的數(shù)據(jù)量，來測(cè)試一下它們插入的效率如何

//插入到頭部
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的插入時(shí)間
        System.out.println(time2-time1);//58746
        //LinkedList的插入時(shí)間
        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的插入時(shí)間
        System.out.println(time2-time1);//23
        //LinkedList的插入時(shí)間
        System.out.println(time3-time2);//140
    }

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

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

2.查詢效率比較

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

 public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
        //先放入一百萬個(gè)元素
        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
    }

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

3.刪除效率比較

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

從尾部刪除：

public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
        //先放入一百萬個(gè)元素
        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的刪除時(shí)間
        System.out.println(time2-time1);//8
        //LinkedList的刪除時(shí)間
        System.out.println(time3-time2);//18
    }

從頭部刪除：

public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
        //先放入一百萬個(gè)元素
        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)了嗎，從尾部刪除的時(shí)候，ArrayList的速度比LinkedList快，而從頭部刪除后，ArrayList就不知道被LinkedList甩了幾條街去了。其實(shí)刪除同插入其實(shí)是一樣的，再次實(shí)踐一次是想讓大家加深印象，能走出誤區(qū)。

4.實(shí)驗(yàn)總結(jié)

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

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

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

3.面試標(biāo)準(zhǔn)回答

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

2.LinkedList在數(shù)組中的開銷更大，因?yàn)樗粌H需要存儲(chǔ)元素，還需要保存前后結(jié)點(diǎn)的地址，而ArrayList更加輕量級(jí)。

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

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

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

您可能感興趣的文章: