Java ArrayList解密

发布时间:2024年01月01日

????????数组的大小是固定的,一旦创建的时候指定了大小,就不能再调整了。也就是说,如果数组满了,就不能再添加任何元素了。

????????ArrayList 在数组的基础上实现了自动扩容,并且提供了比数组更丰富的预定义方法(各种增删改查),非常灵活。

? ? ? ? 下面我们就来探究一下ArrayList的各个方法的实践和原理,以及算法复杂度

一、创建ArrayList

? ? ? ? 创建方式:

ArrayList<String> alist = new ArrayList<String>();

? ? ? ? 看看ArrayList的构造函数:

? ? ? ? 如果初始化大小的话,会构造一个这样长度的object数组;如果初始化为0或者不填的话,就会创建一个空数组。

? ? ? ? 也可以看出,如果非常确定 ArrayList 中元素的个数,在创建的时候还可以指定初始大小,可以有效地避免在添加新的元素时进行不必要的扩容。

二、添加元素?

alist.add("xxx");

? ? ? ? 可以看出来,add过程分为两步,第一步确保数组的大小足够,第二步将元素添加到末尾

2.1?calculateCapacity

? ? ? ? 进去看?ensureCapacityInternal,源码如下:

? ? ? ? 那么首先先看?calculateCapacity,这个函数是为了确定数组的大小。

? ? ? ? 如果数组是空的,那大小就是max {当前size+1,默认大小},源码中默认大小是10;如果数组不为空,那就返回他的指定大小

??

2.2?ensureCapacityInternal

? ? ? ? 确保数组的大小足够。如果数组要溢出了,就要调用grow方法扩容?

?

2.3 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);

2.4 总结

堆栈过程图示:
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++; // 元素个数加一
}

3.1??rangeCheckForAdd

? ? ? ? 判断索引是否越界,越界了就抛错?

3.2??ensureCapacityInternal

? ? ? ? 上面已经讲过,不多赘述。

四、更新元素

alist.set(0, "");

?

public E set(int index, E element) {
    rangeCheck(index); // 检查索引是否越界

    E oldValue = elementData(index); // 获取原来在指定位置上的元素
    elementData[index] = element; // 将新元素替换到指定位置上
    return oldValue; // 返回原来在指定位置上的元素
}

4.1 elementData

? ? ? ? 获取索引位置数组?

五、删除指定位置元素?

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。?

?

6.1 fastRemove?

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()?方法类似,不过遍历的时候从最后开始。?

八、各个方法时间复杂度?

  • get? ? ? ? O(1)
  • add? ? ? ?最好O(1),在末尾插入;最坏O(n),插入后移动数组
  • remove 最好O(1),在末尾删除;最坏O(n),删除后移动数组
  • set? ? ? ? O(1)

?参考:

深入探讨 Java ArrayList:从源码分析到实践应用 | 二哥的Java进阶之路

文章来源:https://blog.csdn.net/m0_49499183/article/details/135326628
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。