1. Array

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

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

例如:

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: 251 exec time is: 17

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()，下面將針對三種情況對該方法進行解析：