本文参考整理自小码哥的《恋上数据结构和算法》课程，图片转自课程ppt，如有侵权，请联系删除~

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

为了解决数组的这个缺点，这里引入了动态数组（ArrayList）

接口设计

• 创建ArrayList类，创建size成员变量来管理数组中元素的个数，创建elements成员变量（数组）来存取数据
• 基本操作：增删改查以及动态扩容

下方列出的接口只是部分常用接口，在Java官方的ArrayList中还有一些未列出的接口

int size();                                //元素的数量
boolean isEmpty();                        //是否为空
boolean contains(E element);            //是否包含某个元素
void add(E element);                    //添加元素到最后面
E get(int index);                        //返回index位置对应的元素
E set(int index, E element);            //设置index位置的元素
void add(int index, E element);            //往index位置添加元素
E remove(int index);                    //删除index位置对应的元素
int indexOf(E element);                    //查看元素的位置
void clear();                            //清空

代码实现

• 为了使动态数组可传入的数据可根据用户需求自行指定，这里使用泛型实现，对泛型不了解的可以查看前面的JavaSE系列教程

构造方法

public class ArrayList<E> {
    private int size;
    private E[] elements;
    private static final int CAPACITY_DEFAULT  = 10;
    private static final int ELEMENT_NOT_FOUND = -1;
    /**
     * @Description:有参构造
     * @param capacity:  容量
     * @return: null
     */
    public ArrayList(int capacity){
        capacity = capacity > CAPACITY_DEFAULT ? capacity : CAPACITY_DEFAULT;
        elements = (E[]) new Object[capacity];
    }
    /**
     * @Description:无参默认使用10作为容量调用有参构造
     * 无参方法
     * @return: null
     */
    public ArrayList(){
        this(CAPACITY_DEFAULT);
    }
}

• 在有参构造中，传入的参数capacity即为指定的初始数组容量，这里我们使用一个常量CAPACITY_DEFAULT作为默认值，为了减少数组扩容次数，默认指定为10

  如果传入参数小于10，我们统一使用默认值10作为初始容量

• 无参构造直接使用默认值调用有参构造对动态数组进行初始化

新增

• 在增加操作中，分为两类

  • 一类是直接传递一个参数，在数组尾部插入（E element）
  • 一类是指定插入位置（int index, E element）

这里采用方法重载，对同一个方法，不同参数做重载，让他实现两种增加元素类型

指定位置增加

如图所示，对动态数组进行指定位置增加操作时，需要将index位置及后续位置元素统一向后移动一位，然后将element插入到index位置

注意：在进行元素后移时，需要从后（size）往前（index）移动，如果弄反的话，就会出现上图中的错误覆盖情况，导致数据出错

// 往index位置添加元素
public void add(int index, E element) {
    rangeCheckForAdd(index);      // 索引合法检查
    ensureCapacity(size + 1);       // 检查容量
    for(int i = size; i > index; i--){
        elements[i] = elements[i - 1];
    }
    elements[index] = element;
    size++;
}

• 在进行增加操作之前，首先要对传入的索引进行检查，对错误索引抛出异常

private void rangeCheckForAdd(int index) {
    if(index > size || index < 0){
        outOfBounds(index);
    }
}

private void outOfBounds(int index){
    throw new IndexOutOfBoundsException("size:" + size + ", index:" + index);
}

数组扩容

在每次增加操作前，除了对索引的检查，我们还需要对目前数组的容量进行检查，判断是否需要扩容，来实现数组容量的可变

• 数组扩容的基本思想就是新new一个容量更大的数组，将原数组中的值全部移动到新数组，并将elements指向新数组（即断开旧数组的连接）
• 在引用数据类型无法被访问到时（无对象指向该内存），会由Java的垃圾处理机制自动进行回收（释放内存）

new出来的空间，都是存放在堆空间中的，而变量名，都是在栈空间进行保存的

private void ensureCapacity(int capacity){
    int oldCapacity = elements.length;      // 获取当前数组容量
    if(capacity < oldCapacity) return;
    int newCapacity = oldCapacity + (oldCapacity >> 1);     // 扩容1.5倍
    E[] newElements = (E[]) new Object[newCapacity];
    for(int i = 0; i < size; i++){
        newElements[i] = elements[i];
    }
    elements = newElements;     // 指向新数组
}

>>是右移运算，>>1也就是除以2的1次方

<<是左移运算，<<1代表乘2的1次方

这里使用位移运算，直接操作二进制数据，可以提高效率

尾部增加

• 尾部增加可以直接调用指定位置增加的方法，传递参数为size和element
• 通过调用自身方法实现类似方法，可以使后期维护更加方便，在对新增操作有优化时，只需要修改一个方法就能对整个功能进行优化

