寫在前面
數(shù)據(jù)結(jié)構(gòu)在面試中基本都是常問的脱盲，但是一般開發(fā)中基本上都是在使用沒有去關(guān)心過怎么實現(xiàn)的闽烙。
在數(shù)據(jù)結(jié)構(gòu)中蝗敢，鏈表是一種線性存儲結(jié)構(gòu)捷泞，也就是常說的線性表。
概念：線性表前普，是數(shù)據(jù)結(jié)構(gòu)中的一種數(shù)據(jù)存儲結(jié)構(gòu)肚邢，數(shù)據(jù)元素之間具有“一對一”的邏輯關(guān)系∈们洌可以理解為把所有數(shù)據(jù)用一根線串起來骡湖，在存儲到物理空間中。
順序表ArrayList
概念：將數(shù)據(jù)依次存儲在連續(xù)的整塊物理空間中峻厚，這種存儲結(jié)構(gòu)稱為順序存儲結(jié)構(gòu)（簡稱順序表）响蕴。類似下圖用一個線把他們連接起來，形成一條線性的結(jié)構(gòu)惠桃。
ArrayList就是屬于這樣的一種浦夷。
ArrayList是基于數(shù)組實現(xiàn)的，數(shù)組是一種最簡單的數(shù)據(jù)結(jié)構(gòu)辜王，在使用時必須要給它創(chuàng)建大小劈狐，在日常開發(fā)中，往往我們是不知道給數(shù)組分配多大空間的呐馆，如果數(shù)組空間分配多了肥缔，內(nèi)存浪費，分配少了汹来，裝不下续膳。而ArrayList在使用時可以添加多個元素切不需要指定大小，因為ArrayList是動態(tài)擴容的收班。
類的繼承關(guān)系
源碼分析
類的屬性
/**
* 默認初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
*ArrayList 實際數(shù)據(jù)存儲的一個數(shù)組
*存儲ArrayList的元素的數(shù)組緩沖區(qū)坟岔。 ArrayList的容量是此數(shù)組緩沖區(qū)的長度。
*添加第一個元素時摔桦，任何具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都將擴展為DEFAULT_CAPACITY社付。
*/
transient Object[] elementData;
/**
* 共享的空數(shù)組實例，用于默認大小的空實例
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* elementData 的大小
*/
private int size;
類的構(gòu)造函數(shù)
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
new ArrayList()做了什么
public class TestClient {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
Integer capacity = getCapacity(list);
System.out.println("沒添加元素時的容量：" + capacity);
System.out.println("沒添加元素時的大小：" + list.size());
list.add("添加元素");
capacity = getCapacity(list);
System.out.println("添加1個元素時的容量：" + capacity);
System.out.println("添加1個元素時的大信缚А：" + list.size());
}
/**
* 通過反射獲取list的容量
*
* @param list
* @return
*/
public static Integer getCapacity(List<String> list) {
Integer length = null;
Class c = list.getClass();
Field f;
try {
f = c.getDeclaredField("elementData");
f.setAccessible(true);
Object[] o = (Object[]) f.get(list);
length = o.length;
} catch (NoSuchFieldException e) {
e.printStackTrace();
} catch (IllegalAccessException e) {
e.printStackTrace();
}
return length;
}
}
打印結(jié)果
沒添加元素時的容量：0
沒添加元素時的大屑拖丁：0
添加1個元素時的容量：10
添加1個元素時的大小：1
因此扛或，當(dāng)new ArrayList()時绵咱，默認會有一個空的Object空數(shù)組，在沒有添加有元素的時候熙兔，其初始化容量是0悲伶，只有當(dāng)添加第一個元素的時候，容量才會設(shè)置成10住涉。
基本方法
添加元素add(E e)
/**
* 將指定的元素追加到此列表的末尾
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1);
//直接賦值
elementData[size++] = e;
return true;
}
add(int index, E element)
在指定索引位置添加元素
String[] elementData = {"1", "2", "3", "4", "5", "6", "7", "8"};
int index = 4;
//從下標(biāo)為4的位置開始復(fù)制麸锉，復(fù)制的長度為8-4=4(復(fù)制"5", "6", "7", "8")，從下標(biāo)為4+1=5的位置開始替換為"5", "6", "7", "8"
System.arraycopy(elementData, index, elementData, index+1, elementData.length-index);
ArrayList 擴容機制
ensureExplicitCapacity(int minCapacity)
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//如果其元素數(shù)量大于其容量舆声，則進行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
grow(int minCapacity)
/**
* 擴容
* @param minCapacity
*/
private void grow(int minCapacity) {
//原來的容量
int oldCapacity = elementData.length;
//新的容量 通過位運算右移一位 如花沉，默認為10 10>>1=5 右移過程：10的二進制為 1010 右移1位->0101 轉(zhuǎn)十進制->5
//可以理解為oldCapacity >> 1 == oldCapacity/2 再加上原來的長度就擴容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果大于ArrayList 可以容許的最大容量，則設(shè)置為最大容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
想了解位運算的可以看看這篇文章
ArrayList 的內(nèi)部實現(xiàn)媳握，其實是用一個對象數(shù)組進行存放具體的值碱屁，然后用一種擴容的機制掂咒，進行數(shù)組的動態(tài)增長椿胯。
其擴容機制可以理解為，如果元素的個數(shù)量瓜，大于其容量打毛，則把其容量擴展為原來容量的1.5倍柿赊。
拓展延伸
- ArrayList的大小是如何自動增加的？
- 什么情況下你會使用ArrayList幻枉？
- 在索引中ArrayList的增加或者刪除某個對象的運行過程碰声？效率很低嗎？解釋一下為什么熬甫？
- ArrayList如何順序刪除節(jié)點胰挑？
- ArrayList的遍歷方法？
