java面試基礎(chǔ) -- ArrayList 和 LinkedList有什么區(qū)別

這篇具有很好參考價值的文章主要介紹了java面試基礎(chǔ) -- ArrayList 和 LinkedList有什么區(qū)別。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

基本介紹

有什么不同??

ArrayList的擴容機制

ArrayLIst的基本使用

ArrayList和Vector

基本介紹

還記得我們的java集合框架嗎, 我們來復(fù)習一下, 如圖:

java面試基礎(chǔ) -- ArrayList 和 LinkedList有什么區(qū)別,java面試基礎(chǔ)篇,java,面試,開發(fā)語言

? ? ? ? ?可以看出來 ArrayList和LinkedList 都是具體類, 他們都是接口List的實現(xiàn)類.

但是他們底層的邏輯是不同的, 相信學過這個的應(yīng)該大概有個映像吧, 如下圖:

java面試基礎(chǔ) -- ArrayList 和 LinkedList有什么區(qū)別,java面試基礎(chǔ)篇,java,面試,開發(fā)語言

????????可以看出來, ArrayList是向內(nèi)存申請一塊連續(xù)的數(shù)組空間進行存儲, 在數(shù)組的存儲形式的基礎(chǔ)上進行鏈表的增刪改查, 而LinkedList則是每次添加元素的時候就向系統(tǒng)申請一塊內(nèi)存, 不用就直接釋放, 他們雖然在內(nèi)存上不是連續(xù)的, 但是在邏輯上他們是連在一起的.

有什么不同??

?底層實現(xiàn)不同, ArrayList是基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu), 而LInkedLIst是基于雙向鏈表的數(shù)據(jù)結(jié)構(gòu)
隨機訪問的性能不同, Arraylist的隨機訪問性能是由于LinkedList的, 因為ArrayList可以根據(jù)下標來直接訪問, 類似于數(shù)組, 時間復(fù)雜度為O(1), 但是LinkedList的隨機訪問時間復(fù)雜度為O(n), 因為他需要遍歷整個鏈表才能找到指定的元素
插入和刪除不同, 對于插入和刪除, LInkedList要明顯由于ArrayList, 因為LInkedList的摻入和刪除操作時間復(fù)雜度為O(1), 例如插入, 我們可以直接在鏈表的頭部進行插入或者是通過一個元素來記錄最后一個結(jié)點的位置, 然后直接在最后一個結(jié)點進行尾插, 刪除是相同的操作, 因此時間復(fù)雜度為O(1), 但是對于ArrayList就不同了, ArrayList的插入和刪除需要移動插入位置的元素的后面的所有元素, 最壞的情況需要移動ArrayList的所有元素, 因此時間復(fù)雜度為O(n)

但是需要注意的是, 其實他們插入的平均時間復(fù)雜度是一樣的, 接下來我們來探討一下, 他們兩個的平均時間復(fù)雜度:

對于ArrayList的插入的平均時間復(fù)雜度, 它想要插入一個數(shù)字, 雖然是直接指定插入的地方, 也就是他的一個隨機插入的性質(zhì), 但是它還需要對后面的元素進行一個挪動, 運氣不好的話, 就需要挪動整個數(shù)組, 時間復(fù)雜度最壞的情況下是O(n), 最壞的情況下是O(1), 平均下來就是O(n/2), 我們?nèi)サ粝禂?shù), 也就是O(n)
對于LinkedList來說, 他進行插入, 需要遍歷鏈表,從頭到尾遍歷, 好的情況就是在頭的時候就便利到了, 時間復(fù)雜度為O(1), 壞的情況下需要遍歷完整個鏈表, 時間復(fù)雜度最壞的情況就是O(n),平均下來就是O(n/2) ,去掉系數(shù)就是O(n)

? ? 所以對于我們真是運用鏈表的場景, 沒有說他們兩個哪個時間復(fù)雜度, 或者是性能更好, 只能是在不同的情況下適應(yīng)不同的場景.?

小結(jié):

