[数据结构]什么是数组?

待我称王封你为后i 2021-12-09 20:49 306阅读 0赞

数组:有限个相同类型的变量所组成的一个集合,数组中的每个变量可以成为一个元素,数组在内存中是顺序存储的,需要开辟连续的内存空间.  
数组的特点:查找快,修改慢, 查找的时间复杂度O(1),而修改是O(n) ,其中当不关心数组的顺序时,删除操作可以用末尾的元素覆盖所要删除位置的元素,然后再删除末尾元素此时复杂度为O(1)

手敲一个简单的数组

/**
     * @author : 董硕
     * @time: 2019-07-14 18:17
     * @desc:手写一个数组 实现add update delete find ,增加了扩容功能
     */
    public class MyArray {
        private int [] array;
        private int size;
    
        public MyArray(int size) {
            this.array = new int [size];
            this.size = 0;
        }
    
        public int get(int index) {
            return array[index];
        }
    
        public void update(int element , int index) {
            array[index] = element;
        }
        public void insert(int element , int index) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException("out of array size");
            }
            if (size >= array.length) {
                resize();
            }
            for (int i = size - 1; i >= index; i--) {
                array[i+1] = array[i];
            }
            array[index] = element;
            size++;
        }
        public int delete(int index) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException("out of array size");
            }
            int deleteElement = array[index];
            for (int i = index; i < size -1; i++) {
                array[i] = array[i+1];
            }
            size--;
            return deleteElement;
        }
        private void resize() {
            int [] newArray = new int[2 * size];
            System.arraycopy(this.array,0,newArray,0,size);
            this.array = newArray;
        }
        private void outPut() {
            System.out.println(JSON.toJSONString(array));
        }
    
        public static void main(String[] args) {
            MyArray myArray = new MyArray(10);
            myArray.insert(0,0);
            myArray.insert(1,1);
            myArray.insert(2,2);
            myArray.insert(3,3);
            myArray.insert(4,4);
            myArray.delete(0);
            myArray.insert(12,0);
            myArray.outPut();
        }
    }