自己动手做Array

学习数据结构

一直以来在学习java web开发，里面很少涉及到数据结构相关的编程，再加上大一没有怎么好好学这门课程，这段时间开始慢慢捡回来，不说如何去精通它，但希望自己从数据结构开始训练自己的基础代码能力，如今用框架用的已经连代码都不会写了。。。

Array代码

/**
 * @author Lin
 * @date 2019-04-13 16:52
 **/
public class Array<E> {

  /**
   * 泛型数组
   */
  private E[] array;
  /**
   * 数组大小
   */
  private int size;

  /**
   * 有参构造方法
   */
  public Array(int capacity) {
    //强制类型转换
    array = (E[]) new Object[capacity];
    //size指向0
    size = 0;
  }

  /**
   * 默认构造函数
   */
  public Array() {
    //默认容量为8
    array = (E[]) new Object[8];
    size = 0;
  }

  /**
   * 获取数组容量
   */
  public int getCapacity() {
    return array.length;
  }

  /**
   * 获取数组元素个数
   */
  public int getSize() {
    return size;
  }

  /**
   * 返回数组是否为空
   */
  public boolean isEmpty() {
    return size == 0;
  }

  /**
   * 在index处插入一个新的元素
   *
   * @param index 索引
   * @param e 插入的元素
   */
  public void add(int index, E e) {
    //判断index是否合法
    if (index < 0 || index > size) {
      throw new IllegalArgumentException("index is not valid!");
    }
    //判断此时size和capacity是否相等，如果相等需要动态增加数组容量
    if (size == this.getCapacity()) {
      resize(size * 2);
    }
    //将index索引处后面的元素向后移一个
    for (int i = size-1; i >= index; i--) {
      array[i + 1] = array[i];
    }
    array[index] = e;
    ++size;
  }

  /**
   * 动态扩容
   *
   * @param capacity 新的容量
   */
  private void resize(int capacity) {
    //新构建一个数组，将原来数组赋值上去
    E[] temp = (E[]) new Object[capacity];
    for (int i = 0; i < size; i++) {
      temp[i] = array[i];
    }
    array = temp;
  }

  /**
   * 在头部添加元素
   *
   * @param e 元素
   */
  public void addFirst(E e) {
    //直接调用add方法
    add(0, e);
  }

  /**
   * 在尾部添加元素
   */
  public void addLast(E e) {
    add(size, e);
  }

  /**
   * 获取索引位置的元素
   *
   * @param index 索引
   * @return 该索引处的元素
   */
  public E get(int index) {
    return array[index];
  }

  /**
   * 修改索引位置的元素
   *
   * @param index 索引
   * @param e 要设置的元素
   */
  public void set(int index, E e) {
    array[index] = e;
  }

  /**
   * 数组中是否包含元素
   *
   * @param e 元素
   * @return 布尔
   */
  public boolean contains(E e) {
    for (E originalElement : array) {
      if (originalElement.equals(e)) {
        return true;
      }
    }
    return false;
  }

  /**
   * 查找数组中第一次出现该元素的索引，不存在则返回-1
   *
   * @param e 元素
   * @return 索引
   */
  public int find(E e) {
    for (int i = 0; i < array.length; i++) {
      if (array[i].equals(e)) {
        return i;
      }
    }
    return -1;
  }

  /**
   * 删除指定索引元素
   *
   * @param index 索引
   * @return 删除的元素
   */
  public E remove(int index) {
    E removeElement = array[index];
    if (index < 0 || index >= size) {
      throw new IllegalArgumentException("index is not valid!");
    }
    for (int i = index; i < size; i++) {
      array[i] = array[i + 1];
    }
    --size;
    //压缩空间
    //这里使用懒压缩，如果在size为容量一半的时候就缩减容量为一半，则当这个数组再次增加一个元素的时候，它又会进行扩容。所以这里给予一定的空间
    if (size==array.length/4&&array.length/2!=0){
      resize(array.length/2);
    }
    return removeElement;
  }

  /**
   * 删除第一个
   *
   * @return 删除的元素
   */
  public E removeFirst() {
    return remove(0);
  }

  /**
   * 删除最后一个元素
   *
   * @return 删除的元素
   */
  public E removeLast() {
    return remove(size-1);
  }

  /**
   * 删除第一个出现的某个元素
   *
   * @param e 需要删除的元素
   */
  public void removeElement(E e) {
    remove(find(e));
  }

  @Override
  public String toString() {

    StringBuilder res = new StringBuilder();
    res.append(String.format("Array: size = %d , capacity = %d\n", size, array.length));
    res.append('[');
    for (int i = 0; i < size; i++) {
      res.append(array[i]);
      if (i != size - 1) {
        res.append(", ");
      }
    }
    res.append(']');
    return res.toString();
  }
}

总结

在Java中，数组的容量一旦声明就无法改变，这里我们通过封装实现了动态数组，并且实现了动态数组的增删改查等简单的功能。其中最为重要的是数组怎样实现增加，删除和动态扩容。

• 增加

  当数组某个位置需要增加元素的时候，我们先要将该索引处后面的元素从最后一个元素开始把各自向后移动一个位置。

• 删除

  当数组某个位置需要删除元素的时候，我们先要将该索引处后面的元素从索引处后面的元素开始依次将各自向前移动一个位置。即为后面元素覆盖前面元素。

• 动态扩容

  当数组进行增加的时候，如果数组容量不够时我们需要进行扩容。当数组中进行删除的时候，如果数组使用量已经远小于数组容量的时候我们需要进行压缩，来减少无用的空间。

  我们上文代码实现扩容的方式是在数组增加和删除的时候重新构建一个数组并且将原来的数组赋值到新的数组中去。为了避免一直重复的重构容量大小，我们将扩充的容量变为原来容量的两倍(如果每次容量只是加1或者很少那么每次add之后都要执行重构容量，但是重构容量需要重新遍历数组，时间复杂度为O(n),极大地浪费时间，所以我们这里通过牺牲空间来节省时间)。当每次删除元素的时候，我们将判断数组使用量是否等于容量的四分之一，当为true的时候我们我们将容量变为原来一半以节省空间(这里为什么是四分之一和一半呢？其实具体数值并不是固定的，但是我们这里实现的是懒压缩，如果这里的判断条件为一半，当使用量为容量一半的时候我们就之间将容量变为原来一半，那么之后再次进行add方法时我们又需要扩容，从而引起复杂震荡，这是得不偿失的)。

  上文Array代码基本是模仿JDK的ArrayList来实现的，在ArrayList中也是通过上述方法来实现的。

  如实现动态扩容:

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //这里使用了移位，为了使运算更加快速
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //这里设置的是最小容量和最大容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}