點擊上方「程式設計師面試圈」，選擇「置頂或者星標」
公眾號回復[ 資源 ] 領取888G學習資源
ArrayList結構圖ArrayList 是 java 集合框架中比較常用的數據結構了。繼承自 AbstractList，實現了 List 接口。底層基於數組實現容量大小動態變化。允許 null 的存在。同時還實現了 RandomAccess、Cloneable、Serializable 接口，所以ArrayList 是支持快速訪問、複製、序列化的。
ArrayList類簡介1、ArrayList是內部是以動態數組的形式來存儲數據的、知道數組的可能會疑惑：數組不是定長的嗎？這裡的動態數組不是意味著去改變原有內部生成的數組的長度、而是保留原有數組的引用、將其指向新生成的數組對象、這樣會造成數組的長度可變的假象。
2、ArrayList具有數組所具有的特性、通過索引支持隨機訪問、所以通過隨機訪問ArrayList中的元素效率非常高、但是執行插入、刪除時效率比較地下、具體原因後面有分析。
3、ArrayList實現了AbstractList抽象類、List接口、所以其更具有了AbstractList和List的功能、前面我們知道AbstractList內部已經實現了獲取Iterator和ListIterator的方法、所以ArrayList只需關心對數組操作的方法的實現、
4、ArrayList實現了RandomAccess接口、此接口只有聲明、沒有方法體、表示ArrayList支持隨機訪問。
5、ArrayList實現了Cloneable接口、此接口只有聲明、沒有方法體、表示ArrayList支持克隆。
6、ArrayList實現了Serializable接口、此接口只有聲明、沒有方法體、表示ArrayList支持序列化、即可以將ArrayList以流的形式通過ObjectInputStream/ObjectOutputStream來寫/讀。
基礎屬性ArrayList部分源碼如下：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
private int size;
//...省略部分代碼
}
如上代碼中為ArrayList的主要屬性:
DEFAULT_CAPACITY：默認容量，即為初始值大小
EMPTY_ELEMENTDATA：共享的空數組，用於初始化空實例
elementData：ArrayList內部結構，是一個Object[]類型的數組
size：數組長度大小
構造方法如下為ArrayList的構造方法:
1.public ArrayList(int initialCapacity)
2.public ArrayList()
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);
}
1.構造方法1，表示接受指定地容量值，初始化創建數組，建議在可估算數組大小時,創建ArrayList可指定
2.構造方法2，是默認的構造方法，它將創建一個空數組
3.構造方法3，接收一個Collection的實體，將該Collection實體轉換為ArrayList對象
主幹流程1.添加指定元素代碼如下
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
可以看到實際上只有3行代碼，其流程主要如下：
1.擴容 (這裡便解釋了，在介紹時提出的問題)：主要源碼如下
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 static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
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);
}
1·擴容的大小為3/2倍原數組長度
2.若值newCapacity比傳入值minCapacity還要小，則使用傳入minCapacity，若newCapacity比設定的最大數組容量大，則使用最大整數值
3.實際擴容，使用了Arrays.copyof(elementData, newCapacity) (此處有兩個問題 1.為啥擴容是原來的3/2倍原數組的長度? 2.調用Arrays.copyOf(elementData, newCapacity)方法具體做了什麼操作? )
2.賦值：將添加的值放置到size++的位置上3.返回：返回true2.添加指定元素到指定的位置上代碼如下:
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++;
}
其流程為:
常見問題1.問題描述在使用ArrayList比較常見的一個問題就是在遍歷ArrayList的時候調用remove()方法進行元素的刪除操作,從而得到意想不到的結果，本人在開發過程中也遇到過這樣的問題，所以在這裡提出了，希望能夠幫助到大家。
2.實例及分析如下代碼中，在遍歷List時，調用了remove方法，刪除元素a
//arrayList中的值為 [a,a,c,a,a]
for (int i = 0; i < arrayList.size(); i++) {
if (arrayList.get(i) == "a") {
arrayList.remove(i);
}
}
System.out.println(arrayList);
這段代碼看似解決了刪除列表中所有的a元素，但是刪除後得出List的結果為[a, c, a]，為什麼這種方式沒有達到想要的效果，其實仔細分析後會發現，在調用remove()方法時List的長度會發生變化而且元素的位置會發生移動，從而在遍歷時list實際上是變化的，例如
當i=0時，此時list中的元素為[a,a,c,a,a],
但當i=1時，此時List中的元素為[a,c,a,a],元素的位置發生了移動，從而導致在遍歷的過程中不能達到刪除的效果
3.解決方案通過上述的分析可以看出，出現問題的原因是元素的位置發生了移動，從而導致異常的結果 方案一、逆向遍歷List刪除,代碼如下，這種做法可行主要是因為remove()方法刪除index處的元素時，是將index+1到size-1索引處的元素前移，而逆向遍歷可以避免元素位置的移動
for (int i = arrayList.size()-1; i >=0 ; i--) {
if (arrayList.get(i) == "a") {
arrayList.remove(i);
}
}
System.out.println(arrayList);
方案二、使用迭代器中的remove方法，迭代器具體參考Iterator詳解，主要代碼如下(這種方式比較推薦)
Iterator<String> ite = arrayList.listIterator();
while (ite.hasNext()){
if(ite.next() == "a")
ite.remove();
}
System.out.println(arrayList);
手寫一個ArrayList自己手寫一個ArrayList,代碼如下：
public class MyArrayList<T> implements Iterable<T> {
private T[] theItems;
private int theSize;
private static final int DEAULT_CAPACITY=10;
public MyArrayList(){
theSize=0;
ensureCapacity(DEAULT_CAPACITY);
}
public void add(T data){
if(size()==theItems.length){
ensureCapacity(size()*2+1);
}
theItems[size()]=data;
theSize++;
}
public void add(int index,T data){
if(size()==theItems.length){
ensureCapacity(size()*2+1);
}
for(int i=theSize;i>index;i--){
theItems[i]=theItems[i-1];
}
theItems[index]=data;
theSize++;
}
public T get(int index){
if(index<0|index>=size()){
throw new IndexOutOfBoundsException("index error");
}
return theItems[index];
}
public T remove(int index){
T removeData=get(index);
for(int i=index;i<size()-1;i++){
theItems[i]=theItems[i+1];
}
theSize--;
return removeData;
}
public int size(){
return theSize;
}
private void ensureCapacity(int newCapacity){
if(theSize>newCapacity){
return;
}
T[] old=theItems;
theItems= (T[]) new Object[newCapacity];
for(int i=0;i<size();i++){
theItems[i]=old[i];
}
}
@Override
public Iterator<T> iterator() {
return null;
}
@Override
public void forEach(Consumer<? super T> action) {
}
@Override
public Spliterator<T> spliterator() {
return null;
}
}
總結1.ArrayList是基於數組實現的，它的內存儲元素的數組為 elementData;elementData的聲明為：transient Object[] elementData;
2.ArrayList中EMPTYELEMENTDATA和DEFAULTCAPACITYEMPTY_ELEMENTDATA的使用；這兩個常量，使用場景不同。前者是用在用戶通過ArrayList(int initialCapacity)該構造方法直接指定初始容量為0時，後者是用戶直接使用無參構造創建ArrayList時。
3.ArrayList默認容量為10。調用無參構造新建一個ArrayList時，它的elementData = DEFAULTCAPACITYEMPTYELEMENTDATA, 當第一次使用 add() 添加元素時，ArrayList的容量會為 10。
4.ArrayList的擴容計算為 newCapacity = oldCapacity + (oldCapacity >> 1);且擴容並非是無限制的，有內存限制，虛擬機限制。
5.ArrayList的toArray()方法和subList()方法，在源數據和子數據之間的區別；
6.注意擴容方法ensureCapacityInternal()。ArrayList在每次增加元素（可能是1個，也可能是一組）時，都要調用該方法來確保足夠的容量。當容量不足以容納當前的元素個數時，就設置新的容量為舊的容量的1.5倍加1，如果設置後的新容量還不夠，則直接新容量設置為傳入的參數（也就是所需的容量），而後用Arrays.copyof()方法將元素拷貝到新的數組。從中可以看出，當容量不夠時，每次增加元素，都要將原來的元素拷貝到一個新的數組中，非常之耗時，也因此建議在事先能確定元素數量的情況下，才使用ArrayList，否則不建議使用。
參考資料https://blog.csdn.net/crave_shy/article/details/17436773
https://www.jianshu.com/p/92373a603d42
https://juejin.im/post/5a1bc1006fb9a045030fce0e
每一個「好看」，都是對我們最大的肯定！