数据结构 | 动态数组ArrayList

数据结构 | 动态数组ArrayList

前言

  • 开了一个新的系列,自己动手撸简化版的 Java 集合,在实践中学习数据结构
  • 参考资料来自小码哥的数据结构和算法视频课,地址在文章尾部,感觉是最好的数据结构算法课了,手把手带我敲代码和优化代码,很多写法和 JDK 源码很相似,顺便把源码给看了,一举两得

数组

  • 数组是一种顺序存储的线性表, 所有元素的内存地址都是连续的
  • 在很多编程语言中,数组有个致命的缺点,无法动态修改容量

数组

  • 实际开发中我们希望数组的容量是动态变化

实现 ArrayList

希望实现一个动态数组,数组容量可以动态变化,并且实现增、删、改、查、插、遍历等操作

1. 属性

底层使用数组存储元素,size 记录当前已经存入的元素个数

public class ArrayList<E> {
    // 当前存储的数据的长度(元素个数)
    private int size = 0;
    // 用于存储数据的数组
    private E[] elements ;
    // 默认初始容量
    private static final int DEFAULT_INITIAL_CAPACITY = 10;
    // 查询不存在时的返回值
    private static final int MINUS_ONE = -1;
}

2. 构造器

提供两个构造器,可以指定初始容量

// 空参构造器,数组初始化长度为10;
public ArrayList() {
    this(DEFAULT_INITIAL_CAPACITY);
}
// 指定容量的构造器,如果小于默认初始容量,则依旧使用默认初始容量
public ArrayList(int capacity) {
    capacity = Math.max(DEFAULT_INITIAL_CAPACITY,capacity);
    elements = (E[]) new Object[capacity];
}

3. 添加元素

  • 添加元素之前,要检查底层数组容量是否满足,如果容量不足,需要先进行扩容
  • 添加元素之前,插入位置之后的元素需要从后向前移动元素,如果从前向后移动元素,那么会进行元素覆盖, 最后出错
// 将元素添加至 ArrayList 尾部
public void add(E ele) {
    add(size,ele);
}

// 将元素添加至指定 index 处
public void add(int index,E ele) {
    checkRangeForAdd(index);

    // 添加元素后,size+1,所以要保证数组至少有 size+1 的容量
    ensureCapacity(size+1);

    // 从后向前依次拷贝元素,tips:尽量减少 for 循环检查条件是有计算 (i>index 这句)
    // 可以使用 System 类提供的数组拷贝方法代替,速度更快,这也是 IDEA 推荐的
    // if (size - index >= 0) System.arraycopy(elements, index, elements, index + 1, size - index);
    for(int i=size;i>index;i--) {
        elements[i] = elements[i-1];
    }
    elements[index] = ele;
    size++;
}

4.1 扩容机制

ArrayList扩容

