一、ArrayList集合

　　1.數據結構特點

　　ArrayList底層數據結構是一個數組,查詢元素速度快,增刪速度稍慢

　　2.幾個概念:

　　(1)DEFAULT_CAPACITY: 表示數組的初始大小,默認10

　　(2)size: 表示當前數組的大小

　　(3)modCount: 統計當前數組元素被修改的次數,只要修改,就+1

　　3.空參構造方法初始化

　　4.第一次添加元素擴容原理

public boolean add(E e) {
        //確保數組大小是否足夠,不夠執行擴容,size為當前數組的大小
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //直接把元素e保存到數組中
        elementData[size++] = e;
        return true;
    }

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

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果是空數組{}
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //在最小容量minCapacity和DEFAULT_CAPACITY(10)選擇一個較大的值
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    //記錄修改次數
    modCount++;
    //如果我們期望的最小容量>數組目前的長度就擴容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //oldCapacity >> 1: 是把oldCapacity/2的意思
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果擴容后的值<我們期望的值,擴容后的值等于我們期望的值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //如果擴容后的值>jvm所能分配的數組的最大值,那么就用Integer的最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //通過復制數組擴容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

　　注意:

　　1.擴容的規則并不是翻倍,是原來容量大小的1.5倍

　　2.ArrayList中數組的最大長度是Integer.MAX_VALUE,超過這個值,JVM就不會給數組分配內存空間了

　　3.新增元素時,并沒有對值進行嚴格的校驗,所以ArrayList是允許null值的

　　二、LinkeList集合

　　1.數據結構特點:

　　LinkedList底層數據結構是一個雙向鏈表,鏈表中的每個節點都可以查找前一個節點或者向后查找后一個節點

　　2.幾個概念:

　　(1)鏈表每個節點叫做Node,Node有prev屬性,代表前一個節點的地址,next屬性代表后一個節點的地址

　　(2)first是雙向鏈表的頭節點,它的前一個節點是null

　　(3)last是雙向鏈表的尾節點,它的后一個節點是null

　　(4)鏈表中如果沒有數據,first和last都null

　　(5)因為是雙向鏈表,只要內存空間足夠大,鏈表的大小是沒有限制的

　　3.鏈表中的元素(節點)叫做Node,是LinkedList集合的私有靜態內部類,代碼如下:

private static class Node<E> {
        E item;//節點數據
        Node<E> next;//下一個節點的地址
        Node<E> prev;//前一個節點的地址
        //初始化參數順序是: 前一個節點地址,節點本身的數據,后一個節點地址
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

　　4.add添加節點(從鏈表尾部添加)

public boolean add(E e) {
    linkLast(e);
    return true;//鏈表節點數據可以重復,所以add方法始終返回true
}

//從尾部添加節點
void linkLast(E e) {
    //把尾節點地址存儲在l中
    final Node<E> l = last;
    //創建新的節點,參數含義如下
    //l是新節點的前一個節點的地址,當前值是尾節點地址值
    //e是當前新增節點中保存的數據,當前新增節點的下一個節點是null,因為是在末尾添加
    final Node<E> newNode = new Node<>(l, e, null);
    //last指向新增節點(新增節點作為尾節點)
    last = newNode;
    //如果鏈表為空(第一次添加節點)(l是尾節點,尾節點為空,鏈表即空),頭部和尾部都是指向同一個節點,都是新建的節點
    if (l == null)
        first = newNode;
    else
        //鏈表不是空(非第一次添加節點),把添加新節點之前的尾節點的下一個節點指向新添加的節點
        l.next = newNode;
    //節點數+1
    size++;
    //鏈表的實際修改次數+1
    modCount++;
}　

       5.get(int index)查詢節點

    public E get(int index) {
        checkElementIndex(index);//檢查索引值是否越界
        return node(index).item;
    }
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }
    核心根據索引獲取節點數據的方法
    鏈表查詢某個節點是比較慢的,需要挨個查找才可以

根據鏈表索引位置查詢元素
Node<E> node(int index) {
    //如果index處于鏈表的前半部分,從頭開始查,size>>1 是 size/2的意思
    if (index < (size >> 1)) {
       
        Node<E> x = first;
        //知道for循環到index的前一個node停止
        for (int i = 0; i < index; i++)            
            x = x.next;
        return x;
    } else {
        //如果index處于鏈表的后半部分,從尾開始查
        Node<E> x = last;
        //知道for循環到index的后一個node停止
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}　

       從源碼中發現,LinkedList并沒有采用從頭循環到尾的做法,而是采取了簡單二分查找法,

　　首先看index是在鏈表的左半部分還是右半部分.如果是在左半部分,就從左側開始找,

　　如果實在鏈表的有伴部分,就從右側開始找.這種方式,循環的次數至少降低了一半,提高查詢性能。

　　本文版權歸黑馬程序員Java培訓學院所有，歡迎轉載，轉載請注明作者出處。謝謝!

　　作者：黑馬程序員Java培訓學院

　　首發：https://java.itheima.com