ArrayList和LinkedList的區別、擴容機制及底層的實現方式是什么

這篇文章主要介紹“ArrayList和LinkedList的區別、擴容機制及底層的實現方式是什么”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“ArrayList和LinkedList的區別、擴容機制及底層的實現方式是什么”文章能幫助大家解決問題。

ArrayList和LinkedList區別、擴容機制及底層實現

ArrayList

ArrayList的底層實現為數組存儲在內存中，線程不同步。可通過數組下標的形式進行查找，所以在查詢方面的效率較為出色，常用在查詢較多的情景下。

LinkedList

LinkedList的底層實現為鏈表形式，也為線程不同步。而鏈表的底層也決定了它在查詢方面不如數組底層的ArrayList而在指定位置插入等修改操作下，性能優于ArrayList。

Vestor

另外還有Vestor，Vestor也是和ArrayList、LinkedList一樣實現了java.util.List接口。最大的區別在于Vestor是線程同步的，所以在效率方面不如另外兩者，適用于多線程項目中。

ArrayList的擴容機制

/**
     * Constructs an empty list with the specified initial capacity.
     */
    public ArrayList(int initialCapacity) {
    super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
    this.elementData = new Object[initialCapacity];
    }

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

翻閱源碼會發現ArrayList初始化如果不指定大小的時候 初始大小為10。

    public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
        newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
    }
    }

擴容的規則也在源碼中有體現，擴容后的大小= 原始大小+原始大小/2 + 1。在進行插入等操作的時候，如果判斷出大小不夠，會依據此方法進行擴容。(以上是JDK1.6版本的源碼，在JDK1.7中擴容規則進行了修改，改為了擴容后的大小= 原始大小+原始大小/2)

LinkedList的擴容機制

由于它的底層是用雙向鏈表實現的，沒有初始化大小，也沒有擴容的機制。

ArrayList和LinkedList（常用方法、底層結構及擴容機制）

1.ArrayList解說

ArrayList初始長度為0（這里以jdk1.8為例），是一個Object類型的空數組，如下

當第一次調用add后，長度變為10

當數組首次擴容的10個空間用完需要擴容后，會第二次走grow方法來擴容（每次擴容為1.5倍）

總的來說：

ArrayList初始大小為10，每次1.5倍進行擴容；它的底層是用數組實現的，所以查詢速度相對LinkedList要快。

2.LinkedList解說

（1）

* LinkedList 是一個繼承于AbstractSequentialList的雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。

* LinkedList 實現 List 接口，能對它進行隊列操作。

* LinkedList 實現 Deque 接口，即能將LinkedList當作雙端隊列使用。

* LinkedList 實現了Cloneable接口，即覆蓋了函數clone()，能克隆。

* LinkedList 實現java.io.Serializable接口，這意味著LinkedList支持序列化，能通過序列化去傳輸。

* LinkedList 是非同步的。

由于它的底層是用雙向鏈表實現的，所以它對元素的增加、刪除效率要比ArrayList好；它是一個雙向鏈表，沒有初始化大小，也沒有擴容的機制，就是一直在前面或者后面新增就好。

（2）LinkedList底層的數據結構是基于雙向循環鏈表的，且頭結點中不存放數據,如下：

private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;

header是雙向鏈表的頭節點，它是雙向鏈表節點所對應的類Entry的實例。Entry中包含成員變量： previous, next, element。其中，previous是該節點的上一個節點，next是該節點的下一個節點，element是該

節點所包含的值。size是雙向鏈表中節點實例的個數。

總之，addBefore(E e,Entry<E> entry)實現在entry之前插入由e構造的新節點。而add(E e)實現在header節點之前插入由e構造的新節點。為了便于理解，下面給出插入節點的示意圖。

關于“ArrayList和LinkedList的區別、擴容機制及底層的實現方式是什么”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。