一、概念
類定義：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
- 繼承了AbstractList抽象類，實現(xiàn)了List接口，擁有一組List通用的操作。
- 實現(xiàn)了RandomAccess接口，可進行隨機訪問。
- 實現(xiàn)了Cloneable接口，可進行淺層次拷貝。
- 實現(xiàn)了Serializable接口，可進行序列化。
特點：
- 長于隨機訪問元素。
- 在List中間插入和刪除元素較慢。
二、使用
//TestArrayList
public class TestArrayList {
private static final String TAG = "TestArrayList";
private ArrayList<String> list = new ArrayList<>();
public void testAdd() {
list.add("a");
list.add("b");
list.add("c");
Log.d(TAG, "zwm, add list: " + list);
}
public void testGet() {
Log.d(TAG, "zwm, get index 2: " + list.get(2));
}
public void testAdd2() {
list.add(0, "ii");
list.add(1, "jj");
list.add(2, "kk");
Log.d(TAG, "zwm, add index list: " + list);
}
public void testAddAll() {
ArrayList<String> temp = new ArrayList<>();
temp.add("lll");
temp.add("mmm");
temp.add("nnn");
list.addAll(temp);
Log.d(TAG, "zwm, addAll list: " + list);
}
public void testAddAll2() {
ArrayList<String> temp = new ArrayList<>();
temp.add("xxxx");
temp.add("zzzz");
temp.add("yyyy");
temp.add("zzzz");
list.addAll(0, temp);
Log.d(TAG, "zwm, addAll index list: " + list);
}
public void testIndexOf() {
Log.d(TAG, "zwm, indexOf zzzz: " + list.indexOf("zzzz"));
}
public void testLastIndexOf() {
Log.d(TAG, "zwm, lastIndexOf zzzz: " + list.lastIndexOf("zzzz"));
}
public void testClone() {
ArrayList<String> cloneList = (ArrayList)list.clone();
Log.d(TAG, "zwm, list.equals(cloneList): " + list.equals(cloneList));
Log.d(TAG, "zwm, list==cloneList: " + (list==cloneList));
}
public void testContains() {
Log.d(TAG, "zwm, contains zzzz: " + list.contains("zzzz"));
}
public void testContainsAll() {
ArrayList<String> temp = new ArrayList<>();
temp.add("xxxx");
temp.add("yyyy");
temp.add("zzzz");
Log.d(TAG, "zwm, containsAll: " + list.containsAll(temp));
}
public void testSize() {
Log.d(TAG, "zwm, size: " + list.size());
}
public void testClear() {
list.clear();
Log.d(TAG, "zwm, clear list: " + list);
}
public void testEmpty() {
Log.d(TAG, "zwm, isEmpty: " + list.isEmpty());
}
public void testIterator() {
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
Log.d(TAG, "zwm, iterator item: " + iterator.next());
}
}
public void testIterator2() {
ListIterator<String> iterator = list.listIterator();
while (iterator.hasNext()) {
String item = iterator.next();
Log.d(TAG, "zwm, listIterator item: " + item);
if(TextUtils.equals(item, "b")) {
Log.d(TAG, "zwm, remove b");
iterator.remove();
} else if(TextUtils.equals(item, "c")) {
Log.d(TAG, "zwm, update c to x");
iterator.set("x");
}
}
Log.d(TAG, "zwm, listIterator list: " + list);
Log.d(TAG, "zwm, next index: " + iterator.nextIndex());
Log.d(TAG, "zwm, previous index: " + iterator.previousIndex());
while(iterator.hasPrevious()) {
String item = iterator.previous();
Log.d(TAG, "zwm, listIterator item: " + item);
}
}
public void testIterator3() {
ListIterator<String> iterator = list.listIterator(2);
while (iterator.hasNext()) {
String item = iterator.next();
Log.d(TAG, "zwm, listIterator index item: " + item);
}
}
public void testRemove() {
Log.d(TAG, "zwm, remove a: " + list.remove("a"));
Log.d(TAG, "zwm, remove list: " + list);
}
public void testRemove2() {
Log.d(TAG, "zwm, remove index 3: " + list.remove(3));
Log.d(TAG, "zwm, remove index list: " + list);
}
public void testRemoveAll() {
ArrayList<String> temp = new ArrayList<>();
temp.add("a");
temp.add("b");
Log.d(TAG, "zwm, removeAll: " + list.removeAll(temp));
Log.d(TAG, "zwm, removeAll list: " + list);
}
public void testRetainAll() {
ArrayList<String> temp = new ArrayList<>();
temp.add("a");
temp.add("b");
temp.add("c");
Log.d(TAG, "zwm, retainAll: " + list.retainAll(temp));
Log.d(TAG, "zwm, retainAll list: " + list);
}
public void testSet() {
list.set(0, "sss");
Log.d(TAG, "zwm, set list: " + list);
}
public void testSubList() {
//以下注釋語句會拋出異常java.lang.ClassCastException: java.util.ArrayList$SubList cannot be cast to java.util.ArrayList
//ArrayList<String> subList = (ArrayList<String>)list.subList(1, 2);
List<String> subList = list.subList(1, 3);
Log.d(TAG, "zwm, subList: " + subList);
}
public void testEnsureCapacity() {
//在數(shù)據(jù)量過大的情況下初始化理想的ArryList容量，效率會明顯高于自動擴容
//所以在項目中有些業(yè)務處理時候對ArryList的長度有明顯的把控時 最好自定義其擴容方法來提高程序的執(zhí)行效率
Log.d(TAG, "zwm, ensureCapacity");
list.ensureCapacity(100);
}
public void testTrimToSize() {
//將ArrayList容量設置為實際大小
Log.d(TAG, "zwm, trimToSize");
list.trimToSize();
}
public void testToArray() {
Object[] arrays = list.toArray();
for(Object item : arrays) {
Log.d(TAG, "zwm, toArray item: " + item);
}
}
public void testToArray2() {
String[] param = new String[list.size()];
String[] result = list.toArray(param);
for(String item : param) {
Log.d(TAG, "zwm, toArray T param item: " + item);
}
for(String item : result) {
Log.d(TAG, "zwm, for result T result item: " + item);
}
}
}
//測試代碼
private void testMethod() {
Log.d(TAG, "zwm, testMethod");
TestArrayList testArrayList = new TestArrayList();
testArrayList.testAdd();
testArrayList.testAdd2();
testArrayList.testAddAll();
testArrayList.testAddAll2();
testArrayList.testGet();
testArrayList.testIndexOf();
testArrayList.testLastIndexOf();
testArrayList.testClone();
testArrayList.testContains();
testArrayList.testContainsAll();
testArrayList.testSize();
testArrayList.testClear();
testArrayList.testEmpty();
testArrayList.testAdd();
testArrayList.testIterator();
testArrayList.testIterator2();
testArrayList.testAdd();
testArrayList.testIterator3();
testArrayList.testEnsureCapacity();
testArrayList.testRemove();
testArrayList.testRemove2();
testArrayList.testRemoveAll();
testArrayList.testAdd();
testArrayList.testRetainAll();
testArrayList.testSet();
testArrayList.testSubList();
testArrayList.testTrimToSize();
testArrayList.testToArray();
testArrayList.testToArray2();
}
//輸出log
2019-08-02 18:31:06.908 zwm, testMethod
2019-08-02 18:31:06.911 zwm, add list: [a, b, c]
2019-08-02 18:31:06.912 zwm, add index list: [ii, jj, kk, a, b, c]
2019-08-02 18:31:06.912 zwm, addAll list: [ii, jj, kk, a, b, c, lll, mmm, nnn]
2019-08-02 18:31:06.913 zwm, addAll index list: [xxxx, zzzz, yyyy, zzzz, ii, jj, kk, a, b, c, lll, mmm, nnn]
2019-08-02 18:31:06.913 zwm, get index 2: yyyy
2019-08-02 18:31:06.913 zwm, indexOf zzzz: 1
2019-08-02 18:31:06.913 zwm, lastIndexOf zzzz: 3
2019-08-02 18:31:06.914 zwm, list.equals(cloneList): true
2019-08-02 18:31:06.914 zwm, list==cloneList: false
2019-08-02 18:31:06.914 zwm, contains zzzz: true
2019-08-02 18:31:06.914 zwm, containsAll: true
2019-08-02 18:31:06.914 zwm, size: 13
2019-08-02 18:31:06.914 zwm, clear list: []
2019-08-02 18:31:06.915 zwm, isEmpty: true
2019-08-02 18:31:06.915 zwm, add list: [a, b, c]
2019-08-02 18:31:06.915 zwm, iterator item: a
2019-08-02 18:31:06.915 zwm, iterator item: b
2019-08-02 18:31:06.915 zwm, iterator item: c
2019-08-02 18:31:06.915 zwm, listIterator item: a
2019-08-02 18:31:06.915 zwm, listIterator item: b
2019-08-02 18:31:06.915 zwm, remove b
2019-08-02 18:31:06.916 zwm, listIterator item: c
2019-08-02 18:31:06.916 zwm, update c to x
2019-08-02 18:31:06.916 zwm, listIterator list: [a, x]
2019-08-02 18:31:06.916 zwm, next index: 2
2019-08-02 18:31:06.916 zwm, previous index: 1
2019-08-02 18:31:06.916 zwm, listIterator item: x
2019-08-02 18:31:06.916 zwm, listIterator item: a
2019-08-02 18:31:06.916 zwm, add list: [a, x, a, b, c]
2019-08-02 18:31:06.917 zwm, listIterator index item: a
2019-08-02 18:31:06.917 zwm, listIterator index item: b
2019-08-02 18:31:06.917 zwm, listIterator index item: c
2019-08-02 18:31:06.917 zwm, ensureCapacity
2019-08-02 18:31:06.917 zwm, remove a: true
2019-08-02 18:31:06.917 zwm, remove list: [x, a, b, c]
2019-08-02 18:31:06.918 zwm, remove index 3: c
2019-08-02 18:31:06.918 zwm, remove index list: [x, a, b]
2019-08-02 18:31:06.918 zwm, removeAll: true
2019-08-02 18:31:06.918 zwm, removeAll list: [x]
2019-08-02 18:31:06.918 zwm, add list: [x, a, b, c]
2019-08-02 18:31:06.919 zwm, retainAll: true
2019-08-02 18:31:06.919 zwm, retainAll list: [a, b, c]
2019-08-02 18:31:06.919 zwm, set list: [sss, b, c]
2019-08-02 18:31:06.919 zwm, subList: [b, c]
2019-08-02 18:31:06.920 zwm, trimToSize
2019-08-02 18:31:06.920 zwm, toArray item: sss
2019-08-02 18:31:06.920 zwm, toArray item: b
2019-08-02 18:31:06.920 zwm, toArray item: c
2019-08-02 18:31:06.920 zwm, toArray T param item: sss
2019-08-02 18:31:06.920 zwm, toArray T param item: b
2019-08-02 18:31:06.920 zwm, toArray T param item: c
2019-08-02 18:31:06.920 zwm, toArray T result item: sss
2019-08-02 18:31:06.920 zwm, toArray T result item: b
2019-08-02 18:31:06.921 zwm, toArray T result item: c
三、原理
重要參數(shù)
//默認的數(shù)組長度
private static final int DEFAULT_CAPACITY = 10;
//默認的空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
//默認的空數(shù)組（與EMPTY_ELEMENTDATA有點區(qū)別，在不同的構造函數(shù)中用到）
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//真正用于存放數(shù)據(jù)的數(shù)組
transient Object[] elementData;
//數(shù)組元素個數(shù)
private int size;
構造函數(shù)
//指定容量大小初始化
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//無參初始化，DEFAULTCAPACITY_EMPTY_ELEMENTDATA與EMPTY_ELEMENTDATA都是空數(shù)組，區(qū)別是當?shù)谝粋€元素被插入時，如果使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA空數(shù)組，會自動將容量擴容到10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//構造一個包含指定Collection的元素的列表，這些元素是按照該Collection的迭代器返回它們的順序排列的
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
public void trimToSize()
//將ArrayList容量設置為實際大小
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size); //拷貝數(shù)組elementData，新數(shù)組大小為size
}
}
public void ensureCapacity(int minCapacity)
//在數(shù)據(jù)量過大的情況下初始化理想的ArryList容量，效率會明顯高于自動擴容
//所以在項目中有些業(yè)務處理時候對ArryList的長度有明顯的把控時 最好自定義其擴容方法來提高程序的執(zhí)行效率
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0) //如果指定的minCapacity數(shù)值比當前數(shù)組容量大，則進行擴容
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //newCapacity賦值為oldCapacity * 1.5
if (newCapacity - minCapacity < 0) //如果newCapacity小于指定的minCapacity數(shù)值，則newCapacity賦值為minCapacity
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) //如果newCapacity大于MAX_ARRAY_SIZE
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); //拷貝數(shù)組elementData，新數(shù)組大小為newCapacity
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? //如果指定的minCapacity數(shù)值大于MAX_ARRAY_SIZE，則擴容至Integer.MAX_VALUE，否則使用MAX_ARRAY_SIZE
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
private void ensureCapacityInternal(int minCapacity)
//在相關操作之前，確保數(shù)組有足夠的容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
public boolean add(E e)
//添加一個元素在數(shù)組末尾
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element)
//在索引位置插入元素
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1, //將index及后面的數(shù)據(jù)后移一位
size - index);
elementData[index] = element; //插入元素到index位置
size++; //元素個數(shù)加1
}
//判斷索引是否越界
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
public boolean addAll(Collection<? extends E> c)
//插入Collection中的所有元素到末尾
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew); //拷貝數(shù)組a的numNew個元素到數(shù)組elementData的末尾
size += numNew; //元素個數(shù)加numNew
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c)
//在索引位置插入Collection中的所有元素
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew, //將index及后面的數(shù)據(jù)后移numNew位
numMoved);
System.arraycopy(a, 0, elementData, index, numNew); //拷貝數(shù)組a的numNew個元素到數(shù)組elementData的以index開始的numNew個位置
size += numNew;
return numNew != 0;
}
public E remove(int index)
//輸出索引位置的元素
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, //將index后面的元素前移一位
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public boolean remove(Object o)
//刪除與對象o相等的元素
public boolean remove(Object o) {
if (o == null) { //要刪除的為空對象
for (int index = 0; index < size; index++)
if (elementData[index] == null) { //判斷是否等于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, //將index后面的元素前移一位
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
public boolean removeAll(Collection<?> c)
//刪除Collection中有的所有元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement) //如果不需要刪除該元素，則從頭開始插入
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
public E set(int index, E element)
//修改索引位置的元素
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
public E get(int index)
//查詢索引位置的元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
public int indexOf(Object o)
//查詢第一個與對象o相等的元素的索引位置
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;
}
public int lastIndexOf(Object o)
//查詢最后一個與對象o相等的元素的索引位置
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;
}
public boolean contains(Object o)
//查詢是否包含與對象o相等的元素
public boolean contains(Object o) {
return indexOf(o) >= 0; //調用indexof方法
}
public void clear()
//清空數(shù)組
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
public int size()
//獲取數(shù)組元素個數(shù)
public int size() {
return size;
}
public boolean isEmpty()
//判斷數(shù)組是否有元素
public boolean isEmpty() {
return size == 0;
}
public Iterator<E> iterator()
//返回迭代器對象
public Iterator<E> iterator() {
return new Itr();
}
//迭代器類，實現(xiàn)了Iterator接口
private class Itr implements Iterator<E> {
//獲取下一個元素
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
//移除當前元素
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//確認是否在別的線程有修改集合
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
fail-fast機制：
在next和remove操作之前，都會調用checkForComodification函數(shù)，如果modCount和本身記錄的expectedModCount不一致，就證明集合在別處被修改過，拋出ConcurrentModificationException異常，產生fail-fast事件。
fail-fast機制是java集合（Collection）中的一種錯誤機制，當多個線程對同一個集合的內容進行操作時，就可能會產生fail-fast事件。例如：當某一個線程A通過iterator去遍歷某集合的過程中，若該集合的內容被其他線程所改變了，那么線程A訪問集合時，就會拋出ConcurrentModificationException異常，產生fail-fast事件。一般在多線程環(huán)境下，可以考慮使用CopyOnWriteArrayList來避免fail-fast。
public ListIterator<E> listIterator()
//返回迭代器對象
public ListIterator<E> listIterator() {
return new ListItr(0);
}
//迭代器類，實現(xiàn)了ListIterator接口
private class ListItr extends Itr implements ListIterator<E>
