实现动态数组

因为数组开辟时是静态的。在这里底层使用静态数组二次封装一个属于自己的动态数组类Array

Array类

public class Array<E>{
  private E[] data; //开辟一个数组
  private int size; //指向第一个没有元素的索引,也代表数组中有多少个有效的元素

  /**
   * 有参构造函数
   * @param capacity 数组的容量
   */

  public Array(int capacity){
      data = (E[])new Object[capacity];
      size = 0;
  }

  /**
   * 默认构造函数,默认容量给10
   */
  public Array(){
      this(10);
  }

  /**
   * 获取数组中的元素个数
   * @return元素个数
   */

  public int getSize(){
      return size;
  }

  /**
   * 获取数组的容量
   * @return数组的大小
   */

  public int getCapacity(){
      return data.length;
  }

  /**
   * 返回数组是否为空
   * @return 数组是否为空
   */

  public boolean isEmpty(){
      return size == 0;
  }

  /**
   * 插入新元素
   * @param index 在index插入
   * @param e 新元素的值
   */
  public void add(int index, E e){

      //index不能为负,index如果大于size说明数组不是紧密排列的,则不合法
      if(index < 0 || index > size){
          throw new IllegalArgumentException("add() failed. Require index >= 0 && index <= size");
      }
      if(size == data.length){ //如果此时元素个数等于数组长度,则进行动态扩容
          resize(2 * data.length);
      }
      //将元素往后挪动
      for(int i = size-1 ; i >= index ; i-- ){
          data[i+1] = data[i];
      }
      data[index] = e;
      size ++;
  }

  /**
   * 向所有元素后添加一个新元素
   * @param e 要插入的元素
   */

  public void addLast(E e){
     add(size,e);
  }


  /**
   * 在数组头部插入一个元素
   * @param index
   * @return 元素位置
   */
  public void addFirst(E e){
      add(0,e);
  }

  /**
   * 获取index位置的元素
   * @param index 要获取的元素的索引
   * @return 元素值
   */

  public E get(int index){
      if(index < 0 || index >= size){
          throw new IllegalArgumentException("Get failed,Index is illegal");
      }
      return data[index];
  }

  /**
   * 获取最后一个元素
   * @return 最后一个元素
   */
  public E getLast(){
      return get(size - 1);
  }

  /**
   * 获取第一个元素
   * @return 第一个元素
   */
  public E getFirst(){
      return get(0);
  }

  /**
   * 修改Index索引位置的元素为e
   * @param index 要修改的元素的索引
   * @param e 要修改的元素的值
   */

  void set(int index,E e){
      if(index < 0 || index >= size){
          throw new IllegalArgumentException("Set failed,Index is illegal");
      }
      data[index] = e;
  }

  /**
   *查找数组中是否含有元素e
   * @param e 要查找的元素的值
   * @return true or false
   */

  public boolean contains(E e){
      for(int i = 0 ; i < size ; i++){
          if(data[i].equals(e))
              return true;
      }
      return false;
  }

  /**
   * 查找数组中元素e所在的索引,如果不存在则返回-1
   * @param e 要查找的元素的值
   * @return 返回索引或者-1
   */

  public int find(E e){
      for(int i = 0 ; i < size ; i++){
          if(data[i].equals(e))
              return i;
      }
      return -1;
  }

  /**
   * 从数组中删除第一个元素elem
   * @param elem
   * @return true or false
   */
  public boolean removeElement(E elem){
      int index = find(elem);
      if(index != -1){
          remove(index);
          return true;
      }
      return false;
  }

  /**
   * 删除Index位置的元素,返回index位置的元素
   * @param index 要删除的索引位置的值
   * @return 返回删除的元素的值
   */

