ArrayList詳解

概述

ArrayList是我們日常中最長用的集合之一,在使用列表時,除非特殊情況,我們一般都會選擇使用ArrayList,本文就ArrayList的幾個主要方法進行介紹,並結合幾個圖片來介紹幾個重要操作。

基礎屬性

一些基本屬性,參考下圖理解。

get方法

很簡單,由於底層是數組實現的,先檢查下索引是否越界,然後直接返回對應索引位置的元素即可。

set方法

  1. 校驗索引是否越界
  2. 根據index獲取指定位置的元素
  3. 用傳入的element替換index位置的元素
  4. 返回index位置原來的元素

add方法

add(E e):

  1. 調用ensureCapacityInternal方法(下文有詳解),如果數組還沒初始化,則進行初始化;如果已經初始化瞭,則將modCount+1,並校驗添加元素後是否需要擴容。
  2. 在elementData數組尾部添加元素即可(size位置)。

add(int index, E element):

  1. 檢查索引是否越界,再調用ensureCapacityInternal方法,將modCount+1,並校驗添加元素後是否需要擴容。
  2. 將index位置及之後的所有元素向右移動一個位置(為要添加的元素騰出1個位置)。
  3. 將index位置設置為element元素,並將size+1。

add(int index, E element)的過程如下圖所示。

remove方法

remove(int index):

  1. 檢查索引是否越界,將modCount+1,拿到索引位置index的原元素。
  2. 計算需要移動的元素個數。
  3. 如果需要移動,將index+1位置及之後的所有元素,向左移動一個位置。
  4. 將size-1位置的元素賦值為空(因為上面將元素左移瞭,所以size-1位置的元素為重復的,將其移除)。

remove(Object o):

  1. 如果入參元素為空,則遍歷數組查找是否存在元素為空,如果存在則調用fastRemove將該元素移除,並返回true表示移除成功。
  2. 如果入參元素不為空,則遍歷數組查找是否存在元素與入參元素使用equals比較返回true,如果存在則調用fastRemove將該元素移除,並返回true表示移除成功。
  3. 否則,不存在目標元素,則返回false。

fastRemove(int index):跟remove(int index)類似

  1. 將modCount+1,並計算需要移動的元素個數。
  2. 如果需要移動,將index+1位置及之後的所有元素,向左移動一個位置。
  3. 將size-1位置的元素賦值為空(因為上面將元素左移瞭,所以size-1位置的元素為重復的,將其移除)。

remove(int index)方法的過程如下圖所示。

clear方法

遍歷數組將所有元素清空即可。

擴容

上文add方法在添加元素之前會先調用ensureCapacityInternal方法,主要是有兩個目的:1.如果沒初始化則進行初始化;2.校驗添加元素後是否需要擴容。

ensureCapacityInternal(int minCapacity):此方法就是為默認大小的空實例數組DEFAULTCAPACITY_EMPTY_ELEMENTDATA而寫的,判斷數組是否為DEFAULTCAPACITY_EMPTY_ELEMENTDATA,如果是則將minCapacity設置為DEFAULT_CAPACITY。

ensureExplicitCapacity(int minCapacity):將modCount+1,並校驗minCapacity是否大於當前數組的容量,如果大於則調用grow方法進行擴容。

grow(int minCapacity):

  1. 將數組新容量設置為老容量的1.5倍。
  2. 兩個if判斷,第一個是對DEFAULTCAPACITY_EMPTY_ELEMENTDATA初始化的兼容,第二個是對超過MAX_ARRAY_SIZE的兼容。
  3. 調用Arrays.copyOf方法創建長度為newCapacity的新數組,並將老數組的數據復制給新數組,並將elementData賦值為新數組。

grow(int minCapacity)的過程如下圖所示。

ArrayList和LinkedList比較

  1. ArrayList底層基於動態數組實現,LinkedList底層基於鏈表實現。
  2. 對於隨機訪問(get/set方法),ArrayList通過index直接定位到數組對應位置的節點,而LinkedList需要從頭結點或尾節點開始遍歷,直到尋找到目標節點,因此在效率上ArrayList優於LinkedList
  3. 對於插入和刪除(add/remove方法),ArrayList需要移動目標節點後面的節點(使用System.arraycopy方法移動節點),而LinkedList隻需修改目標節點前後節點的next或prev屬性即可,因此在效率上LinkedList優於ArrayList。

推薦閱讀

赞(0)