数组是数据结构里线性表示的一种，它的特点：

• 数组在内存中是一块连续的空间，在创建数组时需要预先准备它的最大容量；
• 当数组长度达到最大容量时，再次插入元素前需要先为其扩容；
• 根据下标（索引）访问元素效率极高，时间复杂度为O(1)；
• 在中间插入、删除元素有代价，需要移动元素，平均时间复杂度为O(n)。

操作

创建

对于数组来说，操作系统会给它在内存里分配一块连续的空间，数组下标为0处是它在该内存空间的起始地址。每个内存空间都有其唯一的起始地址。

由于程序在运行时，会不断地申请内存创建变量，而数组的特性是要有连续空间。因此，创建数组时，必须指定它的最大容量，也就是数组的长度必须是固定的。

以Java、C/C++等静态语言为例，创建数组的方式很简单，数组中每个元素类型必须是相同的。下面这个例子就是创建长度为5的数组，其中每个元素类型为int。

int[] nums = new int[5];

C/C++还可以通过为指针分配一块内存空间的形式，创建类似数组的结构，比如下面这个例子创建出来的nums变量在C/C++中可以也通过数组的形式去访问它。

int* nums = (int*) calloc(5, sizeof(int));

在部分动态类型的语言中，数组中的元素类型可以是不一样的。

访问

以上面创建的数组为例，访问的方式就是通过它的下标，比如：

nums[0] = 1;
int a = nums[1];

在C/C++中，不管是数组还是指针变量，都还可以通过*操作符加在指针的形式去访问该位置的元素：

*nums = 1;
*(nums + 1) = 5;
int b = *(nums + 2);

应用 - ArrayList

声明：

template <class T> struct Node {
    T data;
    Node(T& data) {
        this->data = data;
    }
};

template <class T> class ArrayList {
private:
    static const unsigned int initial_length = 16;
    Node<T>** nodes;
    unsigned int current_size;
    unsigned int array_length;
    void inflate();

public:
    ArrayList();
    ArrayList(int length);
    ArrayList(ArrayList<T>& list);
    ~ArrayList();
    void add(T& data);
    void add(T& data, unsigned int index);
    /**
     * Remove node at pos
     * @param index starts from 0
     */
    void removeAt(int index);
    void printList();
    unsigned int size();
    Node<T>* operator[](int index);
    Node<T>* get(int index);
};

定义：

template <class T> ArrayList<T>::ArrayList() : ArrayList(initial_length) {}

template <class T> ArrayList<T>::ArrayList(int length) {
    array_length = (unsigned int) length;
    nodes = new Node<T>*[array_length];
    current_size = 0;
}

template <class T> ArrayList<T>::ArrayList(ArrayList<T>& list) {
    array_length = list.array_length;
    nodes = new Node<T>*[array_length];
    current_size = 0;
    for (int i = 0; i < list.current_size; i++) {
        T& data = list.get(i)->data;
        Node<T>* node = new Node<T>(data);
        nodes[i] = node;
    }
    current_size = list.current_size;
}

template <class T> ArrayList<T>::~ArrayList() {
    delete []nodes;
}

template <class T> void ArrayList<T>::add(T& data) {
    if (current_size == array_length) {
        inflate();
    }
    Node<T> * node = new Node<T>(data);
    nodes[current_size] = node;
    ++current_size;
}

template <class T> void ArrayList<T>::add(T& data, unsigned int index) {
    if (index == current_size) {
        this->add(data);
    } else {
        if (current_size == array_length) {
            inflate();
        }
        for (unsigned int i = current_size; i > index; i--) {
            nodes[i] = nodes[i-1];
        }
        Node<T> * node = new Node<T>(data);
        nodes[index] = node;
        ++current_size;
    }
}

template <class T> void ArrayList<T>::inflate() {
    int new_size = current_size * 2;
    Node<T>** newNodes = new Node<T>*[new_size];
    for (int i = 0; i < current_size; ++i) {
        newNodes[i] = nodes[i];
    }
    delete []nodes;
    nodes = newNodes;
    cout << "The array list length inflates to: " << new_size << endl;
}

template <class T> void ArrayList<T>::removeAt(int index) {
    Node<T> * node = nodes[index];
    for (unsigned int i = index; i < current_size; i++) {
        nodes[i] = nodes[i+1];
    }
    delete node;
    --current_size;
}

template <class T> void ArrayList<T>::printList() {
    for (unsigned int i = 0; i < current_size; ++i) {
        Node<T> * node = nodes[i];
        cout << (*node).data << " ";
    }
    cout << endl;
}

template <class T> unsigned int ArrayList<T>::size() {
    return current_size;
}

template <class T> Node<T>* ArrayList<T>::operator[](int index) {
    return nodes[index];
}

template <class T> Node<T>* ArrayList<T>::get(int index) {
    return nodes[index];
}