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

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

下标越界检查方法实现：

 
     * 插入时,下标越界检查
     *  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)。

　　但是站在全局的角度，动态扩容只会在插入操作导致空间不足时偶尔的被触发，所以整体来看，动态扩容的时间复杂度为O(1)。

3.3.3 删除方法实现：

    @Override
    @SuppressWarnings("unchecked")
    public E remove( index) {
        :::数组下标越界检查
        rangeCheck(index);

        :::先暂存将要被移除的元素
        E willBeRemoved = (E).elements[index];
        
        :::将删除下标位置之后的数据整体前移一位
        int i=index+1; i<this.elements[i-1] = .elements[i];
        }

        :::由于数据整体前移了一位，释放列表末尾的失效引用，增加GC效率
        this.elements[(this.size - 1)] = :::size自减
        this.size--:::返回被删除的元素
         willBeRemoved;
    }

删除方法——时间复杂度:

　　向量的删除操作会导致被删除位置之后的数据整体前移一位。

　　和插入操作类似，向量删除操作的时间复杂度为O(n)。

3.3.4 修改/查询方法实现：

public E set(:::先暂存之前index下标处元素的引用
        E oldValue = (E).elements[index];
        :::将index下标元素设置为参数"e"
         e;

        :::返回被替换掉的元素
         oldValue;
    }

    @Override
    @SuppressWarnings("unchecked"public E get(:::返回对应下标的元素
        return (E).elements[index];
    }

修改/查询方法——时间复杂度：

　　可以看到，向量的修改和查询操作都直接通过下标访问内部数组。

　　通过下标访问数组内部元素只需要计算偏移量即可直接访问对应数据，因此向量修改/查询操作的时间复杂度为O(1)。

3.4 向量其它接口：

3.4.1 clear方法

　　clear方法用于清空向量内的元素，初始化向量。

   @Override
     clear() {
        :::遍历列表，释放内部元素引用，增加GC效率
        ;
        }

        :::将size重置为0
        this.size = 0;
    }

3.4.2 trimToSize方法

　　前面提到，向量在空间不足时会自动的进行扩容。自动增长的特性非常方便，但是也带来了一个问题：向量会在新增元素时扩容，但出于效率的考量，删除元素却不会自动的收缩。举个例子：一个很大的向量执行clear时，虽然内部元素的引用被销毁，但是内部数组elements依然占用了很多不必要的内存空间。

（编辑：ASP站长网）