Java集合系列03之ArrayList详细介绍(源码解析)和使用示例
概要上一章，我们学习了Collection的架构。这一章开始，我们对Collection的具体实现类进行讲解；首先，讲解List，而List中ArrayList又最为常用。因此，本章我们讲解ArrayList。先对ArrayList有个整体认识，再学习它的源码，最后再通过例子来学习如何使用它。内容包括：
第1部分 ArrayList简介
第2部分 ArrayList数据结构
第3部分 ArrayList源码解析(基于JDK1.6.0_45)
第4部分 ArrayList遍历方式
第5部分 toArray()异常
第6部分 ArrayList示例
转载请注明出处：http://www.cnblogs.com/skywang12345/p/3308556.html
第1部分 ArrayList介绍ArrayList简介
ArrayList 是一个数组队列，相当于 动态数组。与java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List, Randomaccess, Cloneable, java.io.Serializable这些接口。
ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。稍后，我们会比较List的“快速随机访问”和“通过Iterator迭代器访问”的效率。
ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
和Vector不同，ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。
ArrayList构造函数
//默认构造函数ArrayList()//capacity是ArrayList的默认容量大小。当由于增加数据导致容量不足时，容量会添加上一次容量大小的一半。ArrayList(intcapacity)//创建一个包含collection的ArrayListArrayList(Collection<?extendsE> collection)
ArrayList的API
//Collection中定义的APIbooleanadd(E object)booleanaddAll(Collection<?extendsE>collection)voidclear()booleancontains(Object object)booleancontainsAll(Collection<?>collection)booleanequals(Object object)inthashCode()booleanisEmpty()
Iterator<E>iterator()booleanremove(Object object)booleanremoveAll(Collection<?>collection)booleanretainAll(Collection<?>collection)intsize()<T>T[] toArray(T[] array)
Object[] toArray()//AbstractCollection中定义的APIvoidadd(intlocation, E object)booleanaddAll(intlocation, Collection<?extendsE>collection)
E get(intlocation)intindexOf(Object object)intlastIndexOf(Object object)
ListIterator<E> listIterator(intlocation)
ListIterator<E>listIterator()
E remove(intlocation)
E set(intlocation, E object)
List<E> subList(intstart,intend)//ArrayList新增的APIObject clone()voidensureCapacity(intminimumCapacity)voidtrimToSize()voidremoveRange(intfromIndex,inttoIndex)
第2部分 ArrayList数据结构ArrayList的继承关系
java.lang.Object
↳ java.util.AbstractCollection<E>↳ java.util.AbstractList<E>↳ java.util.ArrayList<E>publicclassArrayList<E>extendsAbstractList<E>implementsList<E>, RandomAccess, Cloneable, java.io.Serializable {}
ArrayList与Collection关系如下图：
ArrayList包含了两个重要的对象：elementData 和 size。
(01) elementData 是"Object[]类型的数组"，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长，具体的增长方式，请参考源码分析中的ensureCapacity()函数。
(02) size 则是动态数组的实际大小。
第3部分 ArrayList源码解析(基于JDK1.6.0_45)为了更了解ArrayList的原理，下面对ArrayList源码代码作出分析。ArrayList是通过数组实现的，源码比较容易理解。
1packagejava.util;23publicclassArrayList<E>extendsAbstractList<E>4implementsList<E>, RandomAccess, Cloneable, java.io.Serializable5{6//序列版本号7PRivatestaticfinallongserialVersionUID = 8683452581122892189L;89//保存ArrayList中数据的数组10privatetransientObject[] elementData;1112//ArrayList中实际数据的数量13privateintsize;1415//ArrayList带容量大小的构造函数。16publicArrayList(intinitialCapacity) {17super();18if(initialCapacity < 0)19thrownewIllegalArgumentException("Illegal Capacity: "+20initialCapacity);21//新建一个数组22this.elementData =newObject[initialCapacity];23}2425//ArrayList构造函数。默认容量是10。26publicArrayList() {27this(10);28}2930//创建一个包含collection的ArrayList31publicArrayList(Collection<?extendsE>c) {32elementData =c.toArray();33size =elementData.length;34//c.toArray might (incorrectly) not return Object[] (see 6260652)35if(elementData.getClass() != Object[].class)36elementData = Arrays.copyOf(elementData, size, Object[].class);37}383940//将当前容量值设为 =实际元素个数41publicvoidtrimToSize() {42modCount++;43intoldCapacity =elementData.length;44if(size <oldCapacity) {45elementData =Arrays.copyOf(elementData, size);46}47}484950//确定ArrarList的容量。51//若ArrayList的容量不足以容纳当前的全部元素，设置 新的容量=“(原始容量x3)/2 + 1”52publicvoidensureCapacity(intminCapacity) {53//将“修改统计数”+154modCount++;55intoldCapacity =elementData.length;56//若当前容量不足以容纳当前的元素个数，设置 新的容量=“(原始容量x3)/2 + 1”57if(minCapacity >oldCapacity) {58Object oldData[] =elementData;59intnewCapacity = (oldCapacity * 3)/2 + 1;60if(newCapacity <minCapacity)61newCapacity =minCapacity;62elementData =Arrays.copyOf(elementData, newCapacity);63}64}6566//添加元素e67publicbooleanadd(E e) {68//确定ArrayList的容量大小69ensureCapacity(size + 1);//Increments modCount!!70//添加e到ArrayList中71elementData[size++] =e;72returntrue;73}7475//返回ArrayList的实际大小76publicintsize() {77returnsize;78}7980//返回ArrayList是否包含Object(o)81publicbooleancontains(Object o) {82returnindexOf(o) >= 0;83}8485//返回ArrayList是否为空86publicbooleanisEmpty() {87returnsize == 0;88}8990//正向查找，返回元素的索引值91publicintindexOf(Object o) {92if(o ==null) {93for(inti = 0; i < size; i++)94if(elementData[i]==null)95returni;96}else{97for(inti = 0; i < size; i++)98if(o.equals(elementData[i]))99returni;100}101return-1;102}103104//反向查找，返回元素的索引值105publicintlastIndexOf(Object o) {106if(o ==null) {107for(inti = size-1; i >= 0; i--)108if(elementData[i]==null)109returni;110}else{111for(inti = size-1; i >= 0; i--)112if(o.equals(elementData[i]))113returni;114}115return-1;116}117118//反向查找(从数组末尾向开始查找)，返回元素(o)的索引值119publicintlastIndexOf(Object o) {120if(o ==null) {121for(inti = size-1; i >= 0; i--)122if(elementData[i]==null)123returni;124}else{125for(inti = size-1; i >= 0; i--)126if(o.equals(elementData[i]))127returni;128}129return-1;130}131132133//返回ArrayList的Object数组134publicObject[] toArray() {135returnArrays.copyOf(elementData, size);136}137138//返回ArrayList的模板数组。所谓模板数组，即可以将T设为任意的数据类型139public<T>T[] toArray(T[] a) {140//若数组a的大小 < ArrayList的元素个数；141//则新建一个T[]数组，数组大小是“ArrayList的元素个数”，并将“ArrayList”全部拷贝到新数组中142if(a.length <size)143return(T[]) Arrays.copyOf(elementData, size, a.getClass());144145//若数组a的大小 >= ArrayList的元素个数；146//则将ArrayList的全部元素都拷贝到数组a中。147System.arraycopy(elementData, 0, a, 0, size);148if(a.length >size)149a[size] =null;150returna;151}152153//获取index位置的元素值154publicE get(intindex) {155RangeCheck(index);156157return(E) elementData[index];158}159160//设置index位置的值为element161publicE set(intindex, E element) {162RangeCheck(index);163164E oldValue =(E) elementData[index];165elementData[index] =element;166returnoldValue;167}168169//将e添加到ArrayList中170publicbooleanadd(E e) {171ensureCapacity(size + 1);//Increments modCount!!172elementData[size++] =e;173returntrue;174}175176//将e添加到ArrayList的指定位置177publicvoidadd(intindex, E element) {178if(index > size || index < 0)179thrownewIndexOutOfBoundsException(180"Index: "+index+", Size: "+size);181182ensureCapacity(size+1);//Increments modCount!!183System.arraycopy(elementData, index, elementData, index + 1,184size -index);185elementData[index] =element;186size++;187}188189//删除ArrayList指定位置的元素190publicE remove(intindex) {191RangeCheck(index);192193modCount++;194E oldValue =(E) elementData[index];195196intnumMoved = size - index - 1;197if(numMoved > 0)198System.arraycopy(elementData, index+1, elementData, index,199numMoved);200elementData[--size] =null;//Let gc do its work201202returnoldValue;203}204205//删除ArrayList的指定元素206publicbooleanremove(Object o) {207if(o ==null) {208for(intindex = 0; index < size; index++)209if(elementData[index] ==null) {210fastRemove(index);211returntrue;212}213}else{214for(intindex = 0; index < size; index++)215if(o.equals(elementData[index])) {216fastRemove(index);217returntrue;218}219}220returnfalse;221}222223224//快速删除第index个元素225privatevoidfastRemove(intindex) {226modCount++;227intnumMoved = size - index - 1;228//从"index+1"开始，用后面的元素替换前面的元素。229if(numMoved > 0)230System.arraycopy(elementData, index+1, elementData, index,231numMoved);232//将最后一个元素设为null233elementData[--size] =null;//Let gc do its work234}235236//删除元素237publicbooleanremove(Object o) {238if(o ==null) {239for(intindex = 0; index < size; index++)240if(elementData[index] ==null) {241fastRemove(index);242returntrue;243}244}else{245//便利ArrayList，找到“元素o”，则删除，并返回true。246for(intindex = 0; index < size; index++)247if(o.equals(elementData[index])) {248fastRemove(index);249returntrue;250}251}252returnfalse;253}254255//清空ArrayList，将全部的元素设为null256publicvoidclear() {257modCount++;258259for(inti = 0; i < size; i++)260elementData[i] =null;261262size = 0;263}264265//将集合c追加到ArrayList中266publicbooleanaddAll(Collection<?extendsE>c) {267Object[] a =c.toArray();268intnumNew =a.length;269ensureCapacity(size + numNew);//Increments modCount270System.arraycopy(a, 0, elementData, size, numNew);271size +=numNew;272returnnumNew != 0;273}274275//从index位置开始，将集合c添加到ArrayList276publicbooleanaddAll(intindex, Collection<?extendsE>c) {277if(index > size || index < 0)278thrownewIndexOutOfBoundsException(279"Index: " + index + ", Size: " +size);280281Object[] a =c.toArray();282intnumNew =a.length;283ensureCapacity(size + numNew);//Increments modCount284285intnumMoved = size -index;286if(numMoved > 0)287System.arraycopy(elementData, index, elementData, index +numNew,288numMoved);289290System.arraycopy(a, 0, elementData, index, numNew);291size +=numNew;292returnnumNew != 0;293}294295//删除fromIndex到toIndex之间的全部元素。296protectedvoidremoveRange(intfromIndex,inttoIndex) {297modCount++;298intnumMoved = size -toIndex;299System.arraycopy(elementData, toIndex, elementData, fromIndex,300numMoved);301302//Let gc do its work303intnewSize = size - (toIndex-fromIndex);304while(size !=newSize)305elementData[--size] =null;306}307308privatevoidRangeCheck(intindex) {309if(index >=size)310thrownewIndexOutOfBoundsException(311"Index: "+index+", Size: "+size);312}313314315//克隆函数316publicObject clone() {317try{318ArrayList<E> v = (ArrayList<E>)super.clone();319//将当前ArrayList的全部元素拷贝到v中320v.elementData =Arrays.copyOf(elementData, size);321v.modCount = 0;322returnv;323}catch(CloneNotSupportedException e) {324//this shouldn't happen, since we are Cloneable325thrownewInternalError();326}327}328329330//java.io.Serializable的写入函数331//将ArrayList的“容量，所有的元素值”都写入到输出流中332privatevoidwriteObject(java.io.ObjectOutputStream s)333throwsjava.io.IOException{334//Write out element count, and any hidden stuff335intexpectedModCount =modCount;336s.defaultWriteObject();337338//写入“数组的容量”339s.writeInt(elementData.length);340341//写入“数组的每一个元素”342for(inti=0; i<size; i++)343s.writeObject(elementData[i]);344345if(modCount !=expectedModCount) {346thrownewConcurrentModificationException();347}348349}350351352//java.io.Serializable的读取函数：根据写入方式读出353//先将ArrayList的“容量”读出，然后将“所有的元素值”读出354privatevoidreadObject(java.io.ObjectInputStream s)355throwsjava.io.IOException, ClassNotFoundException {356//Read in size, and any hidden stuff357s.defaultReadObject();358359//从输入流中读取ArrayList的“容量”360intarrayLength =s.readInt();361Object[] a = elementData =newObject[arrayLength];362363//从输入流中将“所有的元素值”读出364for(inti=0; i<size; i++)365a[i] =s.readObject();366}367}
ArrayList源码
总结：
(01) ArrayList 实际上是通过一个数组去保存数据的。当我们构造ArrayList时；若使用默认构造函数，则ArrayList的默认容量大小是10。
(02) 当ArrayList容量不足以容纳全部元素时，ArrayList会重新设置容量：新的容量=“(原始容量x3)/2 + 1”。
(03) ArrayList的克隆函数，即是将全部元素克隆到一个数组中。
(04) ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写入“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。
第4部分 ArrayList遍历方式ArrayList支持3种遍历方式
(01) 第一种，通过迭代器遍历。即通过Iterator去遍历。
Integer value =null;
Iterator iter=list.iterator();while(iter.hasNext()) {
value=(Integer)iter.next();
}
(02) 第二种，随机访问，通过索引值去遍历。
由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。
Integer value =null;intsize =list.size();for(inti=0; i<size; i++) {
value=(Integer)list.get(i);
}
(03) 第三种，for循环遍历。如下：
Integer value =null;for(Integer integ:list) {
value=integ;
}
下面通过一个实例，比较这3种方式的效率，实例代码(ArrayListRandomAccessTest.java)如下：
1importjava.util.*;2importjava.util.concurrent.*;34/*5* @desc ArrayList遍历方式和效率的测试程序。6*7* @author skywang8*/9publicclassArrayListRandomAccessTest {1011publicstaticvoidmain(String[] args) {12List list =newArrayList();13for(inti=0; i<100000; i++)14list.add(i);15//isRandomAccessSupported(list);16iteratorThroughRandomAccess(list) ;17iteratorThroughIterator(list) ;18iteratorThroughFor2(list) ;1920}2122privatestaticvoidisRandomAccessSupported(List list) {23if(listinstanceofRandomAccess) {24System.out.println("RandomAccess implemented!");25}else{26System.out.println("RandomAccess not implemented!");27}2829}3031publicstaticvoiditeratorThroughRandomAccess(List list) {3233longstartTime;34longendTime;35startTime =System.currentTimeMillis();36for(inti=0; i<list.size(); i++) {37list.get(i);38}39endTime =System.currentTimeMillis();40longinterval = endTime -startTime;41System.out.println("iteratorThroughRandomAccess：" + interval+" ms");42}4344publicstaticvoiditeratorThroughIterator(List list) {4546longstartTime;47longendTime;48startTime =System.currentTimeMillis();49for(Iterator iter =list.iterator(); iter.hasNext(); ) {50iter.next();51}52endTime =System.currentTimeMillis();53longinterval = endTime -startTime;54System.out.println("iteratorThroughIterator：" + interval+" ms");55}565758publicstaticvoiditeratorThroughFor2(List list) {5960longstartTime;61longendTime;62startTime =System.currentTimeMillis();63for(Object obj:list)64;65endTime =System.currentTimeMillis();66longinterval = endTime -startTime;67System.out.println("iteratorThroughFor2：" + interval+" ms");68}69}
View Code
运行结果：
iteratorThroughRandomAccess：3 ms
iteratorThroughIterator：8 ms
iteratorThroughFor2：5 ms
由此可见，遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低！
第5部分 toArray()异常当我们调用ArrayList中的 toArray()，可能遇到过抛出“java.lang.ClassCastException”异常的情况。下面我们说说这是怎么回事。
ArrayList提供了2个toArray()函数：
Object[] toArray()<T> T[] toArray(T[] contents)
调用 toArray() 函数会抛出“java.lang.ClassCastException”异常，但是调用 toArray(T[] contents) 能正常返回 T[]。
toArray() 会抛出异常是因为 toArray() 返回的是 Object[] 数组，将 Object[] 转换为其它类型(如如，将Object[]转换为的Integer[])则会抛出“java.lang.ClassCastException”异常，因为Java不支持向下转型。具体的可以参考前面ArrayList.java的源码介绍部分的toArray()。
解决该问题的办法是调用 <T> T[] toArray(T[] contents) ， 而不是 Object[] toArray()。
调用 toArray(T[] contents) 返回T[]的可以通过以下几种方式实现。
//toArray(T[] contents)调用方式一publicstaticInteger[] vectorToArray1(ArrayList<Integer>v) {
Integer[] newText=newInteger[v.size()];
v.toArray(newText);returnnewText;
}//toArray(T[] contents)调用方式二。最常用！publicstaticInteger[] vectorToArray2(ArrayList<Integer>v) {
Integer[] newText= (Integer[])v.toArray(newInteger[0]);returnnewText;
}//toArray(T[] contents)调用方式三publicstaticInteger[] vectorToArray3(ArrayList<Integer>v) {
Integer[] newText=newInteger[v.size()];
Integer[] newStrings=(Integer[])v.toArray(newText);returnnewStrings;
}
第6部分 ArrayList示例本文通过一个实例(ArrayListTest.java)，介绍 ArrayList 中常用API的用法。
importjava.util.*;/** @desc ArrayList常用API的测试程序
* @author skywang
* @email kuiwu-wang@163.com*/publicclassArrayListTest {publicstaticvoidmain(String[] args) {//创建ArrayListArrayList list =newArrayList();//将“”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());//判断list中是否包含"3"System.out.println("ArrayList contains 3 is: "+ list.contains(3));//设置第2个元素为10list.set(1, "10");//通过Iterator遍历ArrayListfor(Iterator iter =list.iterator(); iter.hasNext(); ) {
System.out.println("next is: "+iter.next());
}//将ArrayList转换为数组String[] arr = (String[])list.toArray(newString[0]);for(String str:arr)
System.out.println("str: "+str);//清空ArrayListlist.clear();//判断ArrayList是否为空System.out.println("ArrayList is empty: "+list.isEmpty());
}
}
View Code
运行结果：
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