// 添加元素到最后面
public void add(E element) {
    add(size,element);
}

删除

• 删除方法也可以大体上分为两类

  • 一类是指定索引进行删除
  • 一类是指定元素进行删除

指定索引删除

• 如上图所示，在进行元素删除时，我们同样需要对数组中存储的数据进行移动操作
• 与增加元素有所不同，我们需要将指定的索引处以后的元素统一向前移动一位
• 这里顺序也需要注意，从index+1处开始向前移动，到size截至

// 删除index位置对应的元素
public E remove(int index) {
    rangeCheck(index);
    E old = elements[index];
    for(int i = index; i < size; i++){
        elements[i] = elements[i+1];
    }
    elements[--size] = null;
    trim();
    return old;
}

private void rangeCheck(int index) {
    if(index >= size || index < 0){
        outOfBounds(index);
    }
}

• 当数组元素删除后，剩余的空间可能会很大，这样就会造成大量内存浪费
• 为了避免这种现象，在删除元素后，我们可以对数组进行缩容
• 缩容原理和扩容类似，新创建一个更小的数组，将原数组中的元素移到新数组

public void trim(){
    int capacity = element.length;        // 当前数组容量
    int newCapacity = capacity >> 1;    // 缩容后的容量
    // 当前数组元素大小大于容量2倍或当前容量小于默认值时不缩容
    if(size >= newCapacity || capacity < CAPACITY_DEFAULT) return;
    // 创建新数组
    E[] newElements = (E[]) new Object[newCapacity];
    // 移动元素
    for(int i = 0; i < size; i++){
        newElements[i] = elements[i];
    }
    elements = newElements;
}

注意：在统一前移结束之后，我们还需要对最后一个元素做置空处理

如果不对最后一个元素置空，对应位置仍存储着最后一个对象的地址

如上图所示，5、6索引均指向77的地址，如果不将6置空，后续部分操作可能会出现很大的问题，比如删除5索引的元素，虽然断开了5指向77的地址，但是6仍然指向77的地址，这样就无法由Java虚拟机自行帮我们进行内存释放操作（这里的77并不是指int77，而是指对象）

这里会出现的问题大家可以自己想一想，是比较容易理解的

指定元素删除

• 指定元素删除同样可以通过指定索引删除方法来实现

  • 首先通过indexOf方法查到指定元素的索引
  • 再通过remove(int index) 方法将其删除

// 删除对应的元素
public void remove(E element) {
    remove(indexOf(element));
}

清空

• 清空操作主要就是断开堆空间中地址与对象的连接

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

注意：并不需要将栈空间中的objects与堆空间中的数组连接断开，因为在清空操作之后，我们可能还是需要进行add的，如果直接将数组连接断开，在使用时又需要重新初始化数组，增加了耗时，降低了效率

修改

• 在修改数据时，因为涉及到index，同样需要对index进行合法检查

// 设置index位置的元素
public E set(int index, E element) {
    rangeCheck(index);
    E old = elements[index];
    elements[index] = element;
    return old;
}

在这里，返回了修改前的数据，这里的思想就是：尽可能返回一切有用的数据

查找

简单查找

下面这些方法实现都比较简单，大家直接看代码就行了，很容易理解

// 元素的数量
public int size(){
    return size;
}

// 是否为空
public boolean isEmpty() {
    return size == 0;
}

// 是否包含某个元素
public boolean contains(E element) {
    return indexOf(element) != ELEMENT_NOT_FOUND;
}

// 返回index位置对应的元素
public E get(int index) {
    rangeCheck(index);
    return elements[index];
}

这里的ELEMENT_NOT_FOUND是一个整型常量-1，代表没有查找到对应的元素，这里使用常量可以增加代码的可读性，加强代码语义化

indexOf

这个方法主要就是返回对应元素的索引值

• 将传入的元素和数组中的元素一一比较，找出对应元素的索引，如果找不到，就返回ELEMENT_NOT_FOUND(-1)

// 查看元素的位置
public int indexOf(E element) {
    if(element == null){
        for(int i = 0; i < size; i++){
            if(elements[i] == null) return i;
        }
    }else {
        for(int i = 0; i < size; i++){
            if(elements[i].equals(element)) return i;
        }
    }
    return ELEMENT_NOT_FOUND;
}

• 这里仍然需要分为两种情况，因为我们不排除用户存储null值，所以要对null单独处理

比较对象使用equals方法，可以自定义比较规则，如果使用 ==或者对应对象未重写 equals方法，将比较对象地址值是否相等(同一个对象)

基本数据类型使用 ==进行比较时是比较值是否相等，而引用数据类型使用 ==比较的是地址值

因为null不能调用equals方法，所以对null进行分类处理

toString

