Java集合-ArrayList
# Java集合-ArrayList
List接口的可调整大小的数组实现。实现所有可选列表操作,并允许所有元素,包括null 。除了实现List接口之外,该类还提供了一些方法来操作内部用于存储列表的数组的大小。 (这个类大致相当于Vector ,除了它是不同步的。)
继承体系:
属性:
/**
* 默认初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于空实例的共享空数组实例。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 用于默认大小的空实例的共享空数组实例。我们将其与 EMPTY_ELEMENTDATA 区分开来,以了解添加第一个 * 元素时要膨胀多少。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存储元素的数组
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList的大小
*
* @serial
*/
private int size;
# 构造方法
构造方法一
构造一个具有指定初始容量的空列表。
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 如果传入的初始容量大于0,就新建一个数组存储元素
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 如果传入的初始容量等于0,使用空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 如果传入的初始容量小于0,抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
构造方法二
构造一个初始容量为 10 的空列表。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
构造方法三
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 { // 空集合
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
# add(E e)方法
添加一个元素到集合的尾部
public boolean add(E e) {
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) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
# 扩容函数
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 新容量等于旧容量加上旧容量右移一位,也就是1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新容量还是不够
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);
}
- 新容量 = 旧容量 + 旧容量右移一位(旧容量的0.5)= 旧容量 * 1.5 (扩容是1.5倍)
- 扩容操作实际上是调用Arrays.copyOf()把原数组拷贝为一个新数组,因此最好在创建 ArrayList 对象时就指定大概的容量大小,减少扩容操作的次数。
# add(int index, E element)方法
在此列表中的指定位置插入指定元素。将当前位于该位置的元素(如果有)和任何后续元素向右移动(将其索引加一)
public void add(int index, E element) {
// 检查是否越界
rangeCheckForAdd(index);
// 检查是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// index之后的元素后移
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将元素插入到index的位置
elementData[index] = element;
// 大小增1
size++;
}
# addAll 方法
将集合中所有元素添加到当前ArrayList中。
public boolean addAll(Collection<? extends E> c) {
// 集合转数组
Object[] a = c.toArray();
int numNew = a.length;
// 检查是否需要扩容
ensureCapacityInternal(size + numNew); // Increments modCount
// c中元素全部拷贝到数组的最后
System.arraycopy(a, 0, elementData, size, numNew);
// size增加c的大小
size += numNew;
return numNew != 0;
}
将集合中所有元素添加到ArrayList指定位置后面
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);
// 集合c复制指定位置后面
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
# get 方法
返回此列表中指定位置的元素。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
// 检查给定的索引是否在范围内。如果不是,则引发适当的运行时异常。此方法不检查索引是否为负:它总是在数组访问之前立即使用,如果索引为负,则抛出 ArrayIndexOutOfBoundsException。
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
# set 方法
将此列表中指定位置的元素替换为指定元素。
public E set(int index, E element) {
// 检查范围
rangeCheck(index);
// 获取原始值
E oldValue = elementData(index);
// 赋予新值
elementData[index] = element;
// 返回原始值
return oldValue;
}
# remove(int index) 方法
移除此列表中指定位置的元素。将任何后续元素向左移动(从它们的索引中减去 1)。
public E remove(int index) {
// 检查是否越界
rangeCheck(index);
modCount++;
// 获取index位置的元素
E oldValue = elementData(index);
// 如果index不是最后一位,则将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;
}
# remove(Object o) 方法
从此列表中删除第一次出现的指定元素(如果存在)。
public boolean remove(Object o) {
if (o == null) {
// 遍历整个数组,找到元素第一次出现的位置,并将其快速删除
for (int index = 0; index < size; index++)
// 如果要删除的元素为null,则以null进行比较,使用==
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
// 如果要删除的元素不为null,则进行比较,使用equals()方法
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
快速删除:
private void fastRemove(int index) {
// 少了一个越界的检查
modCount++;
// 如果index不是最后一位,则将index之后的元素往前挪一位
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// 将最后一个元素删除,帮助GC
elementData[--size] = null; // clear to let GC do its work
}
# retainAll方法
仅保留此列表中包含在指定集合中的元素。换句话说,从这个列表中删除所有不包含在指定集合中的元素
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
批量删除
complement为true表示删除c中不包含的元素
complement为false表示删除c中包含的元素
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
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 work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
# removeAll方法
从此列表中删除包含在指定集合中的所有元素。
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
# 参考
上次更新: 2024/06/29, 15:13:44