package java.util;
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认的长度
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 在new ArrayList的这个无参构造方法中会给Object []一个空的对象
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 这个就是ArrayList维护的数组
*/
private transient Object[] elementData;
/**
*集合的大小
*/
private int size;
/**
*可以指定长度
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* 默认无参构造方法,里面会初始化这个维护的数组
*/
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
/**
* 可以传进来一个集合,这里转成数组之后传给elementData
* 然后判断是否是object[]类型,若不是则复制一个给elementData
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {//空数组
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 判断总容量大小+1是否比原数组长度大,即最新的元素能否加进去,加不进去则扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);//扩容
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//容量增加为原来的1.5
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);//拷贝一个新的数组指向原数组
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/****/
public E get(int index) {
rangeCheck(index);//检查下标
return elementData(index);//根据下标拿值
}
/**
*
*/
public E set(int index, E element) {
rangeCheck(index);//检查下标是否越界
E oldValue = elementData(index);
elementData[index] = element;//将新值替换
return oldValue;
}
/**
* 类似 add(int index, E element)方法,不在赘述
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 添加到指定位置
*/
public void add(int index, E element) {
rangeCheckForAdd(index);//检查下标是否越界
ensureCapacityInternal(size + 1); // 会在原来长度基础上+1然后判断当前数组是否为空,若为空判断长度是否大于默认值的10个长度,返回最大值,若之前的长度小于此长度(原长已经满足不了,需要扩容),在此基础上扩展元素的长度为之前+之前的一半,length>>1
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* 相对于根据对象删除效率高些,因为这里是直接根据下标进行删除 ,少了迭代
*/
public E remove(int index) {
rangeCheck(index);//检查下标是否越界
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//这里是将elementData复制到自己本身,从需要删除的位置开始+1,复制的长度为总长度-删除的位置-1也就是将删除位置开始往后的元素全部前移,因为本身长度多了最后一个元素,比如[1,2,3,4],删除index=1的元素这里把3,4插入到之前的元素位置变成[1,3,4,4]多了最后一个元素,后面会把他清除
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; //这里清除最后一个多于的元素
return oldValue;
}
/**
* 根据对象删除,遍历数组,找到第一个符合的元素进行删除,删除步骤请看fastRemove()方法
*/
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)
//这里是将elementData复制到自己本身,从需要删除的位置开始+1,复制的长度为总长度-删除的位置-1也就是将删除位置开始往后的元素全部前移,因为本身长度多了最后一个元素,比如[1,2,3,4],删除index=1的元素这里把3,4插入到之前的元素位置变成[1,3,4,4]多了最后一个元素,后面会把他清除
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // 清除最后一个多余的元素
}
/**
*遍历数组,将每一个元素的值都置为null
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
看上面几个方法,不在赘述
*/
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);
size += numNew;
return numNew != 0;
}
/**
看上面几个方法,不在赘述
*/
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);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
}