（希望我所描述的一切，给你带来收获！）
我们将要使用的是JAVA中的静态数组——E[] data = new E[]();去实现一个属于我们自己的动态数组
第一步：（关于泛型不作过多解释）
1 public class Array<E> { 2 private E[] data; 3 private int size; 4 }
data是我们需要的数组，size是我们需要维护的动态数组的长度；size可以认为是数组的索引号，size总是指向数据的末端——当整个数组为空时size指向的是 data[0] 的位置，当数组只有 data[0] 一个元素时，size指向的数据末端是 data[1];也就是说，size总是指向用户数据(用户添加的数据)的后一个位置。
第二步：
1 /** 2 * 3 * @param capacity 4 */ 5 public Array(int capacity) { 6 data = (E[]) new Object[capacity]; 7 }
我们申请一个容量为capacity的数组，注意！java中不能直接对泛型进行new的操作，但Object是所有类的父类，通过new一个Object再进行类型强转是行得通的！但是，有时我们并不确定我们所需要多少大小的capacity，为了方便，我们还需要一个无参构造函数，初始化一个默认的capacity数组（默认的capacity我给的是10）
1 /** 2 * the default capacity is 10 3 */ 4 public Array() { 5 this(10); 6 }
第三步：实现一些简单的操作，例如：获取当前数组的长度、判断数组是否为空......
1 /** 2 *@return the current data length of the array 3 */ 4 public int getSize() { 5 return size; 6 } 7 8 /** 9 * Determines whether the array is empty 10 * @return false or true 11 */ 12 public boolean isEmpty() { 13 return size == 0; 14 } 15 16 /** 17 * get the Array capacity 18 * @return Array capacity 19 */ 20 public int capacity() { 21 return data.length; 22 }
我们一定要明确的一点是：用户只能看到size长度的data(这是外界给予可能是有价值意义的数据)，而data.length则只是能承载多少用户数据的边界（限度）
第四步：为我们的Array<E>实现增加元素的操作add(int index,E e)方法
1 /** 2 * Insert an element on an index 3 * @param index 4 * @param e 5 */ 6 public void add(int index,E e) { 7 if (index < 0 || index > size) 8 throw new IllegalArgumentException("Add failed.Array is full"); 9 for (int i = size - 1; i >= index; i--) { 10 data[i+1] = data[i]; 11 } 12 data[index] = e; 13 size++; 14 }
需要注意的是，用户指定位置插入元素，index值一定要具有合法性——即index属于[0,size]
循环体中，data[i+1] = data[i]的语义是明显的——前一个元素向后一个元素移动。最初的移动在Array的尾部，即是 size - 1 的位置
第五步：移除Array中的所有的元素e
我们先理清思路：1、移除元素e我们需要先获得元素e所在的index
2、通过目标index，我们只需要进行 data[index] = data[ index + 1 ]——拿目标元素所在位置的下一个位置上的元素去覆盖目标元素
3、覆盖操作肯定是在循环中进行的，因为不一定只有一个元素e，很可能有相连的e，这时，当第一次覆盖操作结束之后，我们应该还需要再考察覆盖之后的index是否还是e
1 /** 2 * remove all "e" from the array 3 * @param e 4 */ 5 public void removeElements(E e) { 6 for (int i = 0; i < size; i++) { 7 if (data[i].equals(e)) { 8 remove(i); 9 i--; 10 } 11 } 12 }
removeElements(E e)复用了remove(int index)
1 /** 2 * remove elements from index positions 3 * @param index 4 * @return 5 */ 6 public E remove(int index) { 7 if (index < 0 || index >= size) 8 throw new IllegalArgumentException("remove failed,Index is illegal"); 9 E ret = data[index]; 10 for (int i = index + 1; i < size; i++) { 11 data[i - 1] = data[i]; 12 } 13 size--; 14 return ret; 15 }
关于removeElements(E e)其实还有其他方法去实现，在这里小编就再列个方法：我们可以构建一个removeElement(E e)方法，这个方法每运行一次就移除Array中首个元素e，那么我们可以在removeElements(E e)中复用此方法，逻辑上加以判断就好
第六步：当我们添加的数据长度超出capacity容量时就应该考虑换一个更大的数组去容纳这些数据！
1 private void resize(int newCapacity) { 2 E[] newData = (E[]) new Object[newCapacity]; 3 for (int i = 0; i < size; i++) { 4 newData[i] = data[i]; 5 } 6 data = newData; 7 }
主要是在添加方法中复用该resize方法
1 /** 2 * Insert an element on an index 3 * @param index 4 * @param e 5 */ 6 public void add(int index,E e) { 7 if (index < 0 || index > size) 8 throw new IllegalArgumentException("Add failed.Array is full"); 9 if (size == data.length) { 10 resize(2*data.length); 11 } 12 for (int i = size - 1; i >= index; i--) { 13 data[i+1] = data[i]; 14 } 15 data[index] = e; 16 size++; 17 }
假设data数组的容量为10，那么最大索值index就为为9，当index == 9这个位置存入值时，size即为10，所以用if (size == data.length)去判断数组是否应该扩 容。当数组空间已经装满数据，我们再次添加数据时就会触发resize方法，使得数组“扩容”。
以下是缩容的算法
1 /** 2 * remove elements from index positions 3 * @param index 4 * @return 5 */ 6 public E remove(int index) { 7 if (index < 0 || index >= size) 8 throw new IllegalArgumentException("remove failed,array is full"); 9 E ret = data[index]; 10 for (int i = index + 1; i < size; i++) { 11 data[i - 1] = data[i]; 12 } 13 size--; 14 if (size == data.length/4 && data.length/2 != 0) { 15 resize(data.length/2); 16 } 17 return ret; 18 }
我们判定数组缩容的条件是 size == data.length/4，即当前数据的总量只用capacity总容量的 1/4。
为什么不是 size == data.length/2 ？
理由：如果是 size == data.length/2 就开始缩容的话，那么当我们再次添加元素时又会进行扩容，两次基本的O(1)的操作却触发了两次O(n)的数组拷贝，试想一下，如果我的操作是反复的在 size == data.length/2 时添加和移除呢？势必每一次的操作都会是O(n)级别的复杂度！这就是复杂度的震荡!
data.length/2 != 0 ===> 考虑data.length == 1时， 1/2 == 0，数组的容量自然是不能为0的!
