1、ArrayList继承和实现结构
ArrayList继承抽象的list类AbstractList,实现了List接口,Serializable接口。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
2、ArrayList的底层实现结构是什么?默认的初始化容量是多少?
答:ArrayList底层采用数组进行实现,并且在不指定初始化容量的时候,默认的初始化容量为:10。
private static final int DEFAULT_CAPACITY = 10; //默认的初始化容量设置为10 transient Object[] elementData; //底层采用对象数组进行元素的存储
3、底层的构造器
(1)空参构造器,底层的数组变量elementData 默认初始化为一个空数组,只有当我们第一次向list中添加数据的时候,才会将elementData 重新赋值为一个长度为10的数组,这个过程还是比较复杂的,具体可以看下面的讲解(ArrayList第一次添加元素时所经历的一系列操作)。
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //这里将elementData 数组初始化为一个空数组,并不是直接就初始化为一个长度为10 的数组,这个过程是在第一次添加元素的时候才进行的 }
(2)带参构造器,将参数传入的一个集合类型变量c转换成数组,添加到list底层的数组中。
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; } }
4、ArrayList第一次添加元素时所经历的一系列操作。
(1)在我们调用无参构造器创建list对象的时候,底层会将elementData 数组初始化为一个空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA(private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
);
(2)当我们第一次调用add()方法往list中添加元素的时候(list.add("tmj");
),进入到add()方法体;
public boolean add(E e) { ensureCapacityInternal(size + 1); // 进行数组的容量保证,如果第一次添加,此时的elementData还是空数组 //就需要将elementData赋值为一个长度为默认10的数组对象,如果不是第一次添加,就需要进行数组容量判断,检查当前的elementData数组是否还有剩余的位置存放, //如果容量不够,需要进行扩容,再将扩容的数组赋值为elementData变量,就完成数组的扩容 elementData[size++] = e; //容量保证完成后,就将元素放到记录的index索引处,这里就是size对应的索引。 return true; }
(3)ensureCapacityInternal()方法调用;
private void ensureCapacityInternal(int minCapacity) { //当第一次调用add方法时,minCapacity为1,就代表这个底层数组最小的容量为minCapacity,因为必须将元素放下 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //第一次add时,会进入这个代码块 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); //第一次进来的时候minCapacity=1,所以和默认的容量10相比,最终得到minCapacity选取两者较大这 = 10 } ensureExplicitCapacity(minCapacity); //这个方法用于对判断数组是否需要进行扩容 }
(4)ensureExplicitCapacity()方法调用
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) //如果我们需要的最小容量小于了当前数组的容量(第一次add时,当前数组容量为0),就调用grow()进行数组的扩容 grow(minCapacity); }
(5)grow()方法调用
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //原先数组的容量 int newCapacity = oldCapacity + (oldCapacity >> 1); //进行扩容后数组的新容量,newCapacity = oldCapacity + oldCapacity /2; //这里就是关键点,可以看出,每次进行数组扩容的时候,都是将新的数组扩容为原先数组容量的1.5倍。这里的右移就代表除2操作。 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); //完成数组中元素的转移 }
5、常用方法介绍
(1)toArray():
将一个list对象转换成对应的数组对象
(2)get(int index):
返回指定索引位置上的元素
public E get(int index) { rangeCheck(index); //索引范围检查 return elementData(index); }
(3)set(int index, E element):
将某个索引位置上的元素设置为新的元素,并返回原先元素的值。
public E set(int index, E element) { rangeCheck(index); //索引检查 E oldValue = elementData(index); elementData[index] = element; return oldValue; }
(4)add(E e):
添加一个元素到list中
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
(5)add(int index, E element):
在指定的索引位置上添加元素,这个操作会导致该index后续的其他元素依次后移,腾出一个空间给新的元素。
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++; }
(6)remove(int index)
:删除指定索引位置上的元素,这个操作会导致index后面的元素依次往前面移动,并且size–,list中元素个数减1。
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; }
(7)remove(Object o):
从list中移除查找到的第一个特定的对象o,如果有多个相同的对象,只会移除第一个,返回是否移除对象,如果list中没有该对象,返回false,否则返回true。如果需要移除多个,可以自己写一个循环进行迭代删除。
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; }
(8)clear():
清空这个list中的元素,实际上就是将底层的数组每个位置上的值都设置为null并将size设置为0,这样可以帮助GC进行垃圾回收。
public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
(9)removeRange(int fromIndex, int toIndex):
移除list中某个index1到另外一个index2之间的所有元素。
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 work int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; }