第1章. 动态数组(ArrayList)

动态数组

一、动态数组接口设计

// 这里可以写一个List接口,然后ArrayList类去实现这个接口,实现接口中的方法。但为了方便起见,直接将这些方法写在类中。
// 这些方法暂时不添加泛型、和正确的返回值
public class ArrayList {
    // 动态数组的长度
    private int size;

    // 动态数组的所有元素
    private int[] elements;

    // 返回动态数组的长度
    public int size() {
        return 0;
    }

    // 判断动态数组是否为空
    public boolean isEmpty() {
        return false;
    }
    
    // 判断是否包含某个元素
    public boolean contains(int element) {
        return false;
    }
    
    // 添加元素到动态数组末尾
    public void add(int element) {
        
    }
    
    // 添加元素到动态数组index索引位置
    public void add(int index, int element) {

    }
    
    // 返回index索引位置对应的元素
    public int get(int index) {
        return 0;
    }
    
    // 删除index索引位置对应的元素,并返回所删除的元素
    public int remove(int index) {
        return 0;
    }
    
    // 设置index位置的元素,并返回旧值
    public int set(int index, int element) {
        return 0;
    }
    
    // 查看指定元素第一次出现的位置
    public int indexOf(int element) {
        return 0;
    }
    
    // 清除所有元素
    public void claer() {
        
    }
    
    // 打印数组,重写toString()方法
    @Override
    public String toString() {
       
    }
}

二、动态数组的设计

public class ArrayList {
    // 动态数组的长度
    private int size;

    // 动态数组的所有元素
    private int[] elements;
     
}

三、动态数组的构造器

// 提供一个带参构造器,创建用户输入的数组容量,若用户输入容量小于默认初始容量10,则创建10个长度的数组
// 动态数组的默认初始容量

private static final int DEFAULT_CAPACITY = 10;

public ArrayList(int capacity) {
    capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
    elements = new int[capacity];
}


// 提供一个空参构造器,默认数组的初始容量为10
public ArrayList() {
    //elements = new int[DEFAULT_CAPACITY];
    this(DEFAULT_CAPACITY);
}

四、核心操作

4.1 获取第一个元素位置：indexOf

// 查看指定元素第一次出现的位置,如果找不到则返回-1
public int indexOf(int element) {
    // 遍历动态数组。注意size和elements.length的区别
    for (int i = 0; i < size; i ++) {
        if (elements[i] == element) {
            return i;
        }
    }
    return ELEMENT_NOT_FOUND;
}

• 注意区别size和elements.length的区别
  • size表示的是当前数组元素的个数
  • elements.length表示的是数组的长度，也即动态数组的容量capacity
  • size <= elements.length。所以在遍历动态数组的时候，一定是i < size而不是i < elements.length。

4.2 清除元素：clear

// 清除所有元素
public void clear() {
    size = 0;
}

• 为什么不写成elements=null？
  • 原因是当用户执行clear()操作后，后面可能还需要使用add操作，所以数组分配的这些内存空间后面可能还需要使用。
  • size = 0 的操作已经对用户来说已经无法访问动态数组中的元素了。但这数组的内存空间还在。

4.3 打印数组：toString

// 打印数组
@Override
public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("size = ").append(size).append(", ").append("[");
    for (int i = 0; i < size; i ++) {
        if (i == size - 1) {
            sb.append(elements[i]);
            break;
        }
        sb.append(elements[i]).append(",");
    }
    sb.append("]");

    return sb.toString();
}

• 打印引用对象，默认是调用其toString()方法
• 所以需要重写toStirng方法，在toString()方法中将元素拼接成字符串
• 字符串拼接建议使用StringBuilder

4.4 删除元素：remove

// 删除index索引位置对应的元素,并返回所删除的元素
public int remove(int index) {
    // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
    }
    // 保存要被删除的值
    int remove = elements[index];

    // 从被删除的后一个元素开始往前移动
    for (int i = index + 1; i < size; i ++) {
        elements[i - 1] = elements[i];
    }
    size --;

    return remove;
}

4.5 动态数组扩容

