先看再點贊，給自己一點思考的時間，思考過后請毫不猶豫微信搜索【沉默王二】，關注這個長發飄飄卻靠才華茍且的程式員，
本文 GitHub github.com/itwanger 已收錄，里面還有技術大佬整理的面試題，以及二哥的系列文章，
關于 Java 基礎、Java 面向物件編程、Java 字串、Java 陣列等方面的知識點已經可以告一段落了，小伙伴們可以在「沉默王二」公眾號后臺回復「小白」獲取第二版手冊，覺得不錯的話，請隨手轉發給身邊的小伙伴，贈人玫瑰，手有余香哈，
那么接下來，我開始肝 Java 集合方面的文章了，小伙伴們請默默為我鼓個掌，我能聽得到，真的，別吝嗇你的掌聲，響起來，第一篇，必須得從 ArrayList 開始，畢竟 ArrayList 可以稱得上是集合方面最常用的類了，估計沒有之一，
ArrayList 實作了 List 介面，是基于陣列實作的，小伙伴們都知道，陣列的大小是固定的，創建的時候指定了大小，就不能再調整了，如果陣列滿了，就不能再添加任何元素了，ArrayList 是陣列很好的替代方案，它提供了比陣列更豐富的預定義方法（增刪改查），并且大小是可以根據元素的多少進行自動調整的，非常靈活，
準備在 ArrayList 的第四個位置（下標為 3）上添加一個元素 55，
此時 ArrayList 中第五個位置以后的元素將會向后移動，
準備把 23 從 ArrayList 中移除，
此時下標為 7、8、9 的元素往前挪，
01、如何創建一個 ArrayList
ArrayList<String> alist = new ArrayList<String>();
可以通過上面的陳述句來創建一個字串型別的 ArrayList（通過尖括號來限定 ArrayList 中元素的型別，如果嘗試添加其他型別的元素，將會產生編譯錯誤），更簡化的寫法如下：
List<String> alist = new ArrayList<>();
由于 ArrayList 實作了 List 介面，所以 alist 變數的型別可以是 List 型別；new 關鍵字宣告后的尖括號中可以不再指定元素的型別，因為編譯器可以通過前面尖括號中的型別進行智能推斷，
如果非常確定 ArrayList 中元素的個數，在創建的時候還可以指定初始大小，
List<String> alist = new ArrayList<>(20);
這樣做的好處是，可以有效地避免在添加新的元素時進行不必要的擴容，但通常情況下，我們很難確定 ArrayList 中元素的個數，因此一般不指定初始大小，
02、向 ArrayList 中添加一個元素
可以通過 add() 方法向 ArrayList 中添加一個元素，如果不指定下標的話，就默認添加在末尾，
alist.add("沉默王二");
感興趣的小伙伴可以研究一下 add() 方法的原始碼，它在添加元素的時候會執行 grow() 方法進行擴容，這個是面試官特別喜歡考察的一個重點，
下面是 add(E e) 方法的原始碼：
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
呼叫了私有的 add(E e, Object[] elementData, int s) 方法：
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
然后呼叫了非常關鍵的 grow(int minCapacity) 方法：
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
如果創建 ArrayList 的時候沒有指定初始大小，那么 ArrayList 的初始大小就是 DEFAULT_CAPACITY：
private static final int DEFAULT_CAPACITY = 10;
可以容納 10 個元素，
還可以通過 add(int index, E element) 方法把元素添加到指定的位置：
alist.add(0, "沉默王三");
add(int index, E element) 方法的原始碼如下：
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
該方法會呼叫到一個非常重要的本地方法 System.arraycopy()，它會對陣列進行復制（要插入位置上的元素往后復制，參照文章一開頭提到的兩張圖片），
03、更新 ArrayList 中的元素
可以使用 set() 方法來更改 ArrayList 中的元素，需要提供下標和新元素，
alist.set(0, "沉默王四");
原來 0 位置上的元素為“沉默王三”，現在將其更新為“沉默王四”，
來看一下 set() 方法的原始碼：
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
該方法會先對指定的下標進行檢查，看是否越界，然后替換新值并回傳舊值，
04、洗掉 ArrayList 中的元素
remove(int index) 方法用于洗掉指定下標位置上的元素，remove(Object o) 方法用于洗掉指定值的元素，
alist.remove(1);
alist.remove("沉默王四");
先來看 remove(int index) 方法的原始碼：
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
該方法回傳要洗掉的元素，真正的洗掉操作在 fastRemove(es, index) 方法中，
再來看 remove(Object o) 方法的原始碼：
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
該方法通過 break label 的方式找到要洗掉元素（null 的時候使用 == 運算子判斷，非 null 的時候使用 equals() 方法，意味著如果有相同元素時，洗掉第一個）的下標，然后呼叫 fastRemove() 方法，
既然都呼叫了 fastRemove() 方法，那就繼續來跟蹤一下原始碼：
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
當洗掉的是末尾的元素時，不需要復制陣列，直接把末尾的元素賦值為 null 即可；否則的話，就需要呼叫 System.arraycopy() 對陣列進行復制，參照文章一開頭提到的第三張、第四張圖片，
05、查找 ArrayList 中的元素
如果要正序查找一個元素，可以使用 indexOf() 方法；如果要倒序查找一個元素，可以使用 lastIndexOf() 方法，
alist.indexOf("沉默王二");
alist.lastIndexOf("沉默王二");
來看一下 indexOf() 方法的原始碼：
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = start; i < end; i++) {
if (es[i] == null) {
return i;
}
}
} else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
return i;
}
}
}
return -1;
}
如果元素為 null 的時候使用“==”運算子，否則使用 equals() 方法——該方法不是 null 安全的，
lastIndexOf() 方法和 indexOf() 方法類似，不過遍歷的時候從最后開始，
contains() 方法可以判斷 ArrayList 中是否包含某個元素，其內部呼叫了 indexOf() 方法：
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
如果 ArrayList 中的元素是經過排序的，就可以使用二分查找法，效率更快，
Collections 類的 sort() 方法可以對 ArrayList 進行排序，該方法會按照字母順序對 String 型別的串列進行排序，如果是自定義型別的串列，還可以指定 Comparator 進行排序，
List<String> copy = new ArrayList<>(alist);
copy.add("a");
copy.add("c");
copy.add("b");
copy.add("d");
Collections.sort(copy);
System.out.println(copy);
輸出結果如下所示：
[a, b, c, d]
排序后就可以使用二分查找法了：
int index = Collections.binarySearch(copy, "b");
06、最后
關于 ArrayList，就先介紹這么多吧，通過原始碼的角度，我想小伙伴們一定對 ArrayList 有了更深刻的印象，
簡單總結一下 ArrayList 的時間復雜度，方便后面學習 LinkedList 時作為一個對比，
1）通過下標（也就是 get(int index)）訪問一個元素的時間復雜度為 O(1)，因為是直達的，無論資料增大多少倍，耗時都不變，
2）添加一個元素（也就是 add()）的時間復雜度為 O(1)，因為直接添加到末尾，
3）洗掉一個元素的時間復雜度為 O(n)，因為要遍歷串列，資料量增大幾倍，耗時也增大幾倍，
4）查找一個未排序的串列時間復雜度為 O(n)，因為要遍歷串列；查找排序過的串列時間復雜度為 O(log n)，因為可以使用二分查找法，當資料增大 n 倍時，耗時增大 logn 倍（這里的 log 是以 2 為底的，每找一次排除一半的可能），
我是沉默王二，一枚有顏值卻靠才華茍且的程式員，關注即可提升學習效率，別忘了三連啊，點贊、收藏、留言，我不挑，奧利給，
注：如果文章有任何問題，歡迎毫不留情地指正，
很多讀者都同情我說，“二哥，你像母豬似的日更原創累不累？”我只能說寫作不易，且行且珍惜啊，關鍵是我真的喜歡寫作，最后，歡迎微信搜索「沉默王二」第一時間閱讀，回復「簡歷」更有阿里大佬的簡歷模板，本文 GitHub github.com/itwanger 已收錄，歡迎 star，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/145710.html
標籤：Java
下一篇：虛擬機位元組碼指令表