2. 簡介
java.util.List 是有序集合，也稱為 sequence。此接口可以精确控制每個元素在 List 中的插入位置。使用者可以通過整數索引通路集合中的元素。
2. List 實作類 - ArrayList
java.util.ArrayList 接口是基于 Object 數組、可調整容量大小的 java.util.List 接口的實作之一。java.util.ArrayList 實作了 java.util.List 接口的所有操作，并允許存儲所有元素(包括 null)。java.util.ArrayList 類大緻相當于 java.util.Vector，不同的是 java.util.Vector 類是線程安全的。
2.1 ArrayList 類的重要屬性
- transient Object[] elementData : 用于元素存儲的對象數組；
- private static final int DEFAULT_CAPACITY = 10 : 預設初始容量；
- private static final Object[] EMPY_ELEMENTDATA = {} : 用于空執行個體的共享空數組執行個體；
- private static final Object[] DEFAULTCAPACITY_EMPY_ELEMENTDATA = [] : 用于預設大小的空執行個體的共享空數組執行個體；
- private int size : ArrayList 的大小(包含的元素個數)；
2.2 執行個體化 ArrayList 對象
2.2.1 執行個體化一個預設初始容量為 10 的空 List
class ArrayListTest {
public static void main(String [] args) {
new ArrayList();
}
}
ArrayList 對應的構造函數源碼如下：
/**
* Constructs an empty list with an initial capacity of ten.
* 構造一個初始容量為 10 的空 list
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2.2.2 執行個體化一個具有指定容量的空 ArrayList
class ArrayListTest {
public static void main(String [] args) {
new ArrayList(20);
}
}
ArrayList 對應的構造函數源碼如下：
/**
* Constructs an empty list with the specified initial capacity.
* 構造一個具有指定初始容量的空 list
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
* 如果指定的初始容量為負，則抛出 IllegalArgumentException 異常。
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
2.2.3 按集合疊代器傳回順序執行個體化一個包含指定集合元素的 ArrayList
class ArrayListTest {
public static void main(String [] args) {
Collection list = new ArrayList();
new ArrayList(list);
}
}
ArrayList 對應的構造函數源碼如下：
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
* 按照集合的疊代器傳回的順序構造一個包含指定集合元素的list。
* 将list轉換為數組，然後使用數組拷貝填充到list
*
* @param c the collection whose elements are to be placed into this list
* 其元素将被放入此list的集合。
* @throws NullPointerException if the specified collection is null
* 如果指定的集合為空，則抛出 NullPointerException。
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
2.2.4 使用常用工具包執行個體化 ArrayList
使用 guava 執行個體化期望容量的 ArrayList：
Guava com.google.common.collect.Lists#newArrayListWithExpectedSize(int) 源碼如下：
@GwtCompatible(serializable = true)
public static <E> ArrayList<E> newArrayListWithExpectedSize(int estimatedSize) {
return new ArrayList<>(computeArrayListCapacity(estimatedSize));
}
@VisibleForTesting
static int computeArrayListCapacity(int arraySize) {
checkNonnegative(arraySize, "arraySize");
// TODO(kevinb): Figure out the right behavior, and document it
return Ints.saturatedCast(5L + arraySize + (arraySize / 10));
}
@CanIgnoreReturnValue
static int checkNonnegative(int value, String name) {
if (value < 0) {
throw new IllegalArgumentException(name + " cannot be negative but was: " + value);
}
return value;
}
public static int saturatedCast(long value) {
if (value > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (value < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
return (int) value;
}
2.3 ArrayList 插入元素 add
2.3.1 将指定元素插入到 ArrayList 執行個體對象末尾 add(E e)
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = Lists.newArrayListWithExpectedSize(20);
arrayList.add("hello");
}
}
add(E e) 方法源代碼如下：
/**
* Appends the specified element to the end of this list.
* 将指定的元素插入到此list的末尾
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
add(E e) 方法的時間複雜度
add 方法在插入元素之前有一步確定數組容量的判斷，是以數組是否進行擴容操作，對于 ArrayList 的時間複雜度有很大不同。擴容操作在後續進行講解。
- 不擴容時 add 方法的時間複雜度為 O(1)
- 擴容時 add 方法的時間複雜度為 O(n + 1)
2.3.2 在ArrayList執行個體對象指定位置插入元素 add(int index, E element)
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = Lists.newArrayListWithExpectedSize(20);
arrayList.add("hello");
arrayList.add(0, "world");
}
}
add(int index, E element) 源代碼如下：
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
* 在此list中指定位置插入指定元素。将目前在該位置的元素和任何其後續元素向右移動。
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
add(int index, E element) 時間複雜度
在指定位置插入元素時，其後續元素向右移動(數組拷貝)。
- 不擴容且在最後插入元素時時間複雜度為 O(1)
- 需要擴容且在頭部插入元素時時間複雜度為 O(2n + 1)
2.3.3 按指定集合的疊代器傳回順序，将指定集合中的所有元素追加到集合末尾 addAll(Collection<? Extends E> c)
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
ArrayList<String> arrayList2 = new ArrayList<>(20);
arrayList2.addAll(arrayList2);
}
}
addAll(Collection<? extends E> c) 源代碼如下：
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
* 按照指定集合的疊代器傳回的順序，将指定集合中的所有元素追加到此list的末尾。如果在操作進行時
* 修改了指定的集合，則此操作的行為未定義。這意味着如果指定的集合是這個list，并且這個list是非空的，
* 那麼這個調用的行為是未定義。
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
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;
}
時間複雜度：
- 不擴容情況下為 O(n)，取決于要添加元素的個數
- 擴容情況下為 O(m + n)，取決于原始集合和添加的集合中元素的個數
2.3.3 按指定集合的疊代器傳回順序，将指定集合中的所有元素追加到指定位置 addAll(int index, Collection<? Extends E> c)
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
ArrayList<String> arrayList2 = new ArrayList<>(20);
arrayList2.addAll(1, arrayList2);
}
}
addAll(int index, Collection<? extends E> c) 源代碼如下：
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
* 從指定位置開始，将指定集合中的所有元素插入此list。将目前在該位置和其後續元素向右移動。
* 新元素将按照指定集合的疊代器傳回的順序出現在清單中。
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
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;
}
時間複雜度：
- 不擴容情況下為 O(size() - index + n) size() 為源集合的大小，index 為要插入的位置，n 為追加元素的個數；
- 擴容情況下為 o(m + m - index + n) m 為源集合的大小，index 為要出入的位置，n 為追加元素的個數；
2.4 ArrayList 更新指定元素 set(int index, E element)
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = Lists.newArrayListWithExpectedSize(20);
arrayList.add("hello");
arrayList.set(0, "world");
}
}
set(int index, E element) 方法源代碼如下：
/**
* Replaces the element at the specified position in this list with
* the specified element.
* 用指定的元素替換此list中指定位置的元素
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
set(int index, E element) 方法時間複雜度
set(int index, E element) 方法時間複雜度為 O(1)
2.5 ArrayList 擷取元素
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = Lists.newArrayListWithExpectedSize(20);
arrayList.add("hello");
arrayList.get(0);
}
}
get(int index) 方法源代碼如下：
/**
* Returns the element at the specified position in this list.
* 傳回此list中指定位置的元素。
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
get(int index) 方法時間複雜度
get(int index) 方法時間複雜度為 O(1)
2.6 ArrayList 周遊的幾種方式
2.6.1 fori 周遊 ArrayList
Fori 周遊 ArrayList 的優缺點：
**優點：**可以取到下标
**缺點：**代碼比較繁瑣
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = Lists.newArrayListWithExpectedSize(20);
for (int i = 0; i < arrayList.size(); i ++) {
System.out.println(arrayList.get(i))
}
}
}
2.6.2 foreach 周遊 ArrayList
Foreach 周遊 ArrayList 的優缺點：
優點： 代碼相比 fori 方法更加簡潔
缺點： 無法擷取目前元素的下标
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = Lists.newArrayListWithExpectedSize(20);
for (String item : arrayList) {
System.out.println(item);
}
}
}
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = Lists.newArrayListWithExpectedSize(20);
arrayList.forEach(a -> {
System.out.println(a);
});
}
}
2.6.3 Iterator 疊代器周遊 ArrayList
iterator 周遊 ArrayList 的優缺點：
優點： 可以在周遊時進行元素移除操作
缺點： 無法擷取目前元素的下标
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
Iterator iterator = arrayList.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
Iterator iterator = arrayList.iterator();
for (Iterator item = iterator; item.hasNext(); ) {
System.out.println(item.next());
}
}
}
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
ListIterator<String> iterator = arrayList.listIterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
while (iterator.hasPrevious()) {
System.out.println(iterator.previous());
}
}
}
2.6.4 stream 流周遊 ArrayList
class ArrayListTest {
public void static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
arrayList.stream().forEach(item -> {
System.out.println(item);
});
}
}
2.6.5 parallelStream() 周遊 ArrayList
class ArrayListTest {
public void static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
arrayList.parallelStream().forEach(item -> {
System.out.println(item);
});
}
}
2.7 ArrayList 元素移除
2.7.1 移除指定下标的元素 remove(int index)
移除指定下标位置的元素。将其所有後續元素向左移動，将最後一個元素設定為 null 以便 GC
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
arrayList.add("hello");
arrayList.remove(0);
}
}
2.7.2 移除指定元素第一次出現的元素
從集合中删除第一次出現的指定元素。如果集合不包含該元素，則保持不變。
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
arrayList.add("hello");
arrayList.remove("hello");
}
}
remove(Object o) 方法的源代碼如下：
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
* 從此list中删除第一次出現的指定元素。如果list不包含該元素，則保持不變。更正式地，
* 删除具有最低索引 i 的元素，使得 o==null ? get(i)==null : o.equals(get(i))。
* 如果此list包含指定的元素，則傳回 true。
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
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
}
2.7.3 從集合中删除包含在指定集合中的所有元素 removeAll(Collection<?> c)
@TODO
2.8 ArrayList 擴容和邊界問題
初始化一個空 ArrayList 對象時預設容量為 0 ，在第一次插入元素時擴容，預設擴容為 10，若在此擴容，則為上次容量的 1.5 倍。
ArrayList 最小容量為 0，最大容量根據 JVM 平台的不同且在 JVM 記憶體足夠的情況下，大多接近于 Integer.MAX_VALUE，HotSpot VM 最大容量為 Integer.MAX_VALUE。超過最大容量時将最大容量設定為 Integer.MAX_VALUE。
擴容相關源代碼：
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(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
* 增加容量以確定它至少可以容納由最小容量參數指定的元素數量。
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code - 預防溢出
// oldCapacity 大小等于 elementData.length，元素數量
int oldCapacity = elementData.length;
// 新的 capacity 為 oldCapacity + (oldCapacity >> 1)
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果 newCapacity 小于 minCapacity，則将 minCapacity 指派給 newCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果 newCapacity 的值大于 MAX_ARRAY_SIZE-(Integer.MAX_VALUE - 8)，則啟用 hugeCapacity，hugeCapacity 允許最大容量大小為 Integer.MAX_VALUE
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);
}
/**
* list 大容量允許存儲元素的個數，Integer.MAX_VALUE
* @param minCapacity
* @return
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow - 溢出
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
2.9 ArrayList 線程安全問題
ArrayList 實作不同線程同步的，如果多個線程同時通路一個 ArrayList 執行個體，并且至少有一個線程在結構上修改了集合，它必須在外部同步(結構修改是添加或删除一個或多個元素，或顯式調整後備數組大小的任何操作；僅設定元素的值不是結構修改)；這通常是通過同步一些自然封裝的對象來實作的。
使用 Collections#synchronizedList 方法包裝 ArrayList 以實作線程同步，這最好在建立時完成，以防止對集合的意外不同步通路：
使用 CopyOnWriteArrayList 實作同步對象：
CopyOnWriteArrayList 中元素結構修改時是加鎖的，修改時進行 copy。讀的時候不需要加鎖，如果讀的時候有多個線程正在想 CopyOnWriteArrayList 添加資料，讀還是會讀到舊的資料，因為鎖的時候不會鎖住舊的 CopyOnWriteArrayList。有點像 ThreadLocal 。
2.10 ArrayList 總結
- 建立ArrayList執行個體對象時最好根據業務資料量指定初始容量，防止擴容影響性能；
- 在周遊集合時隻允許在 Iterator 疊代器中移除元素，否則會報錯 ConcurrentModificationException 異常；
- 多線程操作時請手動保證線程同步(Collections、CopyOnWriteArrayList)；