手把手写一个集合框架（一）动态数组

• 数组的构造函数

   //首先，我们需要设计一个带有泛型功能的类
   public class Array<E> {
      private E[]  data;
      private int size;
     //构造函数，空参数默认的容量为10
      public Array(){
        this(10);
     }
    //用户带参数的构造函数
     public Array(int Capacity){
        data = (E[])new Object[Capacity];
        size = 0;
    }
}

• 实现动态数组的基本功能

   public int getCapacity(){ //获取数组容量
        return data.length;
    }
    public int getSize(){//获取数组元素个数
        return this.size;
    }
    public boolean isEmpty(){ //判断数组是否为空
        return this.size==0;
    }
   //当我们数组的元素已经满的时候，我们需要扩容
    private 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){
        if(index<0 || index>size) throw new 
            IllegalArgumentException("index is error...");
        if(size==data.length)
            resize(2*data.length);
        for(int i= size-1;i>=index ;i--){
            data[i+1] = data[i];
        }
        data[index]=e;
    }
    //再添加两个辅助函数，方便接口调用
     public void addFirst(E e){//在第一个位置插入一个元素
           add(0,e);
      }
     public void addLast(E e){//数组最后添加一个元素
        if(size == data.length)
            throw new IllegalArgumentException("add last...");
        data[size]=e;
        size++;
    }

• 向数组删除元素

     //删除某一个索引下面的元素
     public E remove(int index){//删除某一个索引下面的元素
        if(index<0 || index>size)
            throw new IllegalArgumentException();
        E ret = data[index];
        for(int i=index+1;i <size;i++){
              data[i-1] = data[i];
        }
        size--;
      //使用懒惰策略进行缩容，同时当元素为1个就不能缩容了
        if(size == data.length >>2 && size>1)
            resize(data.length>>1); //缩小一半容量
        return ret;
    }
    public void removeElement(E e){ //安装元素删除
        int index = find(e);
        if(index!=-1)
            remove(index);
        return;
    }
    //添加两个辅助接口函数，方便我们后续基于数组实现其他数据结构
     public E removeFirst(){
        return remove(0);
    }
     public E removeLast(){
        return remove(this.size-1);
    }

• 向数组修改元素

    public void set(int index ,E e){ //修改某一个索引下面的元素值
        if(size==data.length)
            throw new IllegalArgumentException("add last...");
        data[index]=e;
    }

• 在数组中查询某一元素

       public int find(E e){ //查找元素的索引
        for(int i=0;i<size;i++){
            if(data[i].equals(e))
                return i;
        }
        return -1;
    }
    public boolean contains(E e){ //查找一是否存在一个元素
        for(int i=0;i<size;i++){
            if(data[i].equals(e))
                return true;
        }
        return false;
    }

• 在数组中获取元素

    //这些方法有利于我们后续基于数组实现其他数据结构
    public E get(int index){//获取指定下标元素
        if(index<0||index>=size)
            throw new IllegalArgumentException("index error");
        return data[index];
    }
    public E getLast(){//获取最后一个元素
        return get(size);
    }
    public E getFirst(){//获取第一个元素
        return get(0);
    }

• 总结
  本文借助静态数组实现了一种动态数组，包括增加、删除、修改、查找等功能。为我们后续基于动态数组实现栈和队列打下基础。