ArrayList簡介：ArrayList 的底層是數組隊列，至關於動態數組。與 Java 中的數組相比，它的容量能動態增加。在添加大量元素前，應用程序可使用ensureCapacity操做來增長 ArrayList 實例的容量。這能夠減小遞增式再分配的數量。java
它繼承於 AbstractList，實現了 List, RandomAccess, Cloneable, java.io.Serializable 這些接口。git
在咱們學數據結構的時候就知道了線性表的順序存儲，插入刪除元素的時間複雜度爲O（n）,求表長以及增長元素，取第 i 元素的時間複雜度爲O（1）github
ArrayList 繼承了AbstractList，實現了List。它是一個數組隊列，提供了相關的添加、刪除、修改、遍歷等功能。數組
ArrayList 實現了RandomAccess 接口，即提供了隨機訪問功能。RandomAccess 是 Java 中用來被 List 實現，爲 List 提供快速訪問功能的。在 ArrayList 中，咱們便可以經過元素的序號快速獲取元素對象，這就是快速隨機訪問。ArrayList 實現了Cloneable 接口，即覆蓋了函數 clone()，能被克隆。ArrayList 實現java.io.Serializable 接口，這意味着ArrayList支持序列化，能經過序列化去傳輸。安全
和Vector 不一樣，ArrayList 中的操做不是線程安全的！因此，建議在單線程中才使用 ArrayList，而在多線程中能夠選擇 Vector 或者 CopyOnWriteArrayList數據結構
| package java.util;多線程
import java.util.function.Consumer;dom import java.util.function.Predicate;函數 import java.util.function.UnaryOperator;性能
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L;
/** * 默認初始容量大小 */ private static final int DEFAULT_CAPACITY = 10;
/** * 空數組（用於空實例）。 */ private static final Object[] EMPTY_ELEMENTDATA = {};
//用於默認大小空實例的共享空數組實例。 //咱們把它從EMPTY_ELEMENTDATA數組中區分出來，以知道在添加第一個元素時容量須要增長多少。 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** * 保存ArrayList數據的數組 */ transient Object[] elementData; // non-private to simplify nested class access
/** * ArrayList 所包含的元素個數 */ private int size;
/** * 帶初始容量參數的構造函數。（用戶本身指定容量） */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { //建立initialCapacity大小的數組 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //建立空數組 this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
/** *默認構造函數，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 爲0.初始化爲10，也就是說初始實際上是空數組 當添加第一個元素的時候數組容量才變成10 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
/** * 構造一個包含指定集合的元素的列表，按照它們由集合的迭代器返回的順序。 */ public ArrayList(Collection<? extends E> c) { // elementData = c.toArray(); //若是指定集合元素個數不爲0 if ((size = elementData.length) != 0) { // c.toArray 可能返回的不是Object類型的數組因此加上下面的語句用於判斷， //這裏用到了反射裏面的getClass()方法 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 用空數組代替 this.elementData = EMPTY_ELEMENTDATA; } }
/** * 修改這個ArrayList實例的容量是列表的當前大小。 應用程序可使用此操做來最小化ArrayList實例的存儲。 */ public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } //下面是ArrayList的擴容機制 //ArrayList的擴容機制提升了性能，若是每次只擴充一個， //那麼頻繁的插入會致使頻繁的拷貝，下降性能，而ArrayList的擴容機制避免了這種狀況。 /** * 若有必要，增長此ArrayList實例的容量，以確保它至少能容納元素的數量 * @param minCapacity 所需的最小容量 */ public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY;
if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } //獲得最小擴容量 private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_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方法進行擴容，調用此方法表明已經開始擴容了 grow(minCapacity); }
/** * 要分配的最大數組大小 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/** * ArrayList擴容的核心方法。 */ private void grow(int minCapacity) { // oldCapacity爲舊容量，newCapacity爲新容量 int oldCapacity = elementData.length; //將oldCapacity 右移一位，其效果至關於oldCapacity /2， //咱們知道位運算的速度遠遠快於整除運算，整句運算式的結果就是將新容量更新爲舊容量的1.5倍， int newCapacity = oldCapacity + (oldCapacity >> 1); //而後檢查新容量是否大於最小須要容量，若仍是小於最小須要容量，那麼就把最小須要容量看成數組的新容量， if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //再檢查新容量是否超出了ArrayList所定義的最大容量， //若超出了，則調用hugeCapacity()來比較minCapacity和 MAX_ARRAY_SIZE， //若是minCapacity大於最大容量，則新容量則爲ArrayList定義的最大容量，不然，新容量大小則爲 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); } //比較minCapacity和 MAX_ARRAY_SIZE private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
/** *返回此列表中的元素數。 */ public int size() { return size; }
/** * 若是此列表不包含元素，則返回 true 。 */ public boolean isEmpty() { //注意=和==的區別 return size == 0; }
/** * 若是此列表包含指定的元素，則返回true 。 */ public boolean contains(Object o) { //indexOf()方法：返回此列表中指定元素的首次出現的索引，若是此列表不包含此元素，則爲-1 return indexOf(o) >= 0; }
/** *返回此列表中指定元素的首次出現的索引，若是此列表不包含此元素，則爲-1 */ public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) //equals()方法比較 if (o.equals(elementData[i])) return i; } return -1; }
/** * 返回此列表中指定元素的最後一次出現的索引，若是此列表不包含元素，則返回-1。. */ public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; }
/** * 返回此ArrayList實例的淺拷貝。 （元素自己不被複制。） */ public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); //Arrays.copyOf功能是實現數組的複製，返回複製後的數組。參數是被複制的數組和複製的長度 v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // 這不該該發生，由於咱們是能夠克隆的 throw new InternalError(e); } }
/** *以正確的順序（從第一個到最後一個元素）返回一個包含此列表中全部元素的數組。 *返回的數組將是「安全的」，由於該列表不保留對它的引用。 （換句話說，這個方法必須分配一個新的數組）。 *所以，調用者能夠自由地修改返回的數組。 此方法充當基於陣列和基於集合的API之間的橋樑。 */ public Object[] toArray() { return Arrays.copyOf(elementData, size); }
/** * 以正確的順序返回一個包含此列表中全部元素的數組（從第一個到最後一個元素）; *返回的數組的運行時類型是指定數組的運行時類型。 若是列表適合指定的數組，則返回其中。 *不然，將爲指定數組的運行時類型和此列表的大小分配一個新數組。 *若是列表適用於指定的數組，其他空間（即數組的列表數量多於此元素），則緊跟在集合結束後的數組中的元素設置爲null 。 *（這僅在調用者知道列表不包含任何空元素的狀況下才能肯定列表的長度。） */ @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { if (a.length < size) // 新建一個運行時類型的數組，可是ArrayList數組的內容 return (T[]) Arrays.copyOf(elementData, size, a.getClass()); //調用System提供的arraycopy()方法實現數組之間的複製 System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; }
// Positional Access Operations
@SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }
/** * 返回此列表中指定位置的元素。 */ public E get(int index) { rangeCheck(index);
return elementData(index); }
/** * 用指定的元素替換此列表中指定位置的元素。 */ public E set(int index, E element) { //對index進行界限檢查 rangeCheck(index);
E oldValue = elementData(index); elementData[index] = element; //返回原來在這個位置的元素 return oldValue; }
/** * 將指定的元素追加到此列表的末尾。 */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! //這裏看到ArrayList添加元素的實質就至關於爲數組賦值 elementData[size++] = e; return true; }
/** * 在此列表中的指定位置插入指定的元素。 *先調用 rangeCheckForAdd 對index進行界限檢查；而後調用 ensureCapacityInternal 方法保證capacity足夠大； *再將從index開始以後的全部成員後移一個位置；將element插入index位置；最後size加1。 */ public void add(int index, E element) { rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!! //arraycopy()這個實現數組之間複製的方法必定要看一下，下面就用到了arraycopy()方法實現數組本身複製本身 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
/** * 刪除該列表中指定位置的元素。 將任何後續元素移動到左側（從其索引中減去一個元素）。 */ public E remove(int index) { rangeCheck(index);
modCount++; E oldValue = elementData(index);
int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work //從列表中刪除的元素 return oldValue; }
/** * 從列表中刪除指定元素的第一個出現（若是存在）。 若是列表不包含該元素，則它不會更改。 *返回true，若是此列表包含指定的元素 */ public boolean remove(Object o) { if (o == 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])) { fastRemove(index); return true; } } return false; }
/* * Private remove method that skips bounds checking and does not * return the value removed. */ private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work }
/** * 從列表中刪除全部元素。 */ public void clear() { modCount++;
// 把數組中全部的元素的值設爲null for (int i = 0; i < size; i++) elementData[i] = null;
size = 0; }
/** * 按指定集合的Iterator返回的順序將指定集合中的全部元素追加到此列表的末尾。 */ public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; }
/** * 將指定集合中的全部元素插入到此列表中，從指定的位置開始。 */ public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index);
Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; }
/** * 今後列表中刪除全部索引爲fromIndex （含）和toIndex之間的元素。 *將任何後續元素移動到左側（減小其索引）。 */ protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
// clear to let GC do its work int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; }
/** * 檢查給定的索引是否在範圍內。 */ private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
/** * add和addAll使用的rangeCheck的一個版本 */ private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
/** * 返回IndexOutOfBoundsException細節信息 */ private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; }
/** * 今後列表中刪除指定集合中包含的全部元素。 */ public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); //若是此列表被修改則返回true return batchRemove(c, false); }
/** * 僅保留此列表中包含在指定集合中的元素。 *換句話說，今後列表中刪除其中不包含在指定集合中的全部元素。 */ public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); }
/** * 從列表中的指定位置開始，返回列表中的元素（按正確順序）的列表迭代器。 *指定的索引表示初始調用將返回的第一個元素爲next 。 初始調用previous將返回指定索引減1的元素。 *返回的列表迭代器是fail-fast 。 */ public ListIterator<E> listIterator(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index); return new ListItr(index); }
/** *返回列表中的列表迭代器（按適當的順序）。 *返回的列表迭代器是fail-fast 。 */ public ListIterator<E> listIterator() { return new ListItr(0); }
/** *以正確的順序返回該列表中的元素的迭代器。 *返回的迭代器是fail-fast 。 */ public Iterator<E> iterator() { return new Itr(); }
|
在如上的源碼中，咱們能夠獲得，在每次增長或者刪除數據的時候都要進行位置或者容量的判斷，擴容時默認擴展爲1.5倍的容量（經過右移>>來擴展，這樣的效率比/2的效率高），可是若是增長的數據比0.5倍的容量要多，則選擇擴展所需大小的容量，咱們能夠發現，不論是刪除數組多餘的空間仍是擴展空間，都頻繁用到了數組的複製，System.arraycopy()和Arrays.copyOf()方法 ，看二者源代碼能夠發現copyOf()內部調用了System.arraycopy()方法 區別: arraycopy()須要目標數組，將原數組拷貝到你本身定義的數組裏，並且能夠選擇拷貝的起點和長度以及放入新數組中的位置; copyOf()是系統自動在內部新建一個數組，並返回該數組。
/** *以正確的順序（從第一個到最後一個元素）返回一個包含此列表中全部元素的數組。 *返回的數組將是「安全的」，由於該列表不保留對它的引用。（換句話說，這個方法必須分配一個新的數組）。 *所以，調用者能夠自由地修改返回的數組。此方法充當基於陣列和基於集合的API之間的橋樑。 */ public Object[] toArray() { //elementData：要複製的數組；size：要複製的長度 return Arrays.copyOf(elementData, size); }
|
ArrayList的遍歷方式：
ArrayList<Integer> arrayList = new ArrayList<Integer>(); //第一種：經過迭代器遍歷 System.out.print("經過迭代器遍歷:"); Iterator<Integer> it = arrayList.iterator(); while(it.hasNext()){ System.out.print(it.next() + " "); } //第二種：經過索引值遍歷 System.out.print("經過索引值遍歷:"); for(int i = 0; i < arrayList.size(); i++){ System.out.print(arrayList.get(i) + " "); } //第三種：for循環遍歷 System.out.print("for循環遍歷:"); for(Integer number : arrayList){ System.out.print(number + " "); }
|