ArrayList集合詳解

public boolean add(E e) {
  //確保數(shù)組大小是否足夠,不夠執(zhí)行擴容,size為當前數(shù)組的大小
        ensureCapacityInternal(size + 1);  // Increments modCount!!
  //直接把元素e保存到數(shù)組中
        elementData[size++] = e;
        return true;
    }
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
 //如果是空數(shù)組{}
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  //在最小容量minCapacity和DEFAULT_CAPACITY(10)選擇一個較大的值
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
 //記錄修改次數(shù)
    modCount++;
 //如果我們期望的最小容量>數(shù)組目前的長度就擴容
    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所能分配的數(shù)組的最大值,那么就用Integer的最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //通過復制數(shù)組擴容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

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

public boolean add(E e) {
 linkLast(e);
 return true;//鏈表節(jié)點數(shù)據(jù)可以重復,所以add方法始終返回true
}
//從尾部添加節(jié)點
void linkLast(E e) {
 //把尾節(jié)點地址存儲在l中
    final Node<E> l = last;
 //創(chuàng)建新的節(jié)點,參數(shù)含義如下
 //l是新節(jié)點的前一個節(jié)點的地址,當前值是尾節(jié)點地址值
 //e是當前新增節(jié)點中保存的數(shù)據(jù),當前新增節(jié)點的下一個節(jié)點是null,因為是在末尾添加
    final Node<E> newNode = new Node<>(l, e, null);
 //last指向新增節(jié)點(新增節(jié)點作為尾節(jié)點)
    last = newNode;
 //如果鏈表為空(第一次添加節(jié)點)(l是尾節(jié)點,尾節(jié)點為空,鏈表即空),頭部和尾部都是指向同一個節(jié)點,都是新建的節(jié)點
    if (l == null)
        first = newNode;
    else
  //鏈表不是空(非第一次添加節(jié)點),把添加新節(jié)點之前的尾節(jié)點的下一個節(jié)點指向新添加的節(jié)點
        l.next = newNode;
 //節(jié)點數(shù)+1
    size++;
 //鏈表的實際修改次數(shù)+1
    modCount++;
}

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循環(huán)到index的前一個node停止
        for (int i = 0; i < index; i++)    
            x = x.next;
        return x;
    } else {
  //如果index處于鏈表的后半部分,從尾開始查
        Node<E> x = last;
  //知道for循環(huán)到index的后一個node停止
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}