Java基础——动态数组

电玩女神 2023-10-02 19:24 6阅读 0赞

**目录**

一、什么是线性表

二、什么是动态数组

三、动态数组的增删改查方法的实现

四、LeetCode 27 题：移除元素（双引用法）

--------------------

### 一、什么是线性表 ###

所谓线性表，就是多个相同数据类型的元素逻辑上呈直线排列，逻辑上连续。

常见的线性表有：数组（顺序表），链表，栈，队列，字符串(char数组)...

### 二、什么是动态数组 ###

Java中提供的数组都是静态数组，即在一个数组定义时确定长度后，使用过程中无法修改此长度。

动态数组就是在普通数组上，增加了一个可以根据元素的个数动态调整数组大小的功能。

### 三、动态数组的增删改查方法的实现 ###

public class MyArr {
        private int[] data;
        //表示当前数组中已经存储的元素个数
        private int size;
    
        //通过构造方法，传入一个长度为length的整形数组
        //data数组初始化，产生一个新的数组对象
        public MyArr(int length) {
    
            this.data = new int[length];
        }
    
        //在数组末尾添加一个值为val的元素
       public void add(int val) {
            data[size]= val;
            size ++;
            //判断数组是否已满，是否需要扩容
            if (size == data.length){
                grow();
            }
        }
        //在数组的index索引位置添加一个值为val的元素
        public void add(int index ,int val) {
            //首先要判断索引位置是否合法
            if (index < 0 || index > size) {
                //错误输出
                System.err.println("索引非法，请重新输入");
            }
            int ret = data[index];
            for (int i = size - 1; i >= index; i--) {
                data[i + 1] = data[i];
            }
            data[index] = val;
            size++;
            if (size == data.length) {
                grow();
            }
        }
            //查询  查询当前动态数组中第一个值为val的元素索引
        public int getByValue(int val){
            for (int i = 0; i < size; i++) {
                if (data[i] == val){
                    return i;
                }
            }
            //循环走完，还未找到val，说明数组中不存在
            return -1;
        }
            //查询 查询当前动态数组中是否包含值为val的元素
        public boolean contains(int val){
    //        for (int i = 0; i < size; i++) {
    //            if (data[i] == val) {
    //                return true;
    //            }
    //        }
    //        return false;
    
            return getByValue(val) != -1;
    
        }
    
        //查询当前动态数组中索引为index的元素值
        public int get(int index){
            if(index < 0 || index >= size){
                System.err.println("索引非法，请重新输入");
                return -1;
            }
            return data[index];
        }
    
        //修改 修改index位置的元素为新的值newval，返回修改前的值
        public int set(int index, int newval) {
            if(index < 0 || index >= size){
                System.err.println("索引非法，请重新输入");
                return -1;
            }
            int ret = data[index];
            data[index] = newval;
            return ret;
        }
    
        //修改 修改第一个值oldVal 的值，更改为新的值 newVal ，返回是否修改成功
        public boolean setVal(int oldVal, int newVal){
    //        for (int i = 0; i < size; i++) {
    //            if(data[i] == oldVal){
    //                data[i] = newVal;
    //                return true;
    //            }
    //        }
            //利用写好的getByValue方法，判断oldVal是否存在
            int index = getByValue(oldVal);
            if (index != -1){
                data[index] = newVal;
                return true;
            }
            return false;
        }
    
        //删除  删除索引为index 对应的元素， 返回删除前的元素
        public int remove (int index){
          if(index < 0 ||index >= size){
              System.err.println("索引非法，请重新输入");
              return -1;
          }
          int ret = data[index];
            for (int i = index; i < size-1 ; i++) {
                data[i] = data[i+1];
            }
            size--;
            return ret ;
        }
    
        //删除  删除数组的头元素
        public int removeFirst(){
           return remove(0);
        }
    
        //删除 删除数组的尾元素
        public int removeLast(){
            return remove(size-1);
        }
    
        //删除  删除第一个值为val的元素，返回是否删除成功
        public boolean removeByValOnce(int val) {
            for (int i = 0; i < size; i++) {
                if (data[i] == val){
                    remove(i);
                    return true;
                }
    
            }
            return false;
        }
    
        //删除  删除数组中所有值为val的元素
        public void removeAllVal(int val){
            for (int i = 0; i < size; i++) {
                //内层循环也要保证索引的合法性
                while (i < size && data[i] == val){
                    remove(i);
                }
    
            }
    
        }
    
        //扩容方法是私有的，因为对程序的使用者来说，根本不知道MyArr类中有一个数组
        //数组的扩容方法对外部也是不可见的
        private void grow() {
    
            this.data = Arrays.copyOf(data,data.length*2);
        }
    
        public String toString(){
            String ret = "[";
            for (int i = 0; i < size; i++) {
                ret += data[i];
                if(i != size-1){
                    ret += ", ";
                }
            }
            ret += "]";
            return ret;
        }
    
    }

### 四、LeetCode 27 题：移除元素（双引用法） ###

输入：nums = [0,1,2,2,3,0,4,2], val = 2
    输出：5, nums = [0,1,4,0,3]

public int removeElement(int[] nums, int val) {
          //  nums = [0,1,2,2,3,0,4,2], val = 2;
            int fir = 0;
            int sec = 0;
            // 若nums[sec] == val，sec++，到下一索引位置，
            // 若nums[sec] != val，将sec位置的值赋值给nums[fir] , fir++，sec++,同时向后移动一位
            //循环的继续条件，sec<nums.length,当sec=nums.length，循环结束
            while (sec < nums.length ) {
                    if (nums[sec] != val ){
                        nums[fir] = nums[sec];
                        fir++;
                    }
                   sec++;
                }
           //循环结束，[0....fir-1]为移除val值后的数组，当前有效元素个数为fir
           return fir;
       }