前言
今天來介紹下ArrayList蕴忆，在集合框架整體框架一章中仗岖，我們介紹了List接口金麸，ArrayList繼承了AbstractList擎析，實現(xiàn)了List。ArrayList在工作中經(jīng)常用到挥下，所以要弄懂這個類是極其重要的揍魂。
構(gòu)造圖如下:
藍色線條：繼承
綠色線條：接口實現(xiàn)
正文
ArrayList簡介
ArrayList定義
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList 是一個數(shù)組隊列，相當(dāng)于 動態(tài)數(shù)組棚瘟。與Java中的數(shù)組相比现斋，它的容量能動態(tài)增長。它繼承于AbstractList偎蘸，實現(xiàn)了List, RandomAccess, Cloneable, java.io.Serializable這些接口庄蹋。
ArrayList 繼承了AbstractList，實現(xiàn)了List迷雪。它是一個數(shù)組隊列限书，提供了相關(guān)的添加、刪除章咧、修改蔗包、遍歷等功能。
ArrayList 實現(xiàn)了RandmoAccess接口慧邮，即提供了隨機訪問功能调限。RandmoAccess是java中用來被List實現(xiàn)，為List提供快速訪問功能的误澳。在ArrayList中耻矮，我們即可以通過元素的序號快速獲取元素對象；這就是快速隨機訪問忆谓。稍后裆装，我們會比較List的“快速隨機訪問”和“通過Iterator迭代器訪問”的效率。
ArrayList 實現(xiàn)了Cloneable接口，即覆蓋了函數(shù)clone()哨免，能被克隆茎活。
ArrayList 實現(xiàn)java.io.Serializable接口，這意味著ArrayList支持序列化琢唾，能通過序列化去傳輸载荔。
和Vector不同，ArrayList中的操作不是線程安全的采桃！所以懒熙，建議在單線程中才使用ArrayList，而在多線程中可以選擇Vector或者CopyOnWriteArrayList普办。
ArrayList屬性
顧名思義哈工扎，ArrayList就是用數(shù)組實現(xiàn)的List容器，既然是用數(shù)組實現(xiàn)衔蹲，當(dāng)然底層用數(shù)組來保存數(shù)據(jù)啦
// 保存ArrayList中數(shù)據(jù)的數(shù)組
private transient Object[] elementData;
// ArrayList中實際數(shù)據(jù)的數(shù)量
private int size;
ArrayList包含了兩個重要的對象：elementData 和 size肢娘。
(1) elementData 是"Object[]類型的數(shù)組"，它保存了添加到ArrayList中的元素舆驶。實際上蔬浙，elementData是個動態(tài)數(shù)組，我們能通過構(gòu)造函數(shù) ArrayList(int initialCapacity)來執(zhí)行它的初始容量為initialCapacity贞远；如果通過不含參數(shù)的構(gòu)造函數(shù)ArrayList()來創(chuàng)建ArrayList畴博，則elementData的容量默認是10。elementData數(shù)組的大小會根據(jù)ArrayList容量的增長而動態(tài)的增長蓝仲，具體的增長方式俱病，請參考源碼分析中的ensureCapacity()函數(shù)。
(2) size 則是動態(tài)數(shù)組的實際大小袱结。
ArrayList構(gòu)造函數(shù)
// ArrayList帶容量大小的構(gòu)造函數(shù)亮隙。
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
// 新建一個數(shù)組
this.elementData = new Object[initialCapacity];
}
// ArrayList構(gòu)造函數(shù)。默認容量是10垢夹。
public ArrayList() {
this(10);
}
// 構(gòu)造一個包含指定元素的list溢吻，這些元素的是按照Collection的迭代器返回的順序排列的
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
- 第一個構(gòu)造方法使用提供的initialCapacity來初始化elementData數(shù)組的大小。
- 第二個構(gòu)造方法調(diào)用第一個構(gòu)造方法并傳入?yún)?shù)10果元，即默認elementData數(shù)組的大小為10促王。
- 第三個構(gòu)造方法則將提供的集合轉(zhuǎn)成數(shù)組返回給elementData（返回若不是Object[]將調(diào)用Arrays.copyOf方法將其轉(zhuǎn)為Object[]）。
API方法摘要
ArrayList源碼解析(基于JDK1.6.0_45)
增加
/**
* 添加一個元素
*/
public boolean add(E e) {
// 進行擴容檢查
ensureCapacity( size + 1); // Increments modCount
// 將e增加至list的數(shù)據(jù)尾部而晒，容量+1
elementData[size ++] = e;
return true;
}
/**
* 在指定位置添加一個元素
*/
public void add(int index, E element) {
// 判斷索引是否越界蝇狼，這里會拋出多么熟悉的異常。倡怎。迅耘。
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: " +size);
// 進行擴容檢查
ensureCapacity( size+1); // Increments modCount
// 對數(shù)組進行復(fù)制處理贱枣，目的就是空出index的位置插入element，并將index后的元素位移一個位置
System. arraycopy(elementData, index, elementData, index + 1,
size - index);
// 將指定的index位置賦值為element
elementData[index] = element;
// list容量+1
size++;
}
/**
* 增加一個集合元素
*/
public boolean addAll(Collection<? extends E> c) {
//將c轉(zhuǎn)換為數(shù)組
Object[] a = c.toArray();
int numNew = a.length ;
//擴容檢查
ensureCapacity( size + numNew); // Increments modCount
//將c添加至list的數(shù)據(jù)尾部
System. arraycopy(a, 0, elementData, size, numNew);
//更新當(dāng)前容器大小
size += numNew;
return numNew != 0;
}
/**
* 在指定位置颤专，增加一個集合元素
*/
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: " + index + ", Size: " + size);
Object[] a = c.toArray();
int numNew = a.length ;
ensureCapacity( size + numNew); // Increments modCount
// 計算需要移動的長度（index之后的元素個數(shù)）
int numMoved = size - index;
// 數(shù)組復(fù)制纽哥，空出第index到index+numNum的位置，即將數(shù)組index后的元素向右移動numNum個位置
if (numMoved > 0)
System. arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 將要插入的集合元素復(fù)制到數(shù)組空出的位置中
System. arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
/**
* 數(shù)組容量檢查栖秕，不夠時則進行擴容
*/
public void ensureCapacity( int minCapacity) {
modCount++;
// 當(dāng)前數(shù)組的長度
int oldCapacity = elementData .length;
// 最小需要的容量大于當(dāng)前數(shù)組的長度則進行擴容
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
// 新擴容的數(shù)組長度為舊容量的1.5倍+1
int newCapacity = (oldCapacity * 3)/2 + 1;
// 如果新擴容的數(shù)組長度還是比最小需要的容量小春塌，則以最小需要的容量為長度進行擴容
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
// 進行數(shù)據(jù)拷貝，Arrays.copyOf底層實現(xiàn)是System.arrayCopy()
elementData = Arrays.copyOf( elementData, newCapacity);
}
}
刪除
/**
* 根據(jù)索引位置刪除元素
*/
public E remove( int index) {
// 數(shù)組越界檢查
RangeCheck(index);
modCount++;
// 取出要刪除位置的元素累魔，供返回使用
E oldValue = (E) elementData[index];
// 計算數(shù)組要復(fù)制的數(shù)量
int numMoved = size - index - 1;
// 數(shù)組復(fù)制，就是將index之后的元素往前移動一個位置
if (numMoved > 0)
System. arraycopy(elementData, index+1, elementData, index,
numMoved);
// 將數(shù)組最后一個元素置空（因為刪除了一個元素够滑，然后index后面的元素都向前移動了垦写，所以最后一個就沒用了），好讓gc盡快回收
// 不要忘了size減一
elementData[--size ] = null; // Let gc do its work
return oldValue;
}
/**
* 根據(jù)元素內(nèi)容刪除彰触，只刪除匹配的第一個
*/
public boolean remove(Object o) {
// 對要刪除的元素進行null判斷
// 對數(shù)據(jù)元素進行遍歷查找梯投，知道找到第一個要刪除的元素，刪除后進行返回况毅，如果要刪除的元素正好是最后一個那就慘了分蓖，時間復(fù)雜度可達O(n) 。尔许。么鹤。
if (o == null) {
for (int index = 0; index < size; index++)
// null值要用==比較
if (elementData [index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
// 非null當(dāng)然是用equals比較了
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++;
// 原理和之前的add一樣，還是進行數(shù)組復(fù)制味廊，將index后的元素向前移動一個位置蒸甜，不細解釋了，
int numMoved = size - index - 1;
if (numMoved > 0)
System. arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size ] = null; // Let gc do its work
}
/**
* 數(shù)組越界檢查
*/
private void RangeCheck(int index) {
if (index >= size )
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: " +size);
}
增加和刪除方法到這里就解釋完了余佛，代碼是很簡單柠新，主要需要特別關(guān)心的就兩個地方：1.數(shù)組擴容，2.數(shù)組復(fù)制辉巡，這兩個操作都是極費效率的恨憎，最慘的情況下(添加到list第一個位置，刪除list最后一個元素或刪除list第一個索引位置的元素)時間復(fù)雜度可達O(n)郊楣。
還記得上面那個坑嗎（為什么提供一個可以指定容量大小的構(gòu)造方法 ）憔恳？看到這里是不是有點明白了呢，簡單解釋下：如果數(shù)組初試容量過小净蚤，假設(shè)默認的10個大小喇嘱，而我們使用ArrayList的主要操作時增加元素，不斷的增加塞栅，一直增加者铜，不停的增加腔丧，會出現(xiàn)上面后果？那就是數(shù)組容量不斷的受挑釁作烟，數(shù)組需要不斷的進行擴容愉粤，擴容的過程就是數(shù)組拷貝System.arraycopy的過程，每一次擴容就會開辟一塊新的內(nèi)存空間和數(shù)據(jù)的復(fù)制移動拿撩，這樣勢必對性能造成影響衣厘。那么在這種以寫為主（寫會擴容，刪不會縮容）場景下压恒，提前預(yù)知性的設(shè)置一個大容量影暴，便可減少擴容的次數(shù)，提高了性能探赫。
上面兩張圖分別是數(shù)組擴容和數(shù)組復(fù)制的過程型宙，需要注意的是，數(shù)組擴容伴隨著開辟新建的內(nèi)存空間以創(chuàng)建新數(shù)組然后進行數(shù)據(jù)復(fù)制伦吠，而數(shù)組復(fù)制不需要開辟新內(nèi)存空間妆兑，只需將數(shù)據(jù)進行復(fù)制。
上面講增加元素可能會進行擴容毛仪，而刪除元素卻不會進行縮容搁嗓，如果在已刪除為主的場景下使用list，一直不停的刪除而很少進行增加箱靴，那么會出現(xiàn)什么情況腺逛？再或者數(shù)組進行一次大擴容后，我們后續(xù)只使用了幾個空間衡怀，會出現(xiàn)上面情況？當(dāng)然是空間浪費啦啦啦狈癞，怎么辦呢？
/**
* 將底層數(shù)組的容量調(diào)整為當(dāng)前實際元素的大小蝶桶，來釋放空間。
*/
public void trimToSize() {
modCount++;
// 當(dāng)前數(shù)組的容量
int oldCapacity = elementData .length;
// 如果當(dāng)前實際元素大小 小于 當(dāng)前數(shù)組的容量真竖，則進行縮容
if (size < oldCapacity) {
elementData = Arrays.copyOf( elementData, size );
}
更新
/**
* 將指定位置的元素更新為新元素
*/
public E set( int index, E element) {
// 數(shù)組越界檢查
RangeCheck(index);
// 取出要更新位置的元素，供返回使用
E oldValue = (E) elementData[index];
// 將該位置賦值為行的元素
elementData[index] = element;
// 返回舊元素
return oldValue;
}
查找
/**
* 查找指定位置上的元素
*/
public E get( int index) {
RangeCheck(index);
return (E) elementData [index];
}
是否包含
/**
* Returns <tt>true</tt> if this list contains the specified element.
* More formally, returns <tt>true</tt> if and only if this list contains
* at least one element <tt>e</tt> such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return <tt> true</tt> if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
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++)
if (o.equals(elementData [i]))
return i;
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
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;
}
contains主要是檢查indexOf战秋，也就是元素在list中出現(xiàn)的索引位置也就是數(shù)組下標(biāo)脂信，再看indexOf和lastIndexOf代碼是不是很熟悉癣蟋，沒錯狰闪，和public boolean remove(Object o) 的代碼一樣疯搅，都是元素null判斷，都是循環(huán)比較埋泵，不多說了幔欧。。丽声。但是要知道礁蔗，最差的情況（要找的元素是最后一個）也是很慘的。雁社。浴井。
容量判斷
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return size ;
}
/**
* Returns <tt>true</tt> if this list contains no elements.
*
* @return <tt> true</tt> if this list contains no elements
*/
public boolean isEmpty() {
return size == 0;
}
由于使用了size進行計數(shù)，發(fā)現(xiàn)list大小獲取和判斷真的好容易歧胁。
總結(jié)：
(01) ArrayList 實際上是通過一個數(shù)組去保存數(shù)據(jù)的滋饲。當(dāng)我們構(gòu)造ArrayList時厉碟；若使用默認構(gòu)造函數(shù)喊巍，則ArrayList的默認容量大小是10。
(02) 當(dāng)ArrayList容量不足以容納全部元素時箍鼓，ArrayList會重新設(shè)置容量：新的容量=“(原始容量x3)/2 + 1”崭参。
(03) ArrayList的克隆函數(shù)，即是將全部元素克隆到一個數(shù)組中款咖。
(04) ArrayList實現(xiàn)java.io.Serializable的方式何暮。當(dāng)寫入到輸出流時，先寫入“容量”铐殃，再依次寫入“每一個元素”海洼；當(dāng)讀出輸入流時，先讀取“容量”富腊，再依次讀取“每一個元素”坏逢。
ArrayList遍歷方式
ArrayList支持3種遍歷方式
(01) 第一種，通過迭代器遍歷赘被。即通過Iterator去遍歷是整。
Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}
(02) 第二種，隨機訪問民假，通過索引值去遍歷。
由于ArrayList實現(xiàn)了RandomAccess接口羊异，它支持通過索引值去隨機訪問元素。
Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
value = (Integer)list.get(i);
}
(03) 第三種秽晚，for循環(huán)遍歷赴蝇。如下：
Integer value = null;
for (Integer integ:list) {
value = integ;
}
下面通過一個實例句伶，比較這3種方式的效率考余，實例代碼(ArrayListRandomAccessTest.java)如下：
import java.util.*;
import java.util.concurrent.*;
/*
* @desc ArrayList遍歷方式和效率的測試程序楚堤。
*
* @author skywang
*/
public class ArrayListRandomAccessTest {
public static void main(String[] args) {
List list = new ArrayList();
for (int i=0; i<100000; i++)
list.add(i);
//isRandomAccessSupported(list);
iteratorThroughRandomAccess(list) ;
iteratorThroughIterator(list) ;
iteratorThroughFor2(list) ;
}
private static void isRandomAccessSupported(List list) {
if (list instanceof RandomAccess) {
System.out.println("RandomAccess implemented!");
} else {
System.out.println("RandomAccess not implemented!");
}
}
public static void iteratorThroughRandomAccess(List list) {
long startTime;
long endTime;
startTime = System.currentTimeMillis();
for (int i=0; i<list.size(); i++) {
list.get(i);
}
endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println("iteratorThroughRandomAccess：" + interval+" ms");
}
public static void iteratorThroughIterator(List list) {
long startTime;
long endTime;
startTime = System.currentTimeMillis();
for(Iterator iter = list.iterator(); iter.hasNext(); ) {
iter.next();
}
endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println("iteratorThroughIterator：" + interval+" ms");
}
public static void iteratorThroughFor2(List list) {
long startTime;
long endTime;
startTime = System.currentTimeMillis();
for(Object obj:list)
;
endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println("iteratorThroughFor2：" + interval+" ms");
}
}
運行結(jié)果：
iteratorThroughRandomAccess：3 ms
iteratorThroughIterator：8 ms
iteratorThroughFor2：5 ms
由此可見衅胀，遍歷ArrayList時滚躯，使用隨機訪問(即掸掏，通過索引序號訪問)效率最高丧凤，而使用迭代器的效率最低愿待！
ArrayList示例
本文通過一個實例(ArrayListTest.java)呼盆，介紹 ArrayList 中常用API的用法蚁廓。
import java.util.*;
/*
* @desc ArrayList常用API的測試程序
* @author skywang
* @email kuiwu-wang@163.com
*/
public class ArrayListTest {
public static void main(String[] args) {
// 創(chuàng)建ArrayList
ArrayList list = new ArrayList();
// 將“”
list.add("1");
list.add("2");
list.add("3");
list.add("4");
// 將下面的元素添加到第1個位置
list.add(0, "5");
// 獲取第1個元素
System.out.println("the first element is: "+ list.get(0));
// 刪除“3”
list.remove("3");
// 獲取ArrayList的大小
System.out.println("Arraylist size=: "+ list.size());
// 判斷l(xiāng)ist中是否包含"3"
System.out.println("ArrayList contains 3 is: "+ list.contains(3));
// 設(shè)置第2個元素為10
list.set(1, "10");
// 通過Iterator遍歷ArrayList
for(Iterator iter = list.iterator(); iter.hasNext(); ) {
System.out.println("next is: "+ iter.next());
}
// 將ArrayList轉(zhuǎn)換為數(shù)組
String[] arr = (String[])list.toArray(new String[0]);
for (String str:arr)
System.out.println("str: "+ str);
// 清空ArrayList
list.clear();
// 判斷ArrayList是否為空
System.out.println("ArrayList is empty: "+ list.isEmpty());
}
}
運行結(jié)果：
the first element is: 5
Arraylist size=: 4
ArrayList contains 3 is: false
next is: 5
next is: 10
next is: 2
next is: 4
str: 5
str: 10
str: 2
str: 4
ArrayList is empty: true
總結(jié)
ArrayList和LinkedList的區(qū)別
- ArrayList是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)腿时，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)批糟。
- 對于隨機訪問get和set，ArrayList覺得優(yōu)于LinkedList盛末，因為LinkedList要移動指針悄但。
- 對于新增和刪除操作add和remove檐嚣，LinkedList比較占優(yōu)勢嚎京，因為ArrayList要移動數(shù)據(jù)隐解。
ArrayList和Vector的區(qū)別
- Vector和ArrayList幾乎是完全相同的,唯一的區(qū)別在于Vector是同步類(synchronized)厢漩，屬于強同步類溜嗜。因此開銷就比ArrayList要大炸宵，訪問要慢谷扣。正常情況下,大多數(shù)的Java程序員使用ArrayList而不是Vector,因為同步完全可以由程序員自己來控制会涎。
- Vector每次擴容請求其大小的2倍空間末秃，而ArrayList是1.5倍。
- Vector還有一個子類Stack.
參考
該文為本人學(xué)習(xí)的筆記惰匙，方便以后自己跳槽前復(fù)習(xí)项鬼。參考網(wǎng)上各大帖子，取其精華整合自己的理解而成鸠真。集合框架源碼面試經(jīng)常會問弧哎，所以解讀源碼十分必要,希望對你有用撤嫩。
Java集合框架：ArrayList
Java 集合系列03之 ArrayList詳細介紹(源碼解析)和使用示例
給jdk寫注釋系列之jdk1.6容器(1)-ArrayList源碼解析
java容器類源碼分析——ArrayList
整理的集合框架思維導(dǎo)圖
個人整理的Java集合框架思維導(dǎo)圖序攘，動態(tài)維護程奠。導(dǎo)出的圖片無法查看備注的一些信息祭钉，所以需要源文件的童鞋可以關(guān)注我個人主頁上的公眾號慌核，回復(fù)Java集合框架即可獲取源文件垮卓。
一直覺得自己寫的不是技術(shù)粟按，而是情懷灭将，一篇篇文章是自己這一路走來的痕跡】站担靠專業(yè)技能的成功是最具可復(fù)制性的姑裂，希望我的這條路能讓你少走彎路，希望我能幫你抹去知識的蒙塵欣鳖，希望我能幫你理清知識的脈絡(luò)泽台，希望未來技術(shù)之巔上有你也有我怀酷。
