arraylist 源码分析
1. 数组介绍
数组是数据结构中很基本的结构, 很多编程语言都内置数组, 类似于数据结构中的线性表
在 java 中当创建数组时会在内存中划分出一块连续的内存, 然后当有数据进入的时候会将数据按顺序的存储在这块连续的内存中. 当需要读取数组中的数据时, 需要提供数组中的索引, 然后数组根据索引将内
存中的数据取出来, 返回给读取程序. 在 Java 中并不是所有的数据都能存储到数组中, 只有相同类型的数据才可以一起存储到数组中.
因为数组在存储数据时是按顺序存储的, 存储数据的内存也是连续的, 所以他的特点就是: 寻址读取数据比较容易, 插入和删除比较困难.
带参构造方法
- public ArrayList(int initialCapacity) {
- if (initialCapacity> 0) {
- // 创建指定长度的数组
- this.elementData = new Object[initialCapacity];
- } else if (initialCapacity == 0) {
- // 空数组
- this.elementData = EMPTY_ELEMENTDATA;
- } else {
- throw new IllegalArgumentException("Illegal Capacity:"+
- initialCapacity);} // 如果既不大于零, 也不小于零, 就会报错抛出异常
- }
空参构造方法
- public ArrayList() {
- this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 给一个成员变量赋值
- }
- private static final Object[] DEFAULTCAPACITY EMPTY ELEMENTDATA={}; // 空参构造方法创建的数组就是一个空的
下面这个用的不多, 能看懂即可
- public ArrayList(Collection<? extends E> c) {
- elementData = c.toArray(); // 把 Collection 这个集合也变成了一个数组, 传给了当前数组 elementData
- // 大于 0, 就拷贝数组
- if ((size = elementData.length) != 0) { // 判断当前 elementData 数组的长度, 如果不等于 0
- if (elementData.getClass() != Object[].class) // 判断类型是不是 Object 数组类型, 如果不是这个类型
- elementData = Arrays.copyOf(elementData, size, Object[].class); // 拷贝一个数组, 然后长度, 然后把 Object[].class 数组传进去, 然后生成一个 elementData 数组
- // 不是大于 0, 就拷贝一个空的
- } else {
- // replace with empty array.
- this.elementData = EMPTY_ELEMENTDATA; // 设置为空数组
- }
- }
添加元素
- public boolean add(E e) {
- // 检测是否需要扩容
下 ¹ensureCapacityInternal(minCapacity:size + 1); // size 是当前存的数据个数
- // 数组赋值
- elementData[size++] = e;
- return true;
- }
扩容的入口方法, 计算容量
private void 上 ¹ensureCapacityInternal(int minCapacity){ //minCapacity 最小值, 传的时候就是 + 1 后的
下下 ³ensureExplicitCapacity(下 ²calculateCapacity(elementData,minCapacity)); // 计算容量, 传入一个数组 elementData, 再传一个最小容量 minCapacity
计算最小容量
private static int 上 ²calculateCapacity(Object[] elementData, int minCapacity){
- // 如果 elementData 是空的
- if(elementData==DEFAUL TCAPACITY EMPTY EL EMENTDAT)|
- // 返回一个默认或者 minCapacity, 最后是返回其中最大的
- return Math. max(DEFAULT_CAPACIT minCapacity);
- // 不是空, 就返回 size+1 的值
- return minCapacity;
- }
private void 上上 ³ensureExplicitCapacity(int minCapacityp{
- // 只要发生修改就 + 1
- modCount++;
- // 是否满足扩容的条件 最小容量 (当前数组存值得容量?) - object 数组的长度
- if(minCapacity-elementData. length〉0)//elementData.lenth=10 (默认容量为 10)
下 ¹grow(minCapacity);
modCount++ : 该字段表示 list 结构上被修改的次数. 在对集合进行新增或移除操作时会使 modCount+1, 这是一个记录集合变化次数的变量.
作用是在使用迭代器 Iterator 对集合进行遍历时, 用 modCount 来判断集合内数据没有发生变化, 否则会抛出异常.
数组扩容方法
private void 上 ¹grow(int minCapacity){
- // 计算当前数组容量, 也就是老的容量
- int oldCapacity=elementData. length;
- // 新的数组容量 = 老容量 + 老容量 / 2 (老容量的 1.5 倍)
int newCapacity=oldCapacity+(oldCapacity>>1);>>1 除二
- // oldcapacity=10
- // oldcapacity>>1
- // 0000 1010>> 1
- // 0000 0101 = 5
- // 判断新的数组容量 - 之前最小容量
- if(newCapacity-minCapacity<0)
- newCapacity=minCapacity;
- if (newCapacity - MAX_ARRAY_SIZE>0) //MAX_ARRAY_SIZE: 值特别大, 如果新的数组比它还大, 就越界了, 或者直接返回最大长度
- newCapacity = hugeCapacity(minCapacity);
- elementData=Arrays. copyof(elementData, newCapacity);
- public void add(int index, E element) {
- // 判断下标是否越界
下 1rangeCheckForAdd(index);
- // 检测是否需要扩容
- ensureCapacityInternal(size + 1);
- // 把 index 之后的所有元素向后移动一位
- System.arraycopy(elementData, index, elementData, index + 1,
- size - index);
- // 将 index 位置覆盖上新值
- elementData[index] = element;
- size++;
- }
private void 上 1rangeCheckForAdd(int index){
- if(index>size || index<0)
- throw new IndexOutofBoundsException(outofBoundsMsg(index));
System.arraycopy(elementData, index, elementData, index + 1,size -index); 举例
- int[] elementData = new int[10];
- for(int i=0;i<5;i++){ // 数组的下标 0,1,2,3,4
- elementData[i]=i+1; // 数组的值 1,2,3,4,5
- System. out. println("=="+Arrays. toString(elementData));
- int size=5;
- int index=1; // 插入数组下标位置
System. arraycopy(elementData, index, elementData, destPos: index+1, length: size-index); 原数组, 插入指定的位置, 又指定的数组, 指定的位置为当前位置 + 1, 到 5-1=4 的位置 >> 从插入位置往后算
System. out. println("--"+Arrays. toString(elementData));
打印结果
== [1,2,3,4,5,0,0,0,0,0]
一 [1,2,2,3,4,5,0,0,0,0] 2: 是要插入的数值
删除方法
指定位置删除
public E remove(int index) {
检测当前下标是否越界
下 1rangeCheck(index);
- modCount++;
- E oldValue = elementData(index);
将 index+1 及之后的元素向前移动一位, 覆盖被删除的值
- int numMoved = size - index - 1;
- if (numMoved> 0)
下下 2System.arraycopy(elementData, index+1, elementData, index,
numMoved);
将最后一个位置的元素清空
- elementData[--size] = null;
- return oldValue;
- }
private void 上 1rangeCheck(int index){
- if(index>=size)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
上上 2 System.arraycopy(elementData, index+1, elementData, index, numMoved); 举例 int[] elementData = new int[10];
- for(int i=0;i<10;i++){
- // 数组的下标 0,1,2,3,4,5,6,7,8,9
- elementData[i]=i+1; // 数组的值 1,2,3,4,5,6,7,8,9,10
- }
- int size = elementData.lengh; // 数组里有几个数, 长度就是几 elementData.lengh = 10
- int index = 2;
- int numMoved = size - index - 1;
- System. out. println("==" + Arrays. toString(elementData));
System. arraycopy(elementData, srcPos: index+1, elementData, index, numMoved); 原数组, 指定的位置为要删除的下标往后一个位置, 又指定的数组, 删除位置的下标, 10-2-1=7>> 从指定删除下标位置往后数, 全部向前移动一位
System. out. println("--" + Arrays. toString(elementData));
打印结果
== [1,2,3,4,5,6,7,8,9,10] 3: 要删除的数字
一 [1,2,4,5,6,7,8,9,10,10]
指定元素删除
- public boolean remove(Object o) {
- if (o == null) {
- for (int index = 0; index <size; index++)
- if (elementData[index] == null) {
下 1fastRemove(index);
- return true;} // 从 0 开始遍历, 大小为数组长度, 找到后直接删除
- } else {
- for (int index = 0; index < size; index++)
- if (o.equals(elementData[index])) {
- fastRemove(index);
- return true;
- }
- }
如果没有匹配元素, 返回 false
- return false;
- }
快速删除, 没有检测 index 下标的原因: 因为之前需要指定下标删除, 现在是直接指定删除某个元素, 如果元素不存在, for 语句遍历也不会找到这个元素, 所有, 只要能满足两个 if 语句其中一个, 那这个元素一定在我的合理范围内的, 所以就不需要检测有没有下标
快速删除, 没有检测 index 下标
private void 上 1fastRemove(int index) {
- modCount++;
- 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
- }
来源: https://www.cnblogs.com/xiaozhongfeixiang/p/11514674.html