数据结构之路 - 数组

数组

在Java中，数组是用来存放同一种数据类型的集合
创建方式：

1. 数据类型[] 数组名 = new 数据类型[数组长度];
   int[] arr = new int[20];   //默认值为数据类型的默认值
2. 数据类型[] 数组名 = new 数据类型[]{数据};
   int[] arr = new int[]{1,2,3,4};//数组长度为4
3. 数据类型[] 数组名 = {数据};
   int[] arr = {1,2,3,4,5}; //数组长度为4
   //错误写法  XXXXXX
   int[] arr = new int[5]{1,2,3,4,5};

数组引用变量是存放在栈内存(stack)中，数组元素是存放在堆内存(heap)中，通过栈内存中的指针指向对应元素的在堆内存中的位置来实现访问
同时数组的索引从0开始

数组相关操作代码封装

①、插入一条新的数据项(末尾添加，指定位置添加)
②、寻找某一特定的数据项
③、删除某一特定的数据项
④、修改某一特定的数据项
⑤、打印数组中的数据

/**
 * @author storm   
 * 前提：按顺序紧密排列的数组
 * 功能：增删改查
 * 此处指定位置添加，为从0开始的
 * 泛型
 */
public class ArrayUtil<E> {
    //定义默认数据长度
    private int DATA_LENGTH = 10;

    //int 数据类型的数据
    private E[] data;

    //描述数据中的实际个数
    private int size;

    /**
     * 初始化无参构造函数，此时为默认长度
     */
    public ArrayUtil() {
        data = (E[]) new Object[DATA_LENGTH];
    }

    /**
     * @param length  数组长度
     * 初始化有参构造函数
     */
    public ArrayUtil(int length) {
        if (length <= 0) {
            throw new IllegalArgumentException("设置的数组长度有问题");
        }
        data = (E[]) new Object[length];
    }

    /**
     * @param array  直接传入默认数组
     * 初始化有参构造函数
     */
    public ArrayUtil(E[] array) {
        data = array;
        size = array.length;
    }

    /**
     * @param index  指定的位置
     * @param init   替换的值
     * 
     * 修改某位置的值      复杂度O(1)
     */
    public void setData(int index, E value) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("位置有误");
        }
        data[index] = value;
    }

    /**
     * @param index  查找的位置
     * @return    需要查找的值
     * 
     * 查询某位置的值     复杂度O(1)
     */
    public E getData(int index) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("位置有误");
        }
        return data[index];
    }

    /**
     * @return   数组中实际数据个数
     */
    public int getRealDataSize() {
        return size;
    }

    /**
     * @return   数组长度
     */
    public int getDataLenght() {
        return data.length;
    }

    /**
     * @param value  添加的值
     * 
     * 在末尾添加数据     复杂度O(1)
     */
    public void addData(E value) {
        addIndexData(size, value);
    }

    /**
     * @param index   指定的位置
     * @param value   添加的值
     * 
     * 指定索引位置添加数据   从0开始  复杂度O(n)
     */
    public void addIndexData(int index, E value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("指定位置有问题");
        }

        if (size == data.length) {
            upDateArrayLength(2 * data.length);
        }

        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];  //防止index 为0，越界
        }
        data[index] = value;
        size++;
    }

    /**
     * @param length  新数组的长度
     * 
     * 更新数组容量 长度大小   复杂度O(n)
     */
    public void upDateArrayLength(int length) {
        E[] newData = (E[]) new Object[length];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    /**
     * @param index  删除的索引
     * 
     * 删除某个位置的数据        复杂度O(n)
     */
    public void deleteIndexData(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("指定位置有问题");
        }
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;

        if (size == data.length / 2 && data.length > 1) {
            upDateArrayLength(data.length / 2);
        }
    }

    /**
     * @param value   查询的值
     * @return   是否包含 true 包含;false 不包含
     * 
     * 包含      复杂度O(n)
     */
    public boolean contains(E value) {
        for (int i = 0; i < size; i++) {
            if (data[i] == value) {
                return true;
            }
        }
        return false;
    }

    /**
     * @param value   查找的值
     * @return        对应值的索引
     * 
     * 查找值的位置        复杂度O(n)
     */
    public int find(E value) {
        for (int i = 0; i < size; i++) {
            if (data[i] == value) {
                return i;
            }
        }
        return -1;
    }

    /** (non-Javadoc)
     * @see java.lang.Object#toString()
     * 
     * 打印输出
     */
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if (i != size -1) {
                sb.append(", ");
            } else {
                sb.append("]");
            }
        }
        System.out.println("Array size = " + size 
                            + "   length = " + data.length);
        return sb.toString();
    }
}

数据优缺点

ArrayUtil 封装类中，实现了数组的增删改查。从代码的实现方法来看，数组有以下的特点。
1. 插入
插入快，当只在数组末尾添加数据时，只需要在末尾的对应的索引处出添加数据即可。
插入慢，当需要在指定位置添加数据时，需要将指定位置后面的数据，全部向后挪动一位，数据量很大时，比较耗时。
2. 删除
删除慢，需要将删除位置后的数据往前挪一位。
3. 查询
查询快，当只根据下标进行查找时，直接可以给出下标对应的数据即可。
查询慢，当根据值来查找数据时，需要遍历数组中的数据和查找的数据比较。如果有序时，可通过一些算法减少比较次数，比如二分查找法；如果无序，则要从数组的第一个开始查询比较，此时比较耗时。
4. 改
速度快，当知道下标，则将下标对应的值进行修改
速度慢，当不知道下标，则要遍历数组进行查询修改
5. 定长 不动态
数组一旦创建后，大小就固定了，不能动态扩展数组的元素个数。如果初始化你给一个很大的数组大小，那会白白浪费内存空间，如果给小了，后面数据个数增加了又添加不进去了。此时可以通过重新创建新的数据，将老的数组值赋值到新数组中去，但数据量很大时，耗时长。
此时就要注意定义数组长度的合理化

~看到新问题会继续补充