  public E remove(int index){
      if(index < 0 || index >= size){
          throw new IllegalArgumentException("Remove failed.Index is illegal");
      }
      E temp = data[index];
      for(int i = index + 1  ; i < size ; i++){
          data[i - 1] = data[i];
      }
      size --;
      data[size] = null; // loitering objects. 释放size位置的内容(非必须,因为访问不到)

      if(size == data.length / 4 && data.length / 2 != 0){ //如果删除元素过多,少于四分之一则数组缩小容量
          resize(data.length / 2);
      }
      return temp;
  }

  /**
   * 删除第一个元素
   * @return
   */

  public E removeFirst(){
      return remove(0);
  }

  /**
   * 删除数组中最后一个元素
   * @return
   */

  public E removeLast(){
      return remove(size-1);
  }

  /**
   * 覆盖父类的方法,定义本类在打印输出时打印的信息
   * @return 打印输出数组字符串
   */
  @Override
  public String toString(){
      StringBuilder res = new StringBuilder();
      res.append(String.format("Array: size = %d,capacity = %d\n",size,data.length));
      res.append('[');
      for(int i = 0 ; i < size ; i ++){
          res.append(data[i]);
          if(i != size - 1)
              res.append(",");
      }
      res.append(']');
      return res.toString();
  }

  /**
   * 扩容数组
   * @param newCapacity 新的数组的大小
   */

  private void resize(int newCapacity){
      E[] newData =(E[]) new Object[newCapacity];
      for(int i = 0 ;i < size ; i++) {
          newData[i] = data[i];
      }
      data = newData;
  }
}

说明: 1.实现动态数组的关键函数是类中的resize()函数,动态数组的底层实现有多种方式,比如本文讲到的使用静态数组进行扩容缩容,或者使用链表。 动态数组的实现原理其实非常简单,假设数组的已经满了,那么如果继续添加元素,则会报出异常。 实现动态数组的思路是,如果这时候数组满了,那么开辟一个新的数组,这个新数组的容量比原数组大(比如是原数组的1.5倍或者2倍,本文采用2倍),然后将原数组的数据拷贝到新开辟的大数组中(这里需要循环),原来的数组data实际上是一个引用,在拷贝之后将data指向新的数组newData,这时候data这个成员变量和newData指向的是同一个空间,因为newData是封装在函数中,在函数执行结束后就失效了,而data是在整个类中的,它的生命周期是和类一样的。而原来的数组,因为没有东西指向它,java的垃圾回收机制会自动回收。这样扩容过程就结束了。

2.在remove()函数中,有一个缩容的操作,即当前的元素个数小到一定程度的时候,调用resize()函数,缩小数组的容量为当前数组容量的一半。这里是小于四分之一,并且缩小一半后的容量不能为0(所以在条件中判断data.length / 2 != 0),这时再执行缩小操作。缩容的界限之所以选取1/4是因为如果removeLast()后刚好是数组的一半了,这时候进行缩容,然后又进行添加的时候,这时候又要进行扩容,这样如果有频繁的增删操作,在resize()函数中就会耗费大量的时间,所以采取Lazy解决方案。在删除元素后元素是1/2时,不着急进行缩容操作,而是等到元素为容量的1/4之一时再进行缩容,只缩容1/2,还留出1/4的空间。这样就防止了复杂度的震荡。

简单的复杂度分析

·添加操作

addLast(e) O(1)

addFirst(e) O(n)

add(index,e) O(n/2) = O(n) //这里是简单的计算,严格计算需要使用概率论的知识,使用期望

resize() O(n)

所以添加操作的整体时间复杂度是O(n)

·删除操作

removeLast(e) O(1)

removeFirst(e) O(n)

remove(index,e) O(n/2) = O(n)

resize() O(n)

整体时间复杂度是O(n)

·修改操作

set(index,e) O(1)

·查找操作

get(index) O(1)

contains(e) O(n)

find(e) O(n)

总结: ·增 O(n) ·删 O(n) ·改 已知索引O(1);未知索引O(n) ·查 已知索引O(1);未知索引O(n)