动态数组

概念

基于Java提供的静态数组封装自己的动态数组,动态数组涉及的组成部分如下图所示。

组成部分解读

  • data:静态数组,通过泛型支持多种类型的元素:private E[] data;
  • size:数组的大小,作为数组的尾指针,在元素数量改变的时候务必维护指针的位置。

    • size = maxIndex + 1
    • 当数组为空,size = 0
    • 当数组为满,size = capacity
  • capacity:数组的容量,不需要另外声明成员变量:capacity = data.length

动态数组的运算

  • 扩容操作

    public void resize(int newCapacity){
        E[] newData = (E[]) new Object[newCapacity];
        for(int i = 0; i < size; i++){
            newData[i] = data[i];
        }
        data = newData;
    }
  • 添加操作

    • 在指定索引插入
    public void add(int index,E e){
        //capacity = 数组的容量
        if(size == data.length){
            //throw new IllegalArgumentException("容量满了");
            resize(2 * data.length);
        }
        //size = maxIndex + 1 --->   maxIndex = size - 1   输入的index > maxIndex + 1
        if(index < 0 || index > size - 1 + 1){
            throw new IllegalArgumentException("参数不符合要求");
        }
        //index以后的元素往后移动一位,并在index处插入元素e
        for(int i = size - 1; i >= index; i--){        //i代表要移动的位置,所以i>=index都需要移动
            data[i+1] = data[i];
        }
        data[index] = e;
        size++;        //维护尾指针
    }
    • 在动态数组头插入
    public void addFirst(E e){
        add(0,e);
    }
    • 在动态数组尾插入
    public void addLast(E e){
        add(size,e);        //size指向最大索引元素后的一个元素
    }
  • 删除操作

    • 删除指定索引元素
    public E remove(int index){
        if(index < 0 || index > size -1){
            throw new IllegalArgumentException("参数不合法");
        }
        E ret = data[index];        //疏忽:删除应该返回删除元素
        for(int i = index; i < size - 1; i++){
            data[i] = data[i+1];
        }
        size--;
        data[size] = null;        //疏忽:清空最后一个元素,为了让垃圾回收机制回收
        //重新调整容量
        //当前数组元素个数 ==  容量的1/4
        if(size == data.length / 4 && data.length /2 != 0){  //原本是/2  解决复杂度震荡
            resize(data.length / 2);
        }
        return ret;
    }
    • 删除头索引元素
    public E removeFirst(){
        return remove(0);
    }
    • 删除尾索引元素
    public E removeLast(){
        return remove(size-1);
    }
    • 根据元素的值删除元素
    public void removeElement(E element){
        int index = find(element);
        if(index != -1){
            remove(index);
        }
    }
  • 修改操作

    public void set(int index,E e){
        data[index] = e;
    }
  • 查询操作

    • 根据索引查
    public E get(int index){
        return data[index];
    }
    • 根据元素查,注意使用值比较
    public int find(E e){
        for(int i = 0; i < size; i++){    //注意遍历终止条件不是size - 1
            if(data[i].equals(e)){        //不用引用比较,值比较更合理
                return i;
            }
        }
        return -1;
    }
    • 是否包含某个元素
    public boolean contains(E e){
        //先找出索引
        int index = find(e);
        //判断索引是否存在
        return index != -1;
    }

时间复杂度分析

最坏复杂度

问:如果只对最后一个元素操作依然是O(n)?因为resize? 答:是的。

均摊复杂度

下面是对增加操作addLast均摊复杂度分析。

案例分析:

  • 在这个案例中,使用9次addLast操作,会触发一次resize,会进行(8 + 8 + 1 = 17)次基本操作;平均每次addLast操作,会进行(17 / 9 = 2)次基本操作
  • 进一步推广,假如capacity = n,则n + 1次addLast操作,会触发一次resize,会进行(n + n + 1 = 2n + 1)次基本操作;平均每次addLast操作,会进行(2n + 1 / n + 1 = 2)次基本操作
  • 最后得出结论,平均每次addLast操作,会进行2次基本操作,这样均摊计算,resize时间复杂度是O(1)的!这样比最坏复杂度更有意义

复杂度震荡

当数组容量capacity = n,也就是说数组容量的扩容和缩容的临界点都为n的时候,如果反复addLast和removeLast,会造成数组的不断扩容和缩容,这样会浪费时间,每次都需要O(n),发生震荡!

  • 出现问题的原因:removeLast时,resize过于着急
  • 解决方案:对于增加操作,不够必须要扩容,但是对于删除操作,有多的空间不一定需要缩容。因此对于删除操作,可以使用Lazy的方案,也就是说更慢一点进行缩容。这也就是remove操作由size == data.length / 2修改为size == data.length / 4的原因。
if(size == data.length / 4 && data.length /2 != 0){  //原本是/2  解决复杂度震荡
    resize(data.length / 2);
}
  • 还有一个问题,为什么需要缩容到原来的一半,而不是四分之一?原因是防止执行增加操作的时候再需要扩容。
©著作权归作者所有

发表评论

正在加载 Emoji