• 需要扩容的地方：add方法

// 确保有needCapacity的容量
private void ensureCapacity(int needCapacity) {
    // 当前容量为nowCapacity
    int nowCapacity = elements.length;
    // 当前容量大于等于所需要的容量，容量够
    if (nowCapacity >= needCapacity) return;
    // 容量不够,则扩容至1.5倍
    int newCapacity = nowCapacity + (nowCapacity >> 1);
    int[] newElements = new int[newCapacity];

    // 拷贝元素
    for(int i = 0; i < elements.length; i ++) {
        newElements[i] = elements[i];
    }
    elements = newElements;

    System.out.println(nowCapacity + "扩容为：" + newCapacity);
}

4.6 添加元素：add

// 添加元素到动态数组末尾
public void add(int element) {
    add(size, element);
}

// 添加元素到动态数组index索引位置
public void add(int index, int element) {
    //        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
    //        if (index < 0 || index > size) {
    //            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
    //        }
    
    // 扩容
    rangeCheckForAdd(index);

    // 当前动态数组的元素个数为size,我们确保需要size+1个容量
    ensureCapacity(size + 1);

    for (int i = size - 1; i >= index; i --) {
        elements[i + 1] = elements[i];
    }
    elements[index] = element;
    size ++;
}

五、给动态数组添加泛型

使用泛型技术可以让动态数组更加通用，可以存放任何数据类型的数据。

public class ArrayList<E> {
    // 动态数组的长度
    private int size;
    // 动态数组的所有元素
    private E[] elements;
    
    // 特别重要！
    elements = (E[]) new Object[capacity];
}

ArrayList<Integer> list = new ArrayList<>();

• elements = (E[]) new Object[capacity];
• E[] newElements = (E[])new Object[newCapacity];

不能elements = new E[capacity]；的原因是泛型是编译时期的，而new是运行时期的

六、内存管理细节

给动态数组添加泛型之后，考虑到内存管理细节，需要修改某些方法的内部实现。

6.1 对象数组

6.2 清空操作clear()细节

// 清除所有元素
public void clear() {
    // (内存管理细节)对象内存清空，但是对象数组所分配的内存还在
    for (int i = 0; i < size; i ++) {
        elements[i] = null;
    }
    size = 0;
}

6.3 删除操作remove()细节

// 删除index索引位置对应的元素,并返回所删除的元素
public E remove(int index) {
    // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
    rangeCheck(index);

    // 保存要被删除的值
    E remove = elements[index];

    // 从被删除的后一个元素开始往前移动
    for (int i = index + 1; i < size; i ++) {
        elements[i - 1] = elements[i];
    }

    // (内存管理细节)将最后一个元素变为null
    elements[size - 1] = null;

    size --;

    return remove;
}

6.4 indexOf()方法小细节

// 查看指定元素第一次出现的位置,如果找不到则返回-1
public int indexOf(E element) {
    // 遍历动态数组。注意size和elements.length的区别
    for (int i = 0; i < size; i ++) {
        // 小细节 不再是 ==
        if (elements[i].equals(element)) {
            return i;
        }
    }
    return ELEMENT_NOT_FOUND;
}

6.5 null值处理细节

// 查看指定元素第一次出现的位置,如果找不到则返回-1
public int indexOf(E element) {
    // 遍历动态数组。注意size和elements.length的区别

    // 找null。则element为空,不可以element.equals(elements[i]),直接用elements[i] == null判断
    if (element == null) {
        for (int i = 0; i < size; i ++) {
            if (elements[i] == null) {  // elements[i]为空
                return i;
            }
        }
    } else {
        // 找不为null。则element不为空,可以element.equals(elements[i])
        for (int i = 0; i < size; i ++) {
            // 避免空指针异常
            if (element.equals(elements[i])) {
                return i;
            }
        }
    }
    return ELEMENT_NOT_FOUND;
}

七、最终迭代后的代码

package DataStructure._01动态数组;

/**
 * @author keyongkang
 * @date 2022-07-10-10:09
 */

public class ArrayList<E> {
    // 动态数组的长度
    private int size;

