数据结构与算法（第一季）：动态数组

一、数组（Array）

• 数组是一种顺序存储的线性表, 所有元素的内存地址都是连续的。

  int[] array = new int[]{11, 22, 33}
  复制代码
  

image

• 在很多编程语言中，数组有个致命的缺点， 无法动态修改容量。

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

二、动态数组（Dynamic Array）接口设计

• 创建ArrayList类，创建size属性来管理数组中元素的个数， 创建elements属性来管理存取的数据。
• 可以对动态数组进行增删改查操作。

image

public class ArrayList<E> {
    private int size;
    private E[] elements;

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

三、动态数组的实现

1、构造方法

• 如果构建的数组空间小于默认空间，则会以默认空间构建数组。

public class ArrayList<E> {
    private int size;
    private E[] elements;
    // 设置elements数组默认的初始化空间
    private static final int CAPACITY_DEFAULT = 10;

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

    // 便利构造器
    public ArrayList() {
        this(CAPACITY_DEFAULT);
    }
}
复制代码

2、添加元素

• 数组添加元素分为在最后一个元素的后面添加新元素和将元素插入到某个位置（非最后面）两种情况。
• 第一种情况，这个新元素需要添加到的索引等于当前数组元素的个数，在ArrayList中size属性就是当前数组元素的个数，所以就是将新元素添加到数组的size位置上，然后size加1。

image

public void add(int index, E element) {
    elements[index] = element;
    size++;
}
复制代码

• 如果是第二种情况，只需要将插入位置后面的元素向后移动即可。
• 注意：需要从后向前移动元素，如果从前向后移动元素，那么会进行元素覆盖, 最后出错。

image

2.1、数组越界

• 添加元素，还要注意传入的索引不能越界，即不能小于0, 也不能大于size。

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

2.2、数组扩容

• 由于数组elements最大的容量只有10，所以当数组存满元素时，就需要对数组进行扩容。
• 因为数组是无法动态扩容的，所以需要创建一个新的数组，这个数组的容量要比之前数组的容量大。
• 然后在将原数组中的元素存放到新数组中，这样就实现了数组的扩容。

image

private void ensureCapacity() {
    // 获取数组当前容量
    int oldCapacity = elements.length;
    // 如果 当前存储的元素个数 < 当前数组容量, 直接返回
    if (size < oldCapacity) return;
    // 新数组的容量为原数组容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 创建新数组
    E[] newElements = (E[]) new Object[newCapacity];
    // 原数组中的元素存储到新数组中
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[I];
    }
    // 引用新数组
    elements = newElements;
}
复制代码

• 实现add函数，需要在添加新元素之前，判断数组越界和扩容。

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++;
}
复制代码

• 最终在最后一个元素的后面添加新元素，即添加元素到尾部的实现方式如下

public void add(E element) {
    add(size, element);
}
复制代码

3、删除元素

• 删除元素，实际上就是去掉指定位置的元素，并将后面的元素向前移动。
• 如下图，当删除索引为3的元素时，只需要将后面的元素向前移动，然后在去掉最后一个元素，size减1即可。

image

3.1、数组越界

• 删除元素时传入的索引不能越界, 即不能小于0, 也不能大于等于size

所以我们在删除元素之前需要先进行索引检查。

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

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

3.2、数组缩容

• 当数组中的元素删除后，数组剩余的空间可能会很大，这样就会造成内存的浪费。
• 所以当数组中元素删除后，我们需要对数组进行缩容。
• 实现方法类似于扩容，当数组中容量小于某个值时，创建新的数组，然后将原有数组中的元素存入新数组即可。

public void trim() {
    // 获取当前数组的容量
    int capacity = elements.length;
    // 当size大于等于容量的一半, 或则容量已经小于默认容量(10)时, 直接返回
    if (size >= capacity >> 1 || capacity < CAPACITY_DEFAULT) return;
    // 计算新的容量 = 原有容量的一半
    int newCapacity = capacity >> 1;
    // 创建新数组
    E[] newElements = (E[]) new Object[newCapacity];
    // 将原数组元素存入新数组
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[I];
    }
    // 引用新数组
    elements = newElements;
}
复制代码

• 最终, remove方法实现如下

public E remove(int index) {
    // 判断索引是否越界
    rangeCheck(index);
    // 取出需要删除的元素
    E old = elements[index];
    // 通过循环, 将index后面的所有元素向前移动一位
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[I];
    }
    // 删除最后一个元素
    elements[--size] = null;
    // 判断数组是否需要缩容
    trim();
    // 将删除的元素返回
    return old;
}
复制代码

4、清空数组

• 清空数组时，需要将所有的元素置为null，只有这样才能真正的释放对象，然后size置为0。

image

public void clear() {
    // 清空存储的数据
    for (int i = 0; i < size; i++) {
        elements[i] = null;
    }
    // 将size置为0
    size = 0;
}
复制代码

5、修改元素

• 修改元素时，只需要将原有位置的元素替换掉即可，同样需要注意一下索引是否越界。

public E set(int index, E element) {
    // 判断索引是否越界
    rangeCheck(index);
    // 取出被替换元素
    E oldElement = elements[index];
    // 替换元素
    elements[index] = element;
    // 返回被替换元素
    return oldElement;
}
复制代码

6、查询元素

• 查询元素，只需要将指定索引的元素返回，注意索引是否越界即可。

public E get(int index) {
    rangeCheck(index);
    return elements[index];
}
复制代码

7、查看元素位置

• 可以通过循环, 查找元素在数组中的位置。
• 注意：假如数组中可以存储null，而null是不能调用equals方法的，所以需要对传入的元素进行判断，如果查找的元素是null，需要单独处理。
• 当元素存在时返回索引，否则返回变量ELEMENT_ON_FOUND的值。

private static final int 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 (element.equals(elements[i])) return I;
        }
    }
    return ELEMENT_NOT_FOUND;
}
复制代码

8、是否包含某元素

• 只需通过判断索引是否等于ELEMENT_ON_FOUND即可。

public boolean contains(E element) {
    // 查看元素的索引是否为ELEMENT_ON_FOUND即可
    return indexOf(element) != ELEMENT_ON_FOUND;
}
复制代码

9、元素的数量

• size的值，即为元素的数量。

public int size() {
    return size;
}
复制代码

10、数组是否为空

• 通过判断size的值是否为0即可。

public boolean isEmpty() {
    return size == 0;
}
复制代码

11、动态数组打印

• 可以重写toString方法, 来打印ArrayList中的元素。

@Override
public String toString() {
    StringBuilder string = new StringBuilder();
    string.append("size = ").append(size).append(", [");
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            string.append(",");
        }
        string.append(elements[I]);
    }
    string.append("]");
    return string.toString();
}
复制代码

到此为止，我们成功的实现了动态数组。

四、动态数组的复杂度

image

五、ArrayList能否进一步优化？

image

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

image

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

image

• 如果继续往前插入元素，则将插入的元素存放在索引8这个位置，并将first改为8。
• 当要获取索引8下一个元素时，对索引取摩，则拿到索引0位置的元素。

image

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