????????ArrayList 和 LinkedList 都是 List 接口的實現(xiàn)類，但它們的底層實現(xiàn)（結(jié)構(gòu)）不同、隨機訪問的性能和添加/刪除的效率不同。如果是隨機訪問比較多的業(yè)務(wù)場景可以選擇使用 ArrayList，如果添加和刪除比較多的業(yè)務(wù)場景可以選擇使用 LinkedList。

????????ArrayList適用于需要快速隨機訪問元素的場景，因為它的底層是基于數(shù)組實現(xiàn)的，可以通過下標直接訪問元素。但是，當需要頻繁插入或刪除元素時，由于需要移動元素，效率較低。

????????LinkedList適用于需要頻繁插入或刪除元素的場景，因為它的底層是基于鏈表實現(xiàn)的，插入或刪除元素只需要改變指針指向，效率較高。但是，當需要隨機訪問元素時，由于需要遍歷鏈表，效率較低。

????????因此，根據(jù)具體的場景需求，選擇合適的集合類可以提高程序的效率。

ArrayList的擴容機制

我們首先創(chuàng)建一個ArrayList如圖:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test  {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>(); // 第0步:創(chuàng)建基于鏈表的List
        arrayList.add(1);  // 1 添加元素
        arrayList.add(2);  // 2 添加元素
        arrayList.add(3);  // 3 添加元素
        arrayList.add(4);  // 4 添加元素
        arrayList.add(5);  // 5 添加元素
        arrayList.add(6);  // 6 添加元素
        arrayList.add(7);  // 7 添加元素
        arrayList.add(8);  // 8 添加元素
        arrayList.add(9);  // 9 添加元素
        System.out.println("hello");  // 打印

    }
}

第0步, 初始化:
java面試基礎(chǔ) -- ArrayList 和 LinkedList有什么區(qū)別,java面試基礎(chǔ)篇,java,面試,開發(fā)語言

java面試基礎(chǔ) -- ArrayList 和 LinkedList有什么區(qū)別,java面試基礎(chǔ)篇,java,面試,開發(fā)語言

ArrayList的構(gòu)造方法如下:

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

里面有三個重載的構(gòu)造方法, 簡單來說就是:

無參構(gòu)造:?Obeject數(shù)組elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
給定初始容量:?
①當傳入的初始容量initialCapacity > 0為真時，創(chuàng)建一個大小為initialCapacity的空數(shù)組，并將引用賦給elementData；

②當傳入的初始容量initialCapacity = 0為真時，將空數(shù)組EMPTY_ELEMENTDATA賦給elementData；

③當傳入的初始容量initialCapacity < 0為真時，直接拋出IllegalArgumentException異常。

此處我們傳入的initialCapacity為空, 也就是無參構(gòu)造方法, 如下:

transient Object[] elementData;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

?????????在構(gòu)造方法中，它將DEFAULTCAPACITY_EMPTY_ELEMENTDATA賦值給elementData，這個DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一個空的Object數(shù)組，而elementData就是ArrayList實際存儲數(shù)據(jù)的容器。

?第1步, 添加元素1:

觸發(fā):

   public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

ensureCapacityInternal為確認初始化容量:

進入ensureCapacityInternal:

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

隨后進入calculateCapacity計算最低所需容量:

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

????????此處的minCapacity為 size + 1, 翻譯過來也就是最低所需的容量, 研究發(fā)現(xiàn), 如果是空數(shù)組(剛開始使用無參構(gòu)造方法的時候)就返回DEFAULT_CAPACITY, 值為10.

? ? ? ? 當elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的時候, 直接返回minCapacity.

????????隨后進入ensureExplicitCapacity(int minCapacity)方法:

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

modCount++，這是用來記錄數(shù)組被修改次數(shù)的變量，我們先不管它.?minCapacity為計算出來的最小所需容量, elementData.length為當前容量,如果最小所需容量大于當前容量, 就需要擴容, 然后進入grow方法:

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

