ArrayList的源码分析
ArrayList是最常用的数组，这里我们分析一下源码：
ArrayList继承了AbstractList<E> ，并且实现了List<E>, RandomAccess, Cloneable, java.io.Serializable里面有几个比较重要的成员变量：
序列化Id
private static final long serialVersionUID=8683452581122892189L;
默认的初始化容量10：
private static final int DEFAULT_CAPACITY=10;
用于空实例的共享空数组实例：
private static final Object[] EMPTY_ELEMENTDATA={};
用于空实例的共享空数组实例，这个跟EMPTY_ELEMENTDATA的区别是在于当第一个元素被添加以后怎么知道需要多少扩容
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};
数组缓冲区中的数组的元素存储。ArrayList的容量是这个array buffer的的长度
transient Object[] elementData;
ArrayList的长度
private int size;
这是一个常量，用来限制数组的最大长度，Integer.MAX_VALUE=2的31次方-1
private static final int MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8;
下面看一下ArrayList的几个构造函数：
这个是指定初始大小的构造函数
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData=new Object[initialCapacity];//如果初始值>0则初始化数组} else if (initialCapacity==0) {this.elementData=EMPTY_ELEMENTDATA;//如果初始值为0，则将孔数组赋给这个数组} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}
这个是默认的构造函数
public ArrayList() {this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;会把默认的空数组赋值给这个数组}
还有一个构造方法,传入的参数是一个collection对象
public ArrayList(Collection<? extends E> c) {elementData=c.toArray();//把collection转为一个Arrayif ((size=elementData.length) !=0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() !=Object[].class)//是否成功转化为Object类型数组elementData=Arrays.copyOf(elementData, size, Object[].class);//转化失败就进行复制} else {// replace with empty array.this.elementData=EMPTY_ELEMENTDATA;}}
下面是分析里面具体的每个方法：
把 ArrayList实例的容量装饰成这个list当前的大小。一个应用可以使用这个方法来最小化ArrayList实例的产生
public void trimToSize() {modCount++;if (size < elementData.length) {elementData=(size==0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}
增加ArrayList实例的容量，如果有必要，要确保这个能保证当前所有元素最小的容量
public void ensureCapacity(int minCapacity) {int minExpand=(elementData !=DEFAULTCAPACITY_EMPTY_ELEMENTDATA)//先判断一下数组是不是为空if (minCapacity > minExpand) { 如果最小容量大于默认容量，就要开始扩容了ensureExplicitCapacity(minCapacity);}}
进行扩容初始化，这是一个私有方法
private void ensureCapacityInternal(int minCapacity) {if (elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity=Math.max(DEFAULT_CAPACITY, minCapacity);//找到最小的初始容量大小}
ensureExplicitCapacity(minCapacity);}这也是一个私有方法，开始进行扩容
private void ensureExplicitCapacity(int minCapacity) {modCount++;if (minCapacity - elementData.length > 0)//判断最小的容量是不是> 数组的长度grow(minCapacity);//扩容的具体实现}
这是个私有方法，这个是扩容的具体实现
private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity=elementData.length; //获取当前数组的大小int newCapacity=oldCapacity + (oldCapacity >> 1); //新数组的容量算法为：当前数组大小 + （当前数组大小 / 2),相当于原来的1.5倍大小if (newCapacity - minCapacity < 0)//如果新的容量大小比最小的容量还小,就用最小扩容量newCapacity=minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)//如果新的容量大小比数组规定的最大容量还大，就调用hugeCapacity来算容量newCapacity=hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData=Arrays.copyOf(elementData, newCapacity);//进行扩容}
这个也是一个私有方法，用来算出当新的数组容量比Java规定的最大数组容量还大的时候，要设置多少作为最大容量
private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ? //判断最小容量是不是已经超过了Java规定的最大数组容量Integer.MAX_VALUE : 超过了就用Integer最大值 2的31次方-1MAX_ARRAY_SIZE; 没有就用数组最大容量 Integer.MAX_VALUE - 8}
返回list里面元素的个数
public int size() {return size;}
判断list是不是为空，通过判断szie是不是为0
public boolean isEmpty() {return size==0;}
判断是不是传入的元素包含在了当前list里面，具体实现是在indexOf方法
public boolean contains(Object o) {return indexOf(o) >=0;//这个意思就是至少包含一次，通过查看indexof()的代码，返回值是数组下标，而数组下标是从0开始的，所以这里写>=0}
这个方法是把传入的Object对象跟list里面的值进行比较，返回的是符合要求的值的数组下标而不是个数
public int indexOf(Object o) {if (o==null) {//这段代码刚开始没有看懂，后来又看了看，原来判断当前传入的对象如果为空，for (int i=0; i < size; i++)//并且list里面也有空对象，那么也是要找到，并说明存在为null的if (elementData[i]==null)return i;} else {for (int i=0; i < size; i++)//这个就是通过用Object的equals方法来做比较，当出现有符合要求的值就返回这个值的数组下标if (o.equals(elementData[i]))return i;}return -1;//没有符合条件的就返回-1}
这个是ArrayList的一个克隆方法，返回的一个浅克隆的ArrayList实例，但是ArrayList里面的元素是没有被克隆的
public Object clone() {try {ArrayList<?> v=(ArrayList<?>) super.clone();这里面是调用了Object的clone()方法v.elementData=Arrays.copyOf(elementData, size);用Arrays的copyOf方法来把元素都放进新的实例中v.modCount=0;return v;} catch (CloneNotSupportedException e) {// this shouldn't happen, since we are Cloneablethrow new InternalError(e);}}
返回一个数组包含了所有当前list的元素，按照当前的数组序列，实际是用Arrays的copyOf方法来实现的
public Object[] toArray() {return Arrays.copyOf(elementData, size);}
返回一个数组包含了所有当前list的所有元素，并且元素类型是指定的元素类型
public <T> T[] toArray(T[] a) {if (a.length < size)// Make a new array of a's runtime type, but my contents:return (T[]) Arrays.copyOf(elementData, size, a.getClass());System.arraycopy(elementData, 0, a, 0, size);if (a.length > size) //如果传入的数组长度大于当前的的数组长度，则返回空a[size]=null;return a;}
根据数组下标返回元素
@SuppressWarnings("unchecked")E elementData(int index) {return (E) elementData[index];}
根据数组下标找到元素
public E get(int index) {rangeCheck(index);//数组越界检查
return elementData(index);//通过调用elementData来找到相应元素}将传入的参数元素添加到指定的下标渣饼返回这个元素
public E set(int index, E element) {rangeCheck(index);//数组越界检查
E oldValue=elementData(index);//先找到当前元素 elementData[index]=element;//把传入的元素设置到指定的位置 return oldValue;}添加一个元素到到当前list里面，如果添加成功则返回true
public boolean add(E e) {ensureCapacityInternal(size + 1); // Increments modCount!!//新进行扩容判断elementData[size++]=e;//直接在当前list的后面进行添加return true;}
将传入的元素添加在指定的数组下标地址
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;//在list里面将传入的元素赋值给指定的数组下标位置size++;}
//将指定的数组下标从list中删除
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 workreturn oldValue;//并返回这个元素}
//将传入的Object对象从数组中移除，移除成功则返回true
public boolean remove(Object o) {if (o==null) {//这里为什么为null还要处理，因为list里面还有为空的对象for (int index=0; index < size; index++)if (elementData[index]==null) {fastRemove(index);//调用fastRemove进行删除return true;}} else {for (int index=0; index < size; index++)if (o.equals(elementData[index])) {//通过遍历找到传入的Object然后进行删除fastRemove(index);return true;}}return false;}
这是一个私有的方法，用来快速删除元素，这个方法跟remove是一样的，只是这个方法没有检测数组是不是越界了，并且没有返回值
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}
这个方法就是将数组清空
public void clear() {modCount++;
// clear to let GC do its work for (int i=0; i < size; i++) elementData[i]=null; size=0;}将传入的collection全部添加到当前数组
public boolean addAll(Collection<? extends E> c) {Object[] a=c.toArray();//通过这个方法将collection变成一个数组int numNew=a.length;ensureCapacityInternal(size + numNew); // Increments modCount//通过当前数组的大小跟传入的数组大小进行扩容判断System.arraycopy(a, 0, elementData, size, numNew);//通过这个方法把传入的collection都加入到当前数组size +=numNew;return numNew !=0;}
这个方法是将传入的数组放在当前list的指定位置
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,numMoved);//先将当前数组在index以及以后的元素往后移动System.arraycopy(a, 0, elementData, index, numNew);//将传入的数组从指定的位置开始插入size +=numNew;return numNew !=0;}
这个方法是将指定数组范围内的元素删除
protected void removeRange(int fromIndex, int toIndex) {modCount++;int numMoved=size - toIndex;System.arraycopy(elementData, toIndex, elementData, fromIndex,numMoved);//先将需要删除的元素范围的位置给移除掉// clear to let GC do its workint newSize=size - (toIndex-fromIndex);for (int i=newSize; i < size; i++) {elementData[i]=null;//通过遍历将这些元素进行删除}size=newSize;}
数组越界检查
private void rangeCheck(int index) {if (index >=size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
数组越界检查，这个检查是在add的时候用
private void rangeCheckForAdd(int index) {if (index > size || index < 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
这个是构造数组越界的时候的异常语言
private String outOfBoundsMsg(int index) {return "Index: "+index+", Size: "+size;}
这个方法是将所有包含在collection的元素从当前数组中移除
public boolean removeAll(Collection<?> c) {Objects.requireNonNull(c);//调用Object的判断是不是空指针的方法return batchRemove(c, false);//调用这个方法来删除
}这个方法正好相反，是将所有没有包含在collection的元素从当前数组中移除
public boolean retainAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, true);}
这个方法就是上面两个方法的具体实现，其中complement为true代表删除所有不包含在传入的数组里面的元素，为false时代表删除所有在传入的数组中的元素
private boolean batchRemove(Collection<?> c, boolean complement) {final Object[] elementData=this.elementData;int r=0, w=0;boolean=false;try {for (; r < size; r++)if (c.contains(elementData[r])==complement)//这个逻辑就是根据传入的boolean值来判断是怎么删除的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 workfor (int i=w; i < size; i++)elementData[i]=null;modCount +=size - w;size=w;modified=true;}}return modified;}
将一个ArrayList实例转化为一个流
private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{// Write out element count, and any hidden stuffint expectedModCount=modCount;s.defaultWriteObject();//调用ObjectOutputStream的defaultWriteObject，这个方法是用来将一个类的非静态和非transient区域转化为流// Write out size as capacity for behavioural compatibility with clone()s.writeInt(size);// Write out all elements in the proper order.for (int i=0; i<size; i++) {s.writeObject(elementData[i]);}if (modCount !=expectedModCount) {throw new ConcurrentModificationException();}}
从stream反序列化成一个ArrayList
private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {elementData=EMPTY_ELEMENTDATA;// Read in size, and any hidden stuffs.defaultReadObject();// Read in capacitys.readInt(); // ignoredif (size > 0) {// be like clone(), allocate array based upon size not capacityensureCapacityInternal(size);Object[] a=elementData;// Read in all elements in the proper order.for (int i=0; i<size; i++) {a[i]=s.readObject();}}}
从传入的位置开始返回一个iterator list包含了这个位置以后的所有元素
public ListIterator<E> listIterator(int index) {if (index < 0 || index > size)throw new IndexOutOfBoundsException("Index: "+index);return new ListItr(index);}
返回一个包含了所有元素的iterator list
public ListIterator<E> listIterator() {return new ListItr(0);}
这个方法也是返回一个包含了所有元素的iterator list，只是实现方式不一样
public Iterator<E> iterator() {return new Itr();}
往下分析发现了一些内部类以及一些不常用的方法，这里就不一一列举了，有兴趣可以自己看一下源码这个主要说一下这个sort方法，这个经常被用到：ArrayList的sort是重写了父类List的sort排序，而在List里面调用了Arrays的sort排序算法，如果大家想要实现自己的逻辑排序算法的话，要调用sort方法并且新写一个Comparator重写compare方法,compare方法的返回值，代表了两个数的比较结果
public void sort(Comparator<? super E> c) {final int expectedModCount=modCount;Arrays.sort((E[]) elementData, 0, size, c);if (modCount !=expectedModCount) {throw new ConcurrentModificationException();}modCount++;}
下面是一个简单的运用sort实现Student类按照年龄进行排序的（Student类就不写了，只是里面有age这个成员变量）
List<Student> datas=new ArrayList<Student>();datas.sort(new Comparator<Student>() {@Overridepublic int compare(Student o1, Student o2) {// return o1.getAge() - o2.getAge(); 升序return o2.getAge() - o1.getAge(); //降序}});
ArrayList
一、ArrayList的结构特征
ArrayList继承AbstractList和实现RandomAccess、Cloneable、Serializable接口
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.SerializableRandomAccess
支持随机访问（基于下标）,为了能够更好地判断集合是ArrayList还是LinkedList，从而能够更好选择更优的遍历方式，提高性能！
Cloneable
支持拷贝：实现Cloneable接口，重写clone方法、方法内容默认调用父类的clone方法。
浅拷贝
基础类型的变量拷贝之后是独立的，不会随着源变量变动而变
String类型拷贝之后也是独立的
? 引用类型拷贝的是引用地址，拷贝前后的变量引用同一个堆中的对象
public Object clone() throws CloneNotSupportedException { User user=(User) super.clone(); return user;}深拷贝
? 变量的所有引用类型变量（除了String）都需要实现Cloneable（数组可以直接调用clone方法），clone方法中，引用类型需要各自调用clone，重新赋值
public Object clone() throws CloneNotSupportedException { User user=(User) super.clone(); user.setName(this.name.clone()); return user;}?
java的传参，基本类型和引用类型传参
java在方法传递参数时，是将变量复制一份，然后传入方法体去执行。复制的是栈中的内容
所以基本类型是复制的变量名和值，值变了不影响源变量
引用类型复制的是变量名和值（引用地址），对象变了，会影响源变量（引用地址是一样的）
String：是不可变对象，重新赋值时，会在常量表新生成字符串（如果已有，直接取他的引用地址），将新字符串的引用地址赋值给栈中的新变量，因此源变量不会受影响
Serializable
序列化：将对象状态转换为可保持或传输的格式的过程。与序列化相对的是反序列化，它将流转换为对象。这两个过程结合起来，可以轻松地存储和传输数据，在Java中的这个Serializable接口其实是给jvm看的，通知jvm，我不对这个类做序列化了，你(jvm)帮我序列化就好了。如果我们没有自己声明一个serialVersionUID变量,接口会默认生成一个serialVersionUID，默认的serialVersinUID对于class的细节非常敏感，反序列化时可能会导致InvalidClassException这个异常（每次序列化都会重新计算该值）
AbstractList
继承了AbstractList ，说明它是一个列表，拥有相应的增，删，查，改等功能。
List
为什么继承了 AbstractList 还需要 实现List 接口？
1、在StackOverFlow 中：传送门 得票最高的答案的回答者说他问了当初写这段代码的 Josh Bloch，得知这就是一个写法错误。I’ve asked Josh Bloch, and he informs me that it was a mistake. He used to think, long ago, that there was some value in it,but he since “saw the light”. Clearly JDK maintainers haven’t considered this to be worth backing out later.二、ArrayList的属性特征
基本属性
private static final long serialVersionUID=8683452581122892189L;//序列化版本号（类文件签名），如果不写会默认生成，类内容的改变会影响签名变化，导致反序列化失败private static final int DEFAULT_CAPACITY=10;//如果实例化时未指定容量，则在初次添加元素时会进行扩容使用此容量作为数组长度//static修饰，所有的未指定容量的实例(也未添加元素)共享此数组，两个空的数组有什么区别呢？ 就是第一次添加元素时知道该 elementData 从空的构造函数还是有参构造函数被初始化的。以便确认如何扩容。空的构造器则初始化为10，有参构造器则按照扩容因子扩容private static final Object[] EMPTY_ELEMENTDATA={};private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};transient Object[] elementData; // arrayList真正存放元素的地方，长度大于等于sizeprivate int size;//arrayList中的元素个数构造器
//无参构造器，构造一个容量大小为 10 的空的 list 集合，但构造函数只是给 elementData 赋值了一个空的数组，其实是在第一次添加元素时容量扩大至 10 的。public ArrayList() { this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}//当使用无参构造函数时是把 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值给 elementData。 当 initialCapacity 为零时则是把 EMPTY_ELEMENTDATA 赋值给 elementData。 当 initialCapacity 大于零时初始化一个大小为 initialCapacity 的 object 数组并赋值给 elementData。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); }}//将 Collection 转化为数组，数组长度赋值给 size。 如果 size 不为零，则判断 elementData 的 class 类型是否为 ArrayList，不是的话则做一次转换。 如果 size 为零，则把 EMPTY_ELEMENTDATA 赋值给 elementData，相当于new ArrayList(0)。public ArrayList(Collection<? extends E> c) { Object[] a=c.toArray(); if ((size=a.length) !=0) { if (c.getClass()==ArrayList.class) { elementData=a; } else { elementData=Arrays.copyOf(a, size, Object[].class); } } else { // 指向空数组 elementData=EMPTY_ELEMENTDATA; }}添加元素--默认尾部添加
//每次添加元素到集合中时都会先确认下集合容量大小。然后将 size 自增 1赋值public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++]=e; return true;}//判断如果 elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA 就取 DEFAULT_CAPACITY 和 minCapacity 的最大值也就是 10。这就是 EMPTY_ELEMENTDATA 与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的区别所在。同时也验证了上面的说法：使用无参构造函数时是在第一次添加元素时初始化容量为 10 的private void ensureCapacityInternal(int minCapacity) { if (elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity=Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity);}//对modCount自增1，记录操作次数，如果 minCapacity 大于 elementData 的长度，则对集合进行扩容,第一次添加元素时 elementData 的长度为零private void ensureExplicitCapacity(int minCapacity) { modCount++; if (minCapacity - elementData.length > 0) grow(minCapacity);}//涉及扩容，会消耗性能，但是如果提前指定容量，会提升性能，可以达到与linkedList相当，甚至超越public void addEffect(){ //不指定下标插入 int length=10000000; List al=new ArrayList(length);//指定容量时 效率相当 List ll=new LinkedList(); long start5=System.currentTimeMillis(); for(int i=0;i <length;i++){ al.add(i); } long end5=System.currentTimeMillis(); System.out.println(end5-start5); long start6=System.currentTimeMillis(); for(int i=0;i <length;i++){ ll.add(i); } long end6=System.currentTimeMillis(); System.out.println(end6-start6);}执行结果：9124237指定下标添加元素
public void add(int index, E element) { rangeCheckForAdd(index);//下标越界检查 ensureCapacityInternal(size + 1); //同上 判断扩容,记录操作数 //依次复制插入位置及后面的数组元素，到后面一格，不是移动，因此复制完后，添加的下标位置和下一个位置指向对同一个对象 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index]=element;//再将元素赋值给该下标 size++;}时间复杂度为O(n)，与移动的元素个数正相关
扩容
private void grow(int minCapacity) { int oldCapacity=elementData.length;//获取当前数组长度 int newCapacity=oldCapacity + (oldCapacity >> 1);//默认将扩容至原来容量的 1.5 倍 if (newCapacity - minCapacity < 0)//如果1.5倍太小的话，则将我们所需的容量大小赋值给newCapacity newCapacity=minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0)//如果1.5倍太大或者我们需要的容量太大，那就直接拿 newCapacity=(minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE 来扩容 newCapacity=hugeCapacity(minCapacity); elementData=Arrays.copyOf(elementData, newCapacity);//然后将原数组中的数据复制到大小为 newCapacity 的新数组中，并将新数组赋值给 elementData。}删除元素
public E remove(int index) { rangeCheck(index);//首先会检查 index 是否合法 modCount++;//操作数+1 E oldValue=elementData(index); int numMoved=size - index - 1; if (numMoved > 0)//判断要删除的元素是否是最后一个位,如果 index 不是最后一个，就从 index + 1 开始往后所有的元素都向前拷贝一份。然后将数组的最后一个位置空,如果 index 是最后一个元素那么就直接将数组的最后一个位置空 System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size]=null; //让指针最后指向空，进行垃圾回收 return oldValue;}//当我们调用 remove(Object o) 时，会把 o 分为是否为空来分别处理。然后对数组做遍历，找到第一个与 o 对应的下标 index，然后调用 fastRemove 方法，删除下标为 index 的元素。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;}//fastRemove(int index) 方法和 remove(int index) 方法基本全部相同。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; }迭代器 iterator
public Iterator<E> iterator() { return new Itr();}private class Itr implements Iterator<E> { int cursor; // 代表下一个要访问的元素下标 int lastRet=-1; // 代表上一个要访问的元素下标 int expectedModCount=modCount;//代表对 ArrayList 修改次数的期望值，初始值为 modCount //如果下一个元素的下标等于集合的大小 ，就证明到最后了 public boolean hasNext() { return cursor !=size; } @SuppressWarnings("unchecked") public E next() { checkForComodification();//判断expectedModCount和modCount是否相等,ConcurrentModificationException int i=cursor; if (i >=size)//对 cursor 进行判断，看是否超过集合大小和数组长度 throw new NoSuchElementException(); Object[] elementData=ArrayList.this.elementData; if (i >=elementData.length) throw new ConcurrentModificationException(); cursor=i + 1;//自增 1。开始时，cursor=0，lastRet=-1；每调用一次next方法，cursor和lastRet都会自增1。 return (E) elementData[lastRet=i];//将cursor赋值给lastRet，并返回下标为 lastRet 的元素 } public void remove() { if (lastRet < 0)//判断 lastRet 的值是否小于 0 throw new IllegalStateException(); checkForComodification();//判断expectedModCount和modCount是否相等,ConcurrentModificationException try { ArrayList.this.remove(lastRet);//直接调用 ArrayList 的 remove 方法删除下标为 lastRet 的元素 cursor=lastRet;//将 lastRet 赋值给 curso lastRet=-1;//将 lastRet 重新赋值为 -1，并将 modCount 重新赋值给 expectedModCount。 expectedModCount=modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (modCount !=expectedModCount) throw new ConcurrentModificationException(); }}remove 方法的弊端。
1、只能进行remove操作，add、clear 等 Itr 中没有。
2、调用 remove 之前必须先调用 next。因为 remove 开始就对 lastRet 做了校验。而 lastRet 初始化时为 -1。
3、next 之后只可以调用一次 remove。因为 remove 会将 lastRet 重新初始化为 -1
不可变集合
Collections.unmodifiableList可以将list封装成不可变集合（只读），但实际上会受源list的改变影响public void unmodifiable() { List list=new ArrayList(Arrays.asList(4,3,3,4,5,6));//缓存不可变配置 List modilist=Collections.unmodifiableList(list);//只读 modilist.set(0,1);//会报错UnsupportedOperationException //modilist.add(5,1); list.set(0,1); System.out.println(modilist.get(0));//打印1}Arrays.asList
public void testArrays(){ long[] arr=new long[]{1,4,3,3}; List list=Arrays.asList(arr);//基本类型不支持泛型化，会把整个数组当成一个元素放入新的数组，传入可变参数 System.out.println(list.size());//打印1}//可变参数public static <T> List<T> asList(T... a) { return new ArrayList<>(a);}基本类型不支持泛型化，会把整个数组当成一个元素放入新的数组，传入可变参数,因此size打印结果是1
什么是fail-fast？
fail-fast机制是java集合中的一种错误机制。
当使用迭代器迭代时，如果发现集合有修改，则快速失败做出响应，抛出ConcurrentModificationException异常。
这种修改有可能是其它线程的修改，也有可能是当前线程自己的修改导致的，比如迭代的过程中直接调用remove()删除元素等。
另外，并不是java中所有的集合都有fail-fast的机制。比如，像最终一致性的ConcurrentHashMap、CopyOnWriterArrayList等都是没有fast-fail的。
fail-fast是怎么实现的：
ArrayList、HashMap中都有一个属性叫modCount，每次对集合的修改这个值都会加1，在遍历前记录这个值到expectedModCount中，遍历中检查两者是否一致，如果出现不一致就说明有修改，则抛出ConcurrentModificationException异常。
底层数组存/取元素效率非常的高(get/set)，时间复杂度是O(1)，而查找（比如：indexOf，contain），插入和删除元素效率不太高，时间复杂度为O(n)。
插入/删除元素会触发底层数组频繁拷贝，效率不高，还会造成内存空间的浪费，解决方案：linkedList
查找元素效率不高，解决方案：HashMap（红黑树）
三、手写ArraryList源码
List接口
package com.xuchang.ds.list;public interface List<E> {//返回线性表的大小public int getSize();//判断线性表中是否为空public boolean isEmpty();//判断线性表中是否包含元素oboolean contains(E o);//在线性表中查找元素o，若成功找到，返回其位置index；否则，返回-1public int indexOf(E e);//获取线性表中 位置为index的元素public E get(int index);//将线性表中 位置为index的元素设置为epublic void set(int index, E e);//在线性表中位置为index处添加元素epublic void add(int index, E e);//删除并返回线性表中位置为index的元素public E remove(int index);}ArraryList代码
package com.xuchang.ds.list;import java.util.Arrays;public class ArrayList<E> implements List<E> { private static final int DEFAULT_CAPACITY=10; private E[] data; private int size; public ArrayList(int capacity) { if(capacity < 0) { throw new IllegalArgumentException("数组容量不能为负..."); } data=(E[]) new Object[capacity]; size=0; } public ArrayList() { this(DEFAULT_CAPACITY); } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size==0; } @Override public boolean contains(E o) { for(int i=0; i<size; i++) { if(data[i].equals(o)) { return true; } } return false; } @Override public int indexOf(E e) { for(int i=0; i<size; i++) { if(data[i].equals(e)){ return i; } } return -1; } @Override public E get(int index) { if(index < 0 || index >=size) { throw new IllegalArgumentException("数组下标越界..."); } return data[index]; } @Override public void set(int index, E e) { if(index < 0 || index >=size) { throw new IllegalArgumentException("数组下标越界..."); } data[index]=e; } @Override public void add(int index, E e) { if(index < 0 || index > size) { throw new IllegalArgumentException("数组下标越界..."); } if(size==data.length) { grow(2*data.length); } //TODO when the size is full, copy in the grow method for(int i=size-1; i>=index; i--) { data[i+1]=data[i]; } data[index]=e; size++; } private void grow(int newcapacity) { /* E[] newdata=(E[]) new Object[newcapacity]; for(int i=0; i<data.length; i++) { newdata[i]=data[i]; } data=newdata;*/ if(newcapacity <=DEFAULT_CAPACITY){ return; } data=Arrays.copyOf(data, newcapacity); } @Override public E remove(int index) { if(index < 0 || index >=size) { throw new IllegalArgumentException("数组下标越界..."); } E val=data[index]; for(int i=index + 1; i < size; i++) { data[i-1]=data[i]; } //TODO if(size < data.length /2 ) { grow(data.length / 2); } size--; data[size]=null; return val; } public static void main(String[] args) { List<Integer> list=new ArrayList<Integer>(); for(int i=0; i<100; i++) { list.add(i, i); } for(int i=0; i<list.getSize(); i++) { System.out.println("The " + i + "th element is: " + list.get(i)); } for(int i=0; i<50; i+=5) { list.remove(i); } for(int i=0; i<list.getSize(); i++) { System.out.println("After removing, The " + i + "th element is: " + list.get(i)); } }}作者：xuchang_2020链接：https://juejin.cn/post/6869361956504305678来源：掘金著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
发表评论