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

　　但是站在全局的角度，动态扩容只会在插入操作导致空间不足时偶尔的被触发，所以整体来看，动态扩容的时间复杂度为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依然占用了很多不必要的内存空间。

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

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