数组指定位置插入和删除元素的实现

电玩女神 2022-10-02 00:56 294阅读 0赞

一般来说，我们用数组这种数据结构最多的情况，是用来做**查询**，时间复杂度为O(1)，那么在这里我们来看一下如何用在数组中插入元素和删除元素。  
**数组的适用场景**：  
一般在**查询**中，适用数组的情况是比较多，因为可以根据下标直接访问元素，时间复杂度是**O(1)**，所以**适用于读多写少的场景**。  
数组的**插入和删除**元素，一般时间复杂度都是**O(N)**，比较麻烦，所以对于插入和删除操作中，不建议选用数组这种数据结构，可以考虑链表。

大家都知道数组是一种**数据结构**，属于**线性表**，数据元素在内存中是一块**连续的存储区域**，属于顺序存储。

那么我们在数组中插入元素的话，一般会有三种插法：  
（1）在数组的第一个位置插入元素  
（2）在数组的最后一个位置插入元素  
（3）在数组的中间位置插入元素

首先我们考虑第一种情况：**在数组的第一个位置插入元素**:  
（1）如果数组是一个**空数组**的话，那么我们就直接把这个元素赋值给下标为0的数组元素；  
（2）如果数组不是空数组，那么我们在第一个位置插入元素之前，需要将原有的数组元素统一向后移动一个位置，但是需要保证插入一个元素后，**数组的长度应该小于初始化的时候数组长度**，  
（3）如果**插入后大于了原有数组的长度**，那么在插入之前，我们需要新建一个数组，进行**数组长度的扩容**，以便元素数组内容和新插入的元素都可以插入到数组中。  
考虑第二种情况，**直接在尾部插入**：  
（1）如果原有数组还有剩余空间，那么就直接插入到原有数组的空闲位置  
（2）如果原有数组所有下标都有元素，那么就需要对原有数组进行扩容  
考虑第三种情况，在数组的中间位置插入元素：  
类似于**在数组的第一个位置插入元素的想法**

下面是具体的实现：

public class ArrayTest {
        public static void main(String[] args) throws  Exception{
            MyArray myArray = new MyArray(4);
            myArray.insert(3,0);
            myArray.insert(7,1);
            myArray.insert(9,2);
            myArray.insert(5,3);
            myArray.insert(6,1);
            myArray.output();
        }
    }
    
    class MyArray{
        private int[] array;
    
        private int size;
    
        public MyArray(int capacity) {
            this.array = new int[capacity];
            this.size = 0;
        }
    
        /**
         *
         * @param element 插入的元素
         * @param index 插入的元素的位置
         * @throws Exception
         */
        public void insert(int element,int index) throws Exception{
            if (index < 0 || index > size){
                throw  new Exception("插入的元素位置超越了数组实际的元素范围");
            }
            if(size >= array.length){
                grow();
            }
            //这个循环就是在插入元素的时候，将指定位置上的元素都向后移动一位，
            //给要插入的元素腾出位置
            //移动顺序就是从最后一个元素开始向后移动，一直到原有位置的元素后移一位
            for (int i = size-1; i >= index ; i--) {
                array[i+1] = array[i];
            }
            array[index] = element;
            size++;
        }
       /**
       * 数组进行扩容，这里必须选择正整数
       */
        private void grow() {
            int[] newArray = new int[array.length*2];
             //将原有数组的内容复制到新数组中
            System.arraycopy(array,0,newArray,0,array.length);
            //原有数组指向新数组的内容
            array = newArray;
        }
    
        public void output(){
            for (int i = 0; i < size; i++) {
                System.out.println(array[i]);
            }
        }
    }

删除指定位置的元素：  
（1）判断索引下标是否在数组的下标0~array.length-1之内  
（2）然后让要删除位置的元素后面的元素挨个往前挪一位就可以了

/**
         * 删除指定位置的元素
         * @param index
         * @throws Exception
         */
        public void delete(int index) throws Exception{
            if (index < 0 || index > size-1 ){
                throw  new Exception("不存在该下标对应的元素");
            }
            for (int i = index; i < size-1; i++) {
                array[i] = array[i+1];
            }
            size--;
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]: /images/20220113/da48433161dd4dd6a2d4093f4b0e0e3f.png