玩转数据结构之动态数组

• 支持泛型
• 支持动态扩容或缩容
• 支持增删改查操作
• 对于增删操作时间复杂度为O(n)，对于改查操作时间复杂度为O(1)；

package com.sjgd.array;

public class Array {
   
   private E[] data;
   
   private int size;

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

   public Array() {
       this(10);
   }

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

   
   public int getSize() {
       return size;
   }

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


   
   public void add(int index, E e) {
       if (index < 0 || index > size) {
           throw new IllegalArgumentException("Add Failed, Require index >=0 and index <= size");
       }
       if (size == data.length) {
           //说明当前数组已满，需要进行扩容
           resize(2 * data.length);
       }
       //索引位置后面的元素都需要往后移1个位置
       for (int i = size - 1; i >= index; i--) {
           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);
   }

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

   
   public void set(int index, E e) {
       if (index < 0 || index >= size) {
           throw new IllegalArgumentException("Add Failed, Require index >=0 and index <= size");
       }
       data[index] = e;
   }


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

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


   public E remove(int index) {
       if (index < 0 || index >= size) {
           throw new IllegalArgumentException("remove Failed, Require index >=0 and index < size");
       }
       E ret = data[index];
       //从删除索引位置之后元素均向前移一位
       for (int i = index + 1; i < size; i++) {
           data[i - 1] = data[i];
       }
       size--;
       //进行空间释放
       data[size] = null;
       //当数组元素到容量1/4时，进行缩容操作
       if (size == data.length / 4 && data.length / 2 != 0) {
           resize(data.length / 2);
       }
       return ret;
   }

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

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

   
   public void removeElement(E e) {
       int index = find(e);
       if (index != -1) {
           remove(index);
       }
   }


   @Override
   public String toString() {
       StringBuilder stringBuilder = new StringBuilder();
       stringBuilder.append(String.format("Array size=%d, capacity=%dn", size, data.length));
       stringBuilder.append("[");
       for (int i = 0; i < size; i++) {
           stringBuilder.append(data[i]);
           if (i != size - 1) {
               stringBuilder.append(",");
           }
       }
       stringBuilder.append("]");
       return stringBuilder.toString();
   }

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