????????数组的大小是固定的,一旦创建的时候指定了大小,就不能再调整了。也就是说,如果数组满了,就不能再添加任何元素了。
????????ArrayList 在数组的基础上实现了自动扩容,并且提供了比数组更丰富的预定义方法(各种增删改查),非常灵活。
? ? ? ? 下面我们就来探究一下ArrayList的各个方法的实践和原理,以及算法复杂度
? ? ? ? 创建方式:
ArrayList<String> alist = new ArrayList<String>();
? ? ? ? 看看ArrayList的构造函数:
? ? ? ? 如果初始化大小的话,会构造一个这样长度的object数组;如果初始化为0或者不填的话,就会创建一个空数组。
? ? ? ? 也可以看出,如果非常确定 ArrayList 中元素的个数,在创建的时候还可以指定初始大小,可以有效地避免在添加新的元素时进行不必要的扩容。
alist.add("xxx");
? ? ? ? 可以看出来,add过程分为两步,第一步确保数组的大小足够,第二步将元素添加到末尾
? ? ? ? 进去看?ensureCapacityInternal,源码如下:
? ? ? ? 那么首先先看?calculateCapacity,这个函数是为了确定数组的大小。
? ? ? ? 如果数组是空的,那大小就是max {当前size+1,默认大小},源码中默认大小是10;如果数组不为空,那就返回他的指定大小
??
? ? ? ? 确保数组的大小足够。如果数组要溢出了,就要调用grow方法扩容?
?
// 检查是否会导致溢出,oldCapacity 为当前数组长度
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); // 扩容至数组的最大长度
// 将当前数组复制到一个新数组中,长度为 newCapacity
elementData = Arrays.copyOf(elementData, newCapacity);
堆栈过程图示:
add(element)
└── if (size == elementData.length) // 判断是否需要扩容
├── grow(minCapacity) // 扩容
│ └── newCapacity = oldCapacity + (oldCapacity >> 1) // 计算新的数组容量
│ └── Arrays.copyOf(elementData, newCapacity) // 创建新的数组
├── elementData[size++] = element; // 添加新元素
└── return true; // 添加成功
alist.add(0, "");
? ? ? ? 上面讲清楚?ensureCapacityInternal之后,这里就很容易理解了。
public void add(int index, E element) {
rangeCheckForAdd(index); // 检查索引是否越界
ensureCapacityInternal(size + 1); // 确保容量足够,如果需要扩容就扩容
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // 将 index 及其后面的元素向后移动一位
elementData[index] = element; // 将元素插入到指定位置
size++; // 元素个数加一
}
? ? ? ? 判断索引是否越界,越界了就抛错?
? ? ? ? 上面已经讲过,不多赘述。
alist.set(0, "");
?
public E set(int index, E element) {
rangeCheck(index); // 检查索引是否越界
E oldValue = elementData(index); // 获取原来在指定位置上的元素
elementData[index] = element; // 将新元素替换到指定位置上
return oldValue; // 返回原来在指定位置上的元素
}
? ? ? ? 获取索引位置数组?
public E remove(int index) {
rangeCheck(index); // 检查索引是否越界
modCount++; //集合实际被修改的次数+1,这个是ArrayList的一个成员变量
E oldValue = elementData(index); // 获取要删除的元素
int numMoved = size - index - 1; // 计算需要移动的元素个数
if (numMoved > 0) // 如果需要移动元素,就用 System.arraycopy 方法实现
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // 将数组末尾的元素置为 null,让 GC 回收该元素占用的空间
return oldValue; // 返回被删除的元素
}
list.remove("");
? ? ? ? 分为元素为null和不为null的情况,区别在于,为null的时候用==判断,不为null的时候用equals判断,逻辑上并没有什么区别。
? ? ? ? 如果找到元素,用fashRemove方法删除元素,返回true;找不到元素就返回false。?
?
private void fastRemove(int index) {
int numMoved = size - index - 1; // 计算需要移动的元素个数
if (numMoved > 0) // 如果需要移动元素,就用 System.arraycopy 方法实现
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // 将数组末尾的元素置为 null,让 GC 回收该元素占用的空间
}
list.indexOf("");
list.lastIndexOf("");
????????如果要正序查找一个元素,可以使用?indexOf()
?方法;如果要倒序查找一个元素,可以使用?lastIndexOf()
?方法。
lastIndexOf()
?方法和?indexOf()
?方法类似,不过遍历的时候从最后开始。?
?参考: