ArrayList與linkedList的用法區別及擴容方式

2023-09-06 14:04:44

1. Array

Array（陣列）是基於索引(index)的資料結構，它使用索引在陣列中搜尋和讀取資料是很快的。

Array獲取資料的時間複雜度是O(1),但是要刪除資料卻是開銷很大，因為這需要重排陣列中的所有資料, (因為刪除資料以後, 需要把後面所有的資料前移)

缺點: 陣列初始化必須指定初始化的長度, 否則報錯

例如：

int[] a = new int[4];//推介使用int[] 這種方式初始化

int c[] = {23,43,56,78};//長度：4，索引範圍：[0,3]

2. List

List—是一個有序的集合，可以包含重複的元素，提供了按索引存取的方式，它繼承Collection。

List有兩個重要的實現類：ArrayList和LinkedList

List是一個介面，不可以範例化, 不能寫成如下：

List<Integer> list = new List<Integer>();//錯誤

類繼承關係

3. ArrayList

ArrayList: 可以看作是能夠自動增長容量的陣列
ArrayList的toArray方法返回一個陣列
ArrayList的asList方法返回一個列表

ArrayList底層的實現是Array, 陣列擴容實現

新增資料空間判斷
新增資料的時候需要判斷當前是否有空閒空間儲存
擴容需要申請新的連續空間
把老的陣列複製過去
新加的內容
回收老的陣列空間

4. 使用陣列長度分配空間效能對比

注意: 長度儘量使用2的冪作為長度, 計算機分配空間大都使用次冪去分配, 減少碎片空間

我們下來看一下程式碼:

package javatest;
 
import java.util.ArrayList;
import java.util.List;
 
/**
 * @ClassName Jtest
 * @Description TODO
 * @Author lingxiangxiang
 * @Date 4:54 PM
 * @Version 1.0
 **/
public class Jtest {
 
    public static int length = 1048576; //10的20次冪
    public static List<Integer> list1 = new ArrayList<>();
    public static List<Integer> list2 = new ArrayList<>(length);
 
    public static void addList(int sign) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < length; i++) {
            if (sign == 0) {
                list1.add(sign);
            } else {
                list2.add(sign);
            }
        }
        long end = System.currentTimeMillis();
        System.out.println(sign + " exec time is: " + (end - start));
    }
 
    public static void main(String[] args) {
        addList(0);
        addList(1);
    }
}

執行結果:

0 exec time is: 25
1 exec time is: 17

ArrayList在初始化的時候指定長度肯定是要比不指定長度的效能好很多, 這樣不用重複的申請空間, 複製陣列, 銷燬老的分配空間了

5. LinkList

LinkList是一個雙連結串列,在新增和刪除元素時具有比ArrayList更好的效能.

但在get與set方面弱於ArrayList.當然,這些對比都是指資料量很大或者操作很頻繁。

連結串列不需要連續的空間, 大小不確定

6. 對比

時間複雜度

操作	陣列	連結串列
隨機存取	O(1)	O(N)
頭部插入	O(N)	O(1)
頭部刪除	O(N)	O(1)
尾部插入	O(1)	O(1)
尾部刪除	O(1)	O(1)

小結

同樣查詢, 時間複雜度都是O(N), 但是陣列要比連結串列快
因為陣列的連續記憶體, 會有一部分或者全部資料一起進入到CPU快取, 而連結串列還需要在去記憶體中根據上下游標查詢, CPU快取比記憶體塊太多
資料大小固定, 不適合動態儲存, 動態新增, 記憶體為一連續的地址, 可隨機存取, 查詢速度快
連結串列代銷可變, 擴充套件性強, 只能順著指標的方向查詢, 速度較慢

7. ArrayList的原始碼分析

7.1 ArrayList的主要成員變數

  private static final int DEFAULT_CAPACITY = 10;
  // ArrayList的預設長度是多少
    private static final Object[] EMPTY_ELEMENTDATA = {};
  // ArrayList的預設空元素連結串列
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  // ArrayList存放的資料
    transient Object[] elementData; // non-private to simplify nested class access
  // ArrayList的長度
    private int size;

7.2 ArrayList的建構函式

// 構造一個初始化容量為10的空列表
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
// 初始化一個指定大小容量的列表
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);
        }
    }
// 構造一個包含指定集合的元素列表, 按照它們由集合迭代器返回的順序
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;
        }
    }

7.3 擴容機制

ArrayList擴容的核心從ensureCapacityInternal方法說起。可以看到前面介紹成員變數的提到的ArrayList有兩個預設的空陣列：

DEFAULTCAPACITY_EMPTY_ELEMENTDATA：是用來使用預設構造方法時候返回的空陣列。如果第一次新增資料的話那麼陣列擴容長度為DEFAULT_CAPACITY=10。
EMPTY_ELEMENTDATA：出現在需要用到空陣列的地方，其中一處就是使用自定義初始容量構造方法時候如果你指定初始容量為0的時候就會返回。

// 增加元素的方法
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
 
 //判斷當前陣列是否是預設構造方法生成的空陣列，如果是的話minCapacity=10反之則根據原來的值傳入下一個方法去完成下一步的擴容判斷
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
        }
 
//minCapacitt表示修改後的陣列容量，minCapacity = size + 1
 private void ensureCapacityInternal(int minCapacity) {
        //判斷看看是否需要擴容
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

下面談談ensureExplicitCapacity方法（modCount設計到Java的快速報錯機制後面會談到），可以看到如果修改後的陣列容量大於當前的陣列長度那麼就需要呼叫grow進行擴容，反之則不需要。

//判斷當前ArrayList是否需要進行擴容
private void ensureExplicitCapacity(int minCapacity) {
  modCount++;
 
  // overflow-conscious code
  // int[] a = new int[5]; 陣列建立的時候是多大, a.length就等於5
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}

最後看下ArrayList擴容的核心方法grow()，下面將針對三種情況對該方法進行解析：

當前陣列是由預設構造方法生成的空陣列並且第一次新增資料。此時minCapacity等於預設的容量（10）那麼根據下面邏輯可以看到最後陣列的容量會從0擴容成10。而後的陣列擴容才是按照當前容量的1.5倍進行擴容；
當前陣列是由自定義初始容量構造方法建立並且指定初始容量為0。此時minCapacity等於1那麼根據下面邏輯可以看到最後陣列的容量會從0變成1。這邊可以看到一個嚴重的問題，一旦我們執行了初始容量為0，那麼根據下面的演演算法前四次擴容每次都 +1，在第5次新增資料進行擴容的時候才是按照當前容量的1.5倍進行擴容。
當擴容量（newCapacity）大於ArrayList陣列定義的最大值後會呼叫hugeCapacity來進行判斷。如果minCapacity已經大於Integer的最大值（溢位為負數）那麼丟擲OutOfMemoryError（記憶體溢位）否則的話根據與MAX_ARRAY_SIZE的比較情況確定是返回Integer最大值還是MAX_ARRAY_SIZE。這邊也可以看到ArrayList允許的最大容量就是Integer的最大值（-2的31次方~2的31次方減1）

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);
    }