java集合之ArrayList詳解

ArrayList 是一個數組隊列，相當于動态數組。

與Java中的數組相比，它的容量能動态增長。

它繼承于AbstractList，實作了List, RandomAccess, Cloneable, java.io.Serializable這些接口。

一、所在包

集合存在于java.util包路徑下

二、特點

• 重複性：資料可以重複
• null值：可以有null值存在
• 有序性：能保證插入的資料有序

三、常用方法介紹

int size()： // 集合中存儲元素的個數

boolean isEmpty()  //判斷目前集合是否為空，傳回值是Boolean類型
//false：集合不為空   true:集合為空

boolean contains(Object o) //判斷目前集合是否包含該Object對象

Iterator<E> iterator() //疊代器，傳回iterator執行個體

Object[] toArray() //将集合轉化為數組

<T> T[] toArray(T[] a) //将集合轉化為數組

 boolean add(E e) //添加元素
 
 boolean remove(Object o)  //删除元素
 
 boolean containsAll(Collection<?> c) //判斷入參集合是否屬于目前集合
 
 boolean addAll(Collection<? extends E> c) // 對該集合添加子集合形成新的集合
 
 boolean addAll(int index, Collection<? extends E> c) //在指定的位置添加子集合
 
void clear() //将集合清除掉

boolean equals(Object o) //判斷是否相等

E get(int index) //通過指定位置來擷取元素

int indexOf(Object o) //判斷目前元素在集合中的位置（從集合頭部往後查找）

int lastIndexOf(Object o) //判斷目前元素在集合中的位置(從集合尾部往前查找)

List<E> subList(int fromIndex, int toIndex) //找目前集合的子集

boolean retainAll(Collection<?> c) //移除此 collection 中未包含在指定 collection 中的所有元素。
//假設有兩個集合A,B，retainAll相當于對A，B做交集，最終結果存在A中，B不要
//傳回值表示的是A是否發生改變
           

四、繼承關系

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
        
ArrayList繼承AbstractList，父類中對部分接口進行實作
實作了List接口提供的方法，Serializable說明該類能夠被序列化 ，能夠被克隆、序列化
           

五、底層資料結構

ArrayList底層資料結構是————數組

六、基本屬性

//預設容量大小
private static final int DEFAULT_CAPACITY = 10;
//預設數組大小
private static final Object[] EMPTY_ELEMENTDATA = {};
//存儲元素的數組
private transient Object[] elementData;
//集合存儲元素的個數
private int size;
           

七、構造函數

1.有參構造，指定集合初始化大小

public ArrayList(int initialCapacity) {
    super();
    //指定大小不合法，則直接抛出異常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity]; //初始化數組大小
}
           

2.無參構造

public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}
           

3.有參構造，通過集合來建立新的集合

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}
           

八、CRUD方法研究

• add()：添加元素

  首先需要進行擴容考慮，如果要擴容（size+1 > table.lengrh），按照1.5倍進行擴容

  将元素插入數組尾部，并對計數size+1

源碼分析

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

//擴容
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  //1.5倍進行擴容
    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);  //将新數組複制到elementData中
}    
           

• remove()：删除元素
  • 先找到元素存儲位置

  • 然後判斷

    注意： null和非null的對象判斷相等的不同：一個是== ，一個是equals

  • 數組移動

    注意： 相同元素存在的情況下，隻需找到從0号開始第一次出現的元素删除

源碼

public boolean remove(Object o) {
    if (o == null) { //如果删除的元素為null
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) { //比較時用==
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) { //如果不為null，比較用equals
                fastRemove(index);
                return true;
            }
    }
    return false;
} 

//删除元素方法
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1; //删除元素後要移動的長度（該元素後面的元素個數）
    if (numMoved > 0) //删除的不是最後一個元素
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);  //從elementData的index+1處開始複制，放置到elementData的index開始numMoved長度
    elementData[--size] = null; 
}  
           

• get()方法：擷取元素

public E get(int index) {
    rangeCheck(index);  //檢查範圍
    return elementData(index);
}

 private void rangeCheck(int index) {
     if (index < 0 || index >= this.size)
         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 } 
E elementData(int index) {
    return (E) elementData[index];
}          
           

數組和集合的差別

1. 長度差別

   數組的長度固定

   集合長度可變

2. 内容不同

   數組存儲的是同一種類型的元素

   集合可以存儲不同類型的元素

3. 元素的資料類型不同

   數組可以存儲基本資料類型，也可以存儲引用資料類型資料

   集合隻能存儲引用類型