<<漫画算法>>--数据结构之数组

大部分记录均来自小灰漫画算法

• 什么是数组
  有限个相同变量组成的有序结合

• 插入元素
  

  数组-插入元素.png
  
  数组扩容
  数组创建好之后长度是固定的。数组长度不够的时候需要人为扩容。再把旧的数组元素复制到新数组中。

插入元素插入后需要对数组下标进行调整；

• 删除元素
  基本个插入元素都差不多，不过元素的当元素无序的时候，时间复杂度跟空间复杂度都为常数

    private int[] array;

    public MyArray(int capacity) {
        array = new int[capacity];
    }

    /**
     * 插入元素
     *
     * @param position:插入位置
     * @param element：插入元素
     */
    public void insert(int position, int element) {
        //判断异常情况
        if (array.length == 0) {
            return;
        }
        if (position < 0 || position > array.length) {
            throw new IndexOutOfBoundsException("超出數組范围");
        }

        //数组扩容
        while (position >= array.length - 1) {
            array = reSize(array);
        }
        //数组元素向后移动
        for (int i = array.length - 1; i > position; i--) {
            array[i] = array[i - 1];
        }
        //插入元素
        array[position] = element;
    }

    /**
     * 删除元素
     * @param position
     */
    public void delete(int position){
        //判断异常情况
        if (array.length == 0) {
            return;
        }
        if (position < 0 || position > array.length) {
            throw new IndexOutOfBoundsException("超出數組范围");
        }
        if(position == array.length - 1) {
            array[position] = 0;
        }else{
            for (int i = position ; i < array.length - 1; i++){
                array[i] = array[i + 1];
            }
        }
    }

    /**
     * 數組扩容
     *
     * @param originalArray
     * @return
     */
    public int[] reSize(int[] originalArray) {
        if (originalArray.length > 0) {
            int[] newArray = new int[originalArray.length * 2];
            //System.arraycopy：相当于在内存中新开辟了一块空间
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }
        return null;
    }

    public void output() {
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

    public static void main(String[] args) {
        MyArray myArray = new MyArray(10);
        myArray.insert(9, 10);
        myArray.insert(9,1);
        myArray.output();
        System.out.println("===========================");
        myArray.delete(9);
        myArray.delete(9);
        myArray.output();
    }

根据上面代码可以知道，数组在添加跟更新数据上面效率远远大于删除和插入元素。