概念
ArrayList就是一個底層是數(shù)組形式組成的有序集合，允許重復(fù)數(shù)據(jù)备蚓，允許數(shù)據(jù)為null,但是非線程安全砌创，讓我們看看源碼
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
我們看到ArrayList實現(xiàn)了RondomAccess接口蚕钦，這也就意味著該類支持快速隨機訪問
以下是ArrayList的主要成員變量
private static final int DEFAULT_CAPACITY = 10;//默認(rèn)初始容量為10
private static final Object[] EMPTY_ELEMENTDATA = {};//定義一個空數(shù)組實例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;//存放數(shù)據(jù)的數(shù)組
private int size;//數(shù)組的大小
注意一下，elementData是由transient修飾的逻恐，ArrayList繼承了Serializable,實現(xiàn)了序列化，elementData是一個緩存數(shù)組,它通常會預(yù)留一些容量峻黍，在很多時候复隆，這個數(shù)組都有很多空的數(shù)據(jù)，所以如果存進(jìn)內(nèi)存姆涩，會占用多余的內(nèi)存空間挽拂，故使用transient反序列化。
創(chuàng)建
當(dāng)我們new一個ArrayList時骨饿，有三種構(gòu)造方式：
1.無參構(gòu)造器亏栈，默認(rèn)創(chuàng)建一個空的數(shù)組
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
當(dāng)添加了第一條數(shù)據(jù)后台腥，elementData初始容量為10；
2.指定集合的大小
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
如圖仑扑，指定初始容量時览爵，elementData的大小為指定值，當(dāng)我們知道集合所需容量大小時镇饮，可以在創(chuàng)建集合時直接指定它的大小
3.構(gòu)造一個包含指定集合的Arraylist
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
添加
先讓我們看一段代碼
ArrayList<String> list = new ArrayList<>();
list.add("hello");
list.add("world");
讓我們看一下源碼蜓竹，看看底層是怎么做的
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 索引增加
elementData[size++] = e;
return true;
}
ensureCapacityInternal()是擴容方法，先不管储藐，實際添加數(shù)據(jù)就是直接在elementData數(shù)組的后面添加了數(shù)據(jù)俱济。
那么看看擴容的操作
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);
}
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
首先判斷當(dāng)前數(shù)組是否為空，若當(dāng)前數(shù)組不為空钙勃，且當(dāng)前數(shù)組的長度小于插入數(shù)據(jù)之后的長度蛛碌，則調(diào)用grow()方法進(jìn)行擴容，我們從int newCapacity = oldCapacity + (oldCapacity >> 1)可以看出辖源，擴容之后的容量為之前的1.5倍蔚携，然后進(jìn)行Arrays.copy()操作將之前的數(shù)組中的數(shù)據(jù)復(fù)制到新數(shù)組。
刪除
我們一般常用到的刪除方式分別是指定下標(biāo)刪除克饶，和指定內(nèi)容刪除酝蜒，讓我們看看源代碼是怎么做的
/*
* 通過制定下標(biāo)刪除
*/
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
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
return oldValue;
}
/*
* 通過指定對象刪除
*/
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 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
}
這兩種刪除的方式都差不多，都是要把指定元素后面位置的所有元素矾湃，利用System.arraycopy方法整體向前移動一個位置亡脑，最后一個位置的元素指定為null，這樣讓gc可以去回收它
插入
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++;
}
插入元素的時候邀跃，也是要利用System.arraycopy()整體往后移霉咨，將元素放在指定位置，數(shù)組的大小增1
總結(jié)
ArrayList底層是用數(shù)組實現(xiàn)的拍屑，具有動態(tài)擴容特性途戒。初始容量為10，擴容增量為原容量的1.5
ArrayList具有隨機訪問特性丽涩，查找速度快
ArrayList插入和刪除操作效率比較低棺滞，因為涉及到元素復(fù)制，當(dāng)需要復(fù)制的元素過多時矢渊，比較耗費性能继准。
因此，ArrayList比較適合順序添加矮男、隨機訪問的場景移必。
小插曲：System.arraycopy()和Arrays.copyOf()的方法的區(qū)別？
以下是它們的源碼：
/*
* System.arraycopy
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
/*
* Arrays.copyOf
*/
public static short[] copyOf(short[] original, int newLength) {
short[] copy = new short[newLength];
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
arraycopy()是native方法毡鉴，所以看不到arraycopy()的具體實現(xiàn)崔泵，哭(???)
我們看到Arrays.copy()的最后還是調(diào)用了System.arraycopy(),Arrays.copy()限制了復(fù)制的范圍只能是整個數(shù)組
