ArrayList依赖于数组，而数组可以随机访问，因此读取的效率要比链表高。相比链表的实现，ArrayList也要简单不少。

List接口

和上一篇提到的双向链表一样，先让ArrayList实现List接口。

template<class T>
class List {
public:
    virtual void add(T value) = 0;
    virtual void add(T value, int position) = 0;
    virtual T get(int position) = 0;
    virtual T remove(int position) = 0;
    virtual inline int getSize() = 0;

protected:
    int size = 0;
    void checkIndexOutOfRange(int index) {
        if (index < 0 || (index >= this->size && this->size > 0)) {
            throw IndexOutOfRangeException(this->size, index);
        }
    }
};

ArrayList类

首先定义几个常量：

#define CAPACITY_STEP 10
#define MAX_CAPACITY 65535
#define COLLAPSE_THRESHOLD 0.5

这两个常量用于数组扩容：

• CAPACITY_STEP 每次扩容容量
• MAX_CAPACITY 最大数组长度

而COLLAPSE_THRESHOLD用于数组缩容，用于数组的利用率比较，如果小于这个阈值，则需要进行缩容操作。

template<class T>
class ArrayList : public List<T> {
private:
    T* data;
    int capacity = 10;

    void expandCapacity();
    void collapseCapacity();

public:
    /* Implements of List.h */
    void add(T value);
    void add(T value, int position);
    T get(int position);
    T remove(int position = 0);
    inline int getSize() {
        return this->size;
    }

    explicit ArrayList(int initialCapacity) {
        this->capacity = initialCapacity;
    }

    explicit ArrayList<T>() {
        this->data = (T*) malloc(sizeof(T) * capacity);
    }

    ~ArrayList() {
        delete this->data;
    }

    void printArrayList() {
        printf("Size/Cap: %d / %d\n", this->size, this->capacity);
        for (int i = 0; i < this->size; i++) {
            printf("%d\n", this->get(i));
        }
    }
};

和链表不同的是，动态数组的元素必须排列在一起，因此在插入或删除元素时，需要把相应的元素全部前移后后移，以保证有空位给新加入的元素且动态数组的中间没有空位。

但由于数组是固定长度的，因此当下标超过数组长度时，需要重新根据扩容机制创建一个新的数组，并将旧数组的元素拷贝到新数组中，这样就实现了数组扩容。

数组扩容

template<class T>
void ArrayList<T>::expandCapacity() {
    // Check whether it need to expand
    if (this->size >= this->capacity) {
        this->capacity += CAPACITY_STEP;
        if (this->capacity > MAX_CAPACITY) {
            this->capacity = MAX_CAPACITY;
        }
        T* t = (T*) malloc(sizeof(T) * this->capacity);
        memcpy(t, this->data, sizeof(T) * this->size);
        delete this->data;
        this->data = t;
    }
}

数组缩容

template<class T>
void ArrayList<T>::collapseCapacity() {
    double usage = (double) this->size / this->capacity;
    if (usage < COLLAPSE_THRESHOLD) {
        int newCapacity = CAPACITY_STEP * ceil((double) this->size / CAPACITY_STEP);
        T* newArray = (T*) malloc(sizeof(T) * newCapacity);
        for (int i = 0; i < this->size; i++) {
            newArray[i] = this->data[i];
        }

        this->capacity = newCapacity;
        delete this->data;
        this->data = newArray;
    }
}

添加元素

template<class T>
void ArrayList<T>::add(T value, int position) {
    expandCapacity();
    if (position >= this->size) {
        add(value);
    } else {
        for (int i = this->size; i > position; i--) {
            this->data[i] = this->data[i - 1];
        }
        this->data[position] = value;
        this->size++;
    }
}

template<class T>
void ArrayList<T>::add(T value) {
    expandCapacity();
    this->data[this->size] = value;
    this->size++;
}

删除元素

template<class T>
T ArrayList<T>::remove(int position) {
    this->checkIndexOutOfRange(position);
    T t = this->get(position);
    for (int i = position; i < this->size - 1; i++) {
        this->data[i] = this->data[i + 1];
    }
    this->size--;
    return t;
}

获取元素

template<class T>
T ArrayList<T>::get(int position) {
    this->checkIndexOutOfRange(position);
    return this->data[position];
}