数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

  1. public class Array<E> {
  3.     private E[] data;
  4.     private int size;
  6.     // 构造函数，传入数组的容量capacity构造Array
  7.     public Array(int capacity){
  8.         data = (E[])new Object[capacity];
  9.         size = 0;
  10.     }
  12.     // 无参数的构造函数，默认数组的容量capacity=10
  13.     public Array(){
  14.         this(10);
  15.     }
  17.     // 获取数组的容量
  18.     public int getCapacity(){
  19.         return data.length;
  20.     }
  22.     // 获取数组中的元素个数
  23.     public int getSize(){
  24.         return size;
  25.     }
  27.     // 返回数组是否为空
  28.     public boolean isEmpty(){
  29.         return size == 0;
  30.     }
  32.     // 在index索引的位置插入一个新元素e
  33.     public void add(int index, E e){
  35.         if(size == data.length)
  36.             throw new IllegalArgumentException("Add failed. Array is full.");
  38.         if(index < 0 || index > size)
  39.             throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
  41.         for(int i = size - 1; i >= index ; i --)
  42.             data[i + 1] = data[i];
  44.         data[index] = e;
  46.         size ++;
  47.     }
  49.     // 向所有元素后添加一个新元素
  50.     public void addLast(E e){
  51.         add(size, e);
  52.     }
  54.     // 在所有元素前添加一个新元素
  55.     public void addFirst(E e){
  56.         add(0, e);
  57.     }
  59.     // 获取index索引位置的元素
  60.     public E get(int index){
  61.         if(index < 0 || index >= size)
  62.             throw new IllegalArgumentException("Get failed. Index is illegal.");
  63.         return data[index];
  64.     }
  66.     // 修改index索引位置的元素为e
  67.     public void set(int index, E e){
  68.         if(index < 0 || index >= size)
  69.             throw new IllegalArgumentException("Set failed. Index is illegal.");
  70.         data[index] = e;
  71.     }
  73.     // 查找数组中是否有元素e
  74.     public boolean contains(E e){
  75.         for(int i = 0 ; i < size ; i ++){
  76.             if(data[i].equals(e))
  77.                 return true;
  78.         }
  79.         return false;
  80.     }
  82.     // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
  83.     public int find(E e){
  84.         for(int i = 0 ; i < size ; i ++){
  85.             if(data[i].equals(e))
  86.                 return i;
  87.         }
  88.         return -1;
  89.     }
  91.     // 从数组中删除index位置的元素, 返回删除的元素
  92.     public E remove(int index){
  93.         if(index < 0 || index >= size)
  94.             throw new IllegalArgumentException("Remove failed. Index is illegal.");
  96.         E ret = data[index];
  97.         for(int i = index + 1 ; i < size ; i ++)
  98.             data[i - 1] = data[i];
  99.         size --;
  100.         data[size] = null; // loitering objects != memory leak
  101.         return ret;
  102.     }
  104.     // 从数组中删除第一个元素, 返回删除的元素
  105.     public E removeFirst(){
  106.         return remove(0);
  107.     }
  109.     // 从数组中删除最后一个元素, 返回删除的元素
  110.     public E removeLast(){
  111.         return remove(size - 1);
  112.     }
  114.     // 从数组中删除元素e
  115.     public void removeElement(E e){
  116.         int index = find(e);
  117.         if(index != -1)
  118.             remove(index);
  119.     }
  121.     @Override
  122.     public String toString(){
  124.         StringBuilder res = new StringBuilder();
  125.         res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
  126.         res.append('[');
  127.         for(int i = 0 ; i < size ; i ++){
  128.             res.append(data[i]);
  129.             if(i != size - 1)
  130.                 res.append(", ");
  131.         }
  132.         res.append(']');
  133.         return res.toString();
  134.     }
  135. }

查找

时间复杂度 数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)
查找元素快：通过索引，可以快速访问指定位置的元素。

插入

时间复杂度为 O(n),假设数组的长度为 n，现在，如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。

删除

时间复杂度为 O(n),

动态扩容

ArrayList是Java集合框架类的一员，可以称它为一个动态数组。它还有一个优势就是将数组的操作封装起来，比如增删查，以及动态扩容。
扩容

    // 在index索引的位置插入一个新元素e
    public void add(int index, E e){

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

        if(size == data.length)
            resize(2 * data.length);

        for(int i = size - 1; i >= index ; i --)
            data[i + 1] = data[i];

        data[index] = e;

        size ++;
    }

缩容

 // 从数组中删除index位置的元素, 返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        E ret = data[index];
        for(int i = index + 1 ; i < size ; i ++)
            data[i - 1] = data[i];
        size --;
        data[size] = null; // loitering objects != memory leak

        if(size == data.length / 2)
            resize(data.length / 2);
        return ret;
    }

具体操作函数

 // 将数组空间的容量变成newCapacity大小
    private void resize(int newCapacity){

        E[] newData = (E[])new Object[newCapacity];
        for(int i = 0 ; i < size ; i ++)
            newData[i] = data[i];
        data = newData;
    }

越界

一般数组的下标是从0开始，因此数组的第一个数下标是0 最后一个数的下标是size-1。
数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。
而大多数语言例如JAVA中如果越界则会抛出java.lang.ArrayIndexOutOfBoundsException