• 在打印引用数据类型时，默认会打印地址值
• 为了指定打印格式，我们需要重写toString方法

每次执行System.out.println打印方法时，都会先调用对象的toString方法得到一个字符串，然后将其输出

@Override
public String toString() {
    StringBuilder str = new StringBuilder();
    str.append("top.hellocode.ArrayList{size=").append(this.size).append(", elements=[");
    for(int i = 0; i < size; i++){
        str.append(elements[i]);
        if(i != size - 1){
            str.append(",");
        }
    }
    str.append("]}");
    return str.toString();
}

这里进行字符串拼接使用了StringBuilder对象，因为在使用 +进行拼接时，底层也是通过StringBuilder实现，这里直接使用StringBuilder，可以提高效率

时间复杂度

完整代码

package top.hellocode;

public class ArrayList<E> {
    private int size;
    private E[] elements;
    private static final int CAPACITY_DEFAULT  = 10;
    private static final int ELEMENT_NOT_FOUND = -1;
    /**
     * @Description:有参构造
     * @param capacity:  容量
     * @return: null
     */
    public ArrayList(int capacity){
        capacity = capacity > CAPACITY_DEFAULT ? capacity : CAPACITY_DEFAULT;
        elements = (E[]) new Object[capacity];
    }
    /**
     * @Description:无参默认使用10作为容量调用有参构造
     * 无参方法
     * @return: null
     */
    public ArrayList(){
        this(CAPACITY_DEFAULT);
    }

    // 元素的数量
    public int size(){
        return size;
    }

    // 是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 是否包含某个元素
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    // 添加元素到最后面
    public void add(E element) {
        add(size,element);
    }

    // 往index位置添加元素
    public void add(int index, E element) {
        rangeCheckForAdd(index);      // 索引合法检查
        ensureCapacity(size + 1);       // 检查容量
        for(int i = size; i > index; i--){
            elements[i] = elements[i - 1];
        }
        elements[index] = element;
        size++;
    }
    private void ensureCapacity(int capacity){
        int oldCapacity = elements.length;      // 获取当前数组容量
        if(capacity < oldCapacity) return;
        int newCapacity = oldCapacity + (oldCapacity >> 1);     // 扩容1.5倍
        E[] newElements = (E[]) new Object[newCapacity];
        for(int i = 0; i < size; i++){
            newElements[i] = elements[i];
        }
        elements = newElements;     // 指向新数组
    }
    /**
     * @Description:检查索引是否合法
     * @param index:
     * @return: void
     */
    private void rangeCheck(int index) {
        if(index >= size || index < 0){
            outOfBounds(index);
        }
    }
    private void rangeCheckForAdd(int index) {
        if(index > size || index < 0){
            outOfBounds(index);
        }
    }
    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("size:" + size + ", index:" + index);
    }

    // 返回index位置对应的元素
    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }

    // 设置index位置的元素
    public E set(int index, E element) {
        rangeCheck(index);
        E old = elements[index];
        elements[index] = element;
        return old;
    }

    // 删除index位置对应的元素
    public E remove(int index) {
        rangeCheck(index);
        E old = elements[index];
        for(int i = index; i < size; i++){
            elements[i] = elements[i+1];
        }
        elements[--size] = null;
        return old;
    }
    // 删除对应的元素
    public void remove(E element) {
        remove(indexOf(element));
    }
    // 查看元素的位置
    public int indexOf(E element) {
        if(element == null){
            for(int i = 0; i < size; i++){
                if(elements[i] == null) return i;
            }
        }else {
            for(int i = 0; i < size; i++){
                if(elements[i].equals(element)) return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

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

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("top.hellocode.ArrayList{size=").append(this.size).append(", elements=[");
        for(int i = 0; i < size; i++){
            str.append(elements[i]);
            if(i != size - 1){
                str.append(",");
            }
        }
        str.append("]}");
        return str.toString();
    }
}

进一步优化

• 在ArrayList中，如果要删除索引0位置的元素，则需要将索引0之后的元素全部往前移一位。
• 如果要在索引0位置添加元素，也需要将索引0及之后的元素全部往后移一位。

• 可以在ArrayList类中增加一个记录首元素位置的成员变量
• 删除索引0位置的元素，我们只需要将first属性改为1
• 在索引0位置添加元素，则只需要将first属性改为0

• 类似上图情况，如果继续往0索引插入元素
• 可以将插入的元素存放在索引8这个位置，并将first改为8
• 当要获取索引8下一个元素时，对索引取%，则拿到索引0位置的元素（9 % 9 = 0）

• 如果在一般位置插入元素，则可选择挪动前半段数据或后半段数据
• 在索引2处插入元素99，可以选择将元素22，33左移，然后插入99
• 扩容和缩容同样可以优化