    // 动态数组的所有元素
    private E[] elements;

    // 动态数组的默认初始容量
    private static final int DEFAULT_CAPACITY = 10;
    private static final int ELEMENT_NOT_FOUND = -1;

    public ArrayList(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = (E[])new Object[capacity];
    }

    public ArrayList() {
        //elements = new int[DEFAULT_CAPACITY];
        this(DEFAULT_CAPACITY);
    }

    private void rangeCheck(int index) {
        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
        }
    }

    private void rangeCheckForAdd(int index) {
        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
        }
    }

    // 返回动态数组的长度
    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) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index > size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }
        rangeCheckForAdd(index);

        // 当前动态数组的元素个数为size,我们确保需要size+1个容量
        ensureCapacity(size + 1);

        for (int i = size - 1; i >= index; i --) {
            elements[i + 1] = elements[i];
        }
        elements[index] = element;
        size ++;
    }

    // 确保有needCapacity的容量
    private void ensureCapacity(int needCapacity) {
        // 当前容量为nowCapacity
        int nowCapacity = elements.length;
        // 当前容量大于等于所需要的容量，容量够
        if (nowCapacity >= needCapacity) return;
        // 容量不够,则扩容至1.5倍
        int newCapacity = nowCapacity + (nowCapacity >> 1);
        E[] newElements = (E[])new Object[newCapacity];

        // 拷贝元素
        for(int i = 0; i < elements.length; i ++) {
            newElements[i] = elements[i];
        }
        elements = newElements;

        System.out.println(nowCapacity + "扩容为：" + newCapacity);
    }

    // 返回index索引位置对应的元素
    public E get(int index) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index >= size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }
        rangeCheck(index);
        return elements[index];
    }

    // 删除index索引位置对应的元素,并返回所删除的元素
    public E remove(int index) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index >= size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }
        rangeCheck(index);

        // 保存要被删除的值
        E remove = elements[index];

        // 从被删除的后一个元素开始往前移动
        for (int i = index + 1; i < size; i ++) {
            elements[i - 1] = elements[i];
        }

        // (内存管理细节)将最后一个元素变为null
        elements[size - 1] = null;

        size --;

        return remove;
    }

    // 设置index位置的元素,并返回旧值
    public E set(int index, E element) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index >= size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }

        rangeCheck(index);

        // 保存当前索引的旧值
        E old = elements[index];
        // 设置index位置的新值
        elements[index] = element;

        return old;
    }

    // 查看指定元素第一次出现的位置,如果找不到则返回-1
    public int indexOf(E element) {
        // 遍历动态数组。注意size和elements.length的区别

        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 (element.equals(elements[i])) {
                    return i;
                }
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    // 清除所有元素
    public void clear() {
        //size = 0;
        // (内存管理细节)对象内存清空，但是对象数组所分配的内存还在
        for (int i = 0; i < size; i ++) {
            elements[i] = null;
        }
        size = 0;
    }

    // 打印数组
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size = ").append(size).append(", ").append("[");
        for (int i = 0; i < size; i ++) {
            if (i == size - 1) {
                sb.append(elements[i]);
                break;
            }
            sb.append(elements[i]).append(", ");
        }
        sb.append("]");

        return sb.toString();
    }
}

本栏目推荐文章
• 类模板实现简单的数组
• 数组内存图
• 数组
• 动态代理
• 整数的划分（递归或动态规划）
• 动态代理
• 【C语言】动态内存申请，堆空间与栈空间差异
• 1.12_redis 的存取在最后 晚上_浙江本地环境的header不能用线上的_header中host和refer分别代表什么意思?_模型的save()参数是数组怎么理解?
• 实时数据流无忧：用 SpringBoot 和 SSE 打造动态前端更新的终极指南
• 使用iviewUI动态添加、删除输入框及做对应的判断

数组 ArrayList 动态数组arraylist动态 数组arraylist 数组arraylist java 数组 中将arraylist java 数组 字符串arraylist字符 数组arraylist hashmap toarray 数组 动态 数组 基础 动态 数组vba-redim动态redim 数组 动态copy bug