????????老的容量為當前容量,新的容量為老的容量的1.5倍,如果新的容量–最小所需容量<О那么新的容量就等于最小所需容量,如果新的容量-當前數(shù)組最大的容量限制>0,那么就進入hugeCapacity方法,然后使用copyOf方法進行數(shù)據(jù)遷移.將老的數(shù)據(jù)遷移到新的容量的數(shù)組中

總結(jié)一下:

? ? ? ? 我們使用無參構(gòu)造方法的時候, 就會創(chuàng)建一個底層為空的數(shù)組的鏈表, 此時size 為0, 然后向里面添加元素的時候, 此時的minCapacity為 size + 1 = 1, 在calculateCapacity方法中返回了DEFAULT_CAPACITY(10), 然后進入ensureExplicitCapacity(10), 此時的minCapacity = 10 > 當前容量 = 0, 所以進行初始擴容(elementData = Arrays.copyOf(elementData, newCapacity)), 將容量擴充到10, 也就是elementData/length == 10, 隨后的插入, 只要沒有超過10, 那就可以直接插入, 如果容量滿了, 那么就進行1.5倍擴容.

java面試基礎(chǔ) -- ArrayList 和 LinkedList有什么區(qū)別,java面試基礎(chǔ)篇,java,面試,開發(fā)語言

ArrayLIst的基本使用

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test  {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>(); // 第0步:創(chuàng)建基于鏈表的List
        // add(int x) 直接向元素末尾位置添加x
       arrayList.add(1);

       // get(int index) 方法, 返回下標為index的元素
       int a = arrayList.get(0);
        System.out.println(a);

        // add(int index, int element); 向指定位置插入元素
        arrayList.add(1,3);

        // size(); 獲取當前元素的個數(shù)
        int size = arrayList.size();

        // remove(int index); 刪除下標為index 的元素
        arrayList.remove(0);

        // 判斷arrList是否為空, 如果為空就返回true, 否則返回false;
        arrayList.isEmpty();

        // set(int index, int element); 將index 下標的元素設(shè)置為 element
        arrayList.set(0,5);

    }
}

LInkedList與之類似

ArrayList和Vector

? ? ? ? ArrayList和Vector都實現(xiàn)了List接口. 代碼演示如圖:

import java.util.ArrayList;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();
        Vector<String> vector = new Vector<>();

        // 添加元素
        arrayList.add("Java");
        arrayList.add("Python");
        arrayList.add("C++");

        vector.add("Java");
        vector.add("Python");
        vector.add("C++");

        // 獲取元素
        System.out.println(arrayList.get(0));
        System.out.println(vector.get(0));

        // 刪除元素
        arrayList.remove(0);
        vector.remove(0);

        // 獲取元素個數(shù)
        System.out.println(arrayList.size());
        System.out.println(vector.size());
    }
}

但它們有以下區(qū)別：

線程安全性：Vector 是線程安全的，而 ArrayList 不是。所以在多線程環(huán)境下，應(yīng)該使用 Vector。
性能：由于 Vector 是線程安全的，所以它的性能通常比 ArrayList 差。在單線程環(huán)境下，ArrayList 比 Vector 快。
初始容量增長方式：當容量不足時，ArrayList 默認會增加 50% 的容量，而 Vector 會將容量翻倍。這意味著在添加元素時，ArrayList 需要更頻繁地進行擴容操作，而 Vector 則更適合于存儲大量數(shù)據(jù)。

Vector的grow方法

????????綜上所述，如果不需要考慮線程安全問題，并且需要高效的存取操作，則 ArrayList 是更好的選擇；如果需要考慮線程安全以及更好的數(shù)據(jù)存儲能力，則應(yīng)該選擇 Vector。

java面試基礎(chǔ) -- ArrayList 和 LinkedList有什么區(qū)別,java面試基礎(chǔ)篇,java,面試,開發(fā)語言文章來源地址http://www.zghlxwxcb.cn/news/detail-652033.html

到了這里，關(guān)于java面試基礎(chǔ) -- ArrayList 和 LinkedList有什么區(qū)別的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！