// 扩容机制,保证当前数组容量至少为capacity
private void ensureCapacity(int capacity) {
    int oldCapacity = elements.length;
    if(oldCapacity >= capacity) {
        return;
    }

    // 位运算,效率更高,容量扩大为之前的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 创建一个新的数组,大小为之前数组的 1.5 倍
    E[] newElements = (E[]) new Object[newCapacity];
    // 拷贝元素
    // arraycopy 的机制是整块内存的拷贝
    // if (size >= 0) System.arraycopy(elements, 0, newElements, 0, size);
    for(int i=0;i<size;i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;
}

4. 删除元素

如果有需求,可以在删除元素后进行缩容,但是要注意,扩容的倍数和缩容的时机设计不合理(互为倒数),会导致复杂度振荡,也就是在缩容时机附近反复添加删除元素,会导致复杂度急剧上升

// 删除 index 位置上的元素,返回被删除的元素
public E remove(int index) {
    checkRange(index);
    E old = elements[index];
    // 从前往后拷贝元素,依然可以用 arraycopy 优化
    // if (size - index + 1 >= 0) System.arraycopy(elements, index + 1, elements, index + 1 - 1, size - index + 1);
    for(int i=index+1;i<size;i++) {
        elements[i-1] = elements[i];
    }
    // 先size减1,再将size位置上的元素置null
    elements[--size] = null;
    // 判断数组是否需要缩容
    trim();
    return old;
}

4.1 缩容机制

// 缩容机制
private void trim() {
    int oldCapacity = elements.length;
    // 如果元素个数大于当前容量的一半,或者容量已经小于默认初始容量,就不要继续缩容
    if(size >= oldCapacity >> 1 || oldCapacity <= DEFAULT_INITIAL_CAPACITY) return;
    // 缩容为之前的一半
    int newCapacity = oldCapacity >> 1;
    E[] newElements= (E[]) new Object[newCapacity];
    for(int i=0;i<size;i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;
}

5. 清空

清空 ArrayList 需要将每个数组元素置空,再将 size 设置为 0,因为 ArrayList 中存的实际是对象的引用,如果没有引用指向对象,对象就会被 JVM 作为垃圾回收

ArrayList清空

// 清空元素
public void clear() {
    for(int i=0;i<size;i++) {
        elements[i] = null;
    }
    size = 0;
}

6. 设置元素

// 修改指定索引位置上的元素,并返回旧的元素
public E set(int index,E ele) {
    checkRange(index);
    E old = elements[index];
    elements[index] = ele;
    return old;
}

7. 获取元素

// 返回指定索引位置上的元素
public E get(int index) {
    // 控制入参,如果非法,抛出异常
    checkRange(index);
    return elements[index];
}

8. 判断是否为空

// 判断当前 ArrayList 是否为空
public boolean isEmpty() {
    return size==0;
}

9. ArrayList 长度

// 返回当前 ArrayList 的长度(元素数量,不是数组容量)
public int size() {
    return size;
}

10. 元素的位置

对于 null 的判断需要特别处理

// 返回 target 元素的第一次出现的索引,如果不存在,返回-1
public int indexOf(E target) {
    // 允许存入 null 值,注意不要空指针调用equals()
    if(target==null) {
        for(int i=0;i<size;i++) {
            if(elements[i]==null) {
                return i;
            }
        }
    }else {
        for(int i=0;i<size;i++) {
            if(target.equals(elements[i])) {
                return i;
            }
        }
    }
    return MINUS_ONE;
}

11. 是否包含元素

// 判断当前 ArrayList 是否包含某元素
public  boolean contain(E target) {
    return indexOf(target) != MINUS_ONE;
}

12. 打印

重写 toString 方法

@Override
public String toString() {
    StringBuilder str = new StringBuilder();
    str.append("size=").append(size).append(", [");
    // StringBuilder 的 append 方法如果拼接的是对象,会调用其 toString 方法后拼接
    for(int i=0;i<size;i++) {
        if(i!=0) {
            str.append(", ");
        }
        str.append(elements[i]);
    }
    str.append("]");
    return str.toString();
}

13. 索引检查

// 入参 index 非法报错
private void indexOutOfBounds() {
    throw new IndexOutOfBoundsException("数组索引越界!");
}

// 检查传入的 index 是否满足边界条件
private void checkRange(int index) {
    if(index<0||index>=size) {
        indexOutOfBounds();
    }
}

// 针对 add 方法的索引合法检查,index 可以是 size,即添加至尾部
private void checkRangeForAdd(int index) {
    if(index<0||index>size) {
        indexOutOfBounds();
    }
}

复杂度

对于 add 和 remove 操作,复杂度来自向后或向前移动元素的操作,扩容或缩容的复杂度是 $O(N)$,但是均摊后复杂度依然是 $O(1)$

操作最好最坏平均
add(int index,E ele)$O(1)$$O(N)$$O(N)$
remove(int index)$O(1)$$O(N)$$O(N)$
set(int index,E ele)$O(1)$$O(1)$$O(1)$
get(int index)$O(1)$$O(1)$$O(1)$

参考