自己动手实现java数据结构（一） 向量

　　部分增删改查接口会通过下标来进行操作，必须对访问数组的下标进行校验。

下标越界检查方法实现：

 
     * 插入时,下标越界检查
     *  index 下标值
     void rangeCheckForAdd( index){
        :::如果下标小于0或者大于size的值，抛出异常
        :::注意：插入时，允许插入向量的末尾，因此(index == size)是合法的
        if(index > this.size || index < 0throw new RuntimeException("index error  index=" + index + " size=" + .size) ;
        }
    }

    
     * 下标越界检查
     * void rangeCheck(:::如果下标小于0或者大于等于size的值，抛出异常
        if(index >= .size) ;
        }
    }

3.3.2 插入方法实现：

 add(E e) {
        :::插入新数据前进行扩容检查
        expandCheck();

        ;::在末尾插入元素
        this.elements[this.size] = e;
        :::size自增
        this.size++;

        truevoid add( index,E e) {
        :::插入时，数组下标越界检查
        rangeCheckForAdd(index);
        :::插入位置下标之后的元素整体向后移动一位(防止数据被覆盖，并且保证数据在数组中的下标顺序)
        :::Tips: 比起for循环，System.arraycopy基于native的内存批量复制在内部数组数据量较大时具有更高的执行效率
        int i=this.size; i>index; i--this.elements[i] = this.elements[i-1];
        }

        :::在index下标位置处插入元素"e"
        this.elements[index] =;
    }

插入方法——时间复杂度:

　　可以看到，向量的插入操作会导致插入位置之后的数据整体向后平移一位。

　　在这里，使用了for循环将数据一个一个的进行复制。事实上，由于数组中下标连续的数据段在内存中也是连续成片的(逻辑意义上的)，因此操作系统可以通过批量复制内存的方法来优化这种"数组中一片连续数据复制"的操作。java在jdk中自带的向量实现中采用了native的System.arraycopy()方法来实现这个优化操作。

　　在我的向量实现中，有多处这种"数组中一片连续数据复制"的操作，为了增强代码的可理解性，都使用了for循环这种较低效率的实现方式，希望能够理解。

　　虽然System.arraycopy能够优化这一操作的效率，但是在渐进的意义上，向量插入操作的时间复杂度为O(n)。

动态扩容：

　　前面我们提到，向量相比数组的一大改进就是向量能够在数据新增时根据存储的数据量进行动态的扩容，而不需要人工的干预。

向量扩容方法的实现：

 
     * 内部数组扩容检查
     * void expandCheck(){
        :::如果当前元素个数 = 当前内部数组容量
        this.size == .capacity){
            :::需要扩容

            :::先暂存之前内部数组的引用
            Object[] tempArray = .elements;
            :::当前内部数组扩充 一定的倍数
            this.capacity = (int)(this.capacity * EXPAND_BASE);
            :::内部数组指向扩充了容量的新数组
            this.elements = new Object[.capacity];

            :::为了代码的可读性，使用for循环实现新老数组的copy操作
            :::Tips: 比起for循环，System.arraycopy基于native的内存批量复制在内部数组数据量较大时具有更高的执行效率
            int i=0; i<tempArray.length; i++this.elements[i] = tempArray[i];
            }
        }
    }

动态扩容——时间复杂度：

　　动态扩容的操作由于需要进行内部数组的整体copy，其时间复杂度是O(n)。

（编辑：网站开发网_盐城站长网 ）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!