Java集合类图
image.png
图片来源网络，权侵删。
List接口通常表示为一个列表（数组、链表、队列和栈）常用实现类有ArrayList和LinkedList
ArrayList
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;
//如果创建ArrayList时候指定大小为0的时候返回改对象
private static final Object[] EMPTY_ELEMENTDATA = {};
//调用无参构造方法的时候返回改对象，往数组里面添加元素的时候会调用ensureCapacity方法进行扩容
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//数组存储的对象
transient Object[] elementData;
//数组的大小
private int size;
构造方法
public ArrayList(int initialCapacity) {
//大于0的时候直接进行初始化
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
//等于0的时候直接返回上文提到的EMPTY_ELEMENTDATA
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
//小于0抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() {
//调用无参构造方法的时候指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
//集合转化为数组
elementData = c.toArray();
//数组长度赋值给size 并且判断不等于0
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//如果elementData.getClass返回不会Object[].class类型的。使用 Arrays.copyOf copy一份新的大小为size 类型为Object[].class 的数组，此处可查看java官方6260652的bug
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {//等于0用EMPTY_ELEMENTDATA代替
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
将数组缓冲区大小调整为实际缓冲区大小
public void trimToSize() {
modCount++;
//当数组实际大小<小于缓冲区大小时 比如使用默认构造函数时，向list中添加一个元素时，此时elementData.length=10,size=1
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
add方法
public boolean add(E e) {
//确保数组容量够用 使用size+1进行确认
ensureCapacityInternal(size + 1); // Increments modCount!!
//数组赋值
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果使用的是默认的无参构造函数 ,首次添加元素的时候，则返回默认的长度大小10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//modCount++
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//此时minCapacity =10 elementData.length = 0
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容
private void grow(int minCapacity) {
//使用默认构造方式首次添加的时候oldCapacity =0
int oldCapacity = elementData.length;
//扩容大小为原来的1.5倍 首次的时候也为0
int newCapacity = oldCapacity + (oldCapacity >> 1)
if (newCapacity - minCapacity < 0)
//初始化为10
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//构造一个大小为newCapacity的数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
public void add(int index, E element) {
//index越界校验
rangeCheckForAdd(index);
//数组大小确认是否扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//使用System.arraycopy将index及后面的元素向后移动一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//将新的元素放在index这位置上
elementData[index] = element;
//size++
size++;
}
//判断下标是否越界
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
get方法
public E get(int index) {
//index范围校验
rangeCheck(index);
//数组元素返回
return elementData(index);
}
set方法
public E set(int index, E element) {
//index索引校验
rangeCheck(index);
//获取旧值
E oldValue = elementData(index);
//覆盖旧值
elementData[index] = element;
//返回旧值
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
根据index删除
public E remove(int index) {
//index校验
rangeCheck(index);
//modCount+++
modCount++;
//获取旧值
E oldValue = elementData(index);
//获取要移动的元素
int numMoved = size - index - 1;
//使用System.arraycopy将index后面的元素向前移动
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//数组最后一位指向null
elementData[--size] = null; // clear to let GC do its work
//返回旧值
return oldValue;
}
根据元素删除
public boolean remove(Object o) {
//如果要删除的元素为null
if (o == null) {
//遍历数组进行删除
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
//要删除的元素不为null
for (int index = 0; index < size; index++)
//使用equals方法进行判断删除
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
