数据结构之数组篇

数组（ArrayList）

普通数组

• 将数据码成一排进行存放
• 优点：通过下标来访问数组中的每一个元素（数组具有随机访问的能力）
• 缺点：数据容量一旦确定就不能更改(数据容量大小固定，是一种静态数据结构)

基于普通数组实现ArrayList

1. ArrayList的基本功能
   ArrayList的基本功能不外乎增、删、改、查等操作
2. 从零开始实现Array
   我们可以仿造ArrayList的基本功能，通过以下的步骤逐步完成自己的Array类 。

   1. 首先——确定Array类的数据成员：
      实现Array类基于基本的数组，所以要有一个基本数组作为该类的属性值，同时要有一个capacity（容量）来表示当前Array对象的容量，还应该要有一个size来表示当前Array对象实际含有的元素个数。事实上，capacity可以通过基本数组的length属性来获得，因此只需要两个属性（基本数组 以及 size）,代码如下：

      /** * 基于普通数组实现Array类 * @author wbkearly * @param <E> Array中元素类型 */
      public class Array<E> {
         
         private E[] data;
         private int size;
      }
      

   2. 为Array类书写一些简单的方法

      /** * 构造函数,传入数组容量capacity构造Array * @param capacity 数组容量 */
      public Array(int capacity) {
      	
      	data = (E[])new Object[capacity];
      	size = 0;
      }
      
      /** * 无参构造函数,默认容量capacity=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;
      }
      

   3. 向Array中添加元素
      值得注意的是，这里向Array中添加元素和普通数组中添加元素有区别，在普通的数组中，当元素超过了容量时，会导致溢出，但是我们的Array类具有自适应的能力，即它可以resize，当数组元素个数大于容量时，它可以增大数组的容量，同时当数组元素个数小于一定范围时，它可以缩小数组的容量以减小程序内存的开销。

        // resize以调整Array大小
        private void resize(int newCapacity) {
       
       	E[] newData = (E[])new Object[newCapacity];
       	for(int i = 0; i < size; i++) {
       		newData[i] = data[i];
       	}
       	data = newData;
        }
        
        /** * 向数组第index位置插入一个新的元素e * @param index 要插入新的元素的位置 * @param e 要插入的新元素 */
       public void add(int index, E e) {
       	
       	if(index < 0 || index > size) {
       		throw new IllegalArgumentException("index越界,index范围需为[0,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++;
       }
       
       // 基于add实现addFirst和addLast
       /** * 向所有元素前添加元素e * @param e 要添加的元素 */
       public void addFirst(E e) {
       	
       	add(0, e);
       }
       
       /** * 向所有元素后添加元素e * @param e 要添加的元素 */
       public void addLast(E e) {
       	
       	add(size, e);
       }
      

   4. 从Array删除元素
      分为两种，即删除指定下标位置元素和删除指定元素，代码如下:

      	/** * 从数组中删除index位置的元素,并返回删除的元素 * @param index 要删除元素的索引index * @return 删除的元素 */
       public E remove(int index) {
       	
       	if(index < 0 || index > size) {
       		throw new IllegalArgumentException("remove失败!index越界,index范围需为[0,size]");
       	}
       	E ret = data[index];
       	for(int i = index + 1; i < size; i++) {
       		data[i-1] = data[i];
       	}
       	size--;
       	data[size] = null;
       	
       	if(size == data.length / 4 && data.length / 2 != 0) {
       		resize(data.length / 2);
       	}
       	
       	return ret;
       }
       
       // 基于remove实现removeFirst和removeLast
       /** * 从数组中删除第一个元素 * @return 原数组中的第一个元素 */
       public E removeFirst() {
       	
       	return remove(0);
       }
       
       /** * 从数组中删除最后一个元素 * @return 原数组中的最后一个元素 */
       public E removeLast() {
       	return remove(size - 1);
       }
       
       /** * 删除数组中值为e的元素 * @param e 待删除的元素e */
       public void removeElement(E e) {
       	
       	int index = find(e);
       	if(index != -1) {
       		remove(index);
       	}
       }
      

   5. 修改指定位置元素

       /** * 修改index索引位置元素为e * @param index 要修改元素的索引 * @param e 修改index索引元素为e */
       public void set(int index, E e) {
       	
       	if(index < 0 || index > size) {
       		throw new IllegalArgumentException("set失败!index越界,index范围需为[0,size]");
       	}
       	data[index] = e;
       }
      

   6. 查询元素
      包括以下方法：

       /** * 获取第一个元素 * @return 数组第一个元素 */
       public E getFirst() {
       	
       	return get(0);
       }
       
       /** * 获取数组最后一个元素 * @return 数组最后一个元素 */
       public E getLast() {
       	
       	return get(size - 1);
       }
       
       /** * 修改index索引位置元素为e * @param index 要修改元素的索引 * @param e 修改index索引元素为e */
       public void set(int index, E e) {
       	
       	if(index < 0 || index > size) {
       		throw new IllegalArgumentException("set失败!index越界,index范围需为[0,size]");
       	}
       	data[index] = e;
       }
       
       /** * 查找数组中是否包含元素e * @param e 要判断是否包含的元素e * @return 是否存在元素e */
       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 要查找索引的元素e * @return 元素e的索引,若不存在,则返回-1 */
       public int find(E e) {
       	
       	for(int i = 0; i < size; i++) {
       		if(data[i].equals(e)) {
       			return i;
       		}
       	}
       	return -1;
       }
      

3. Array类的完整代码

   /** * 基于普通数组实现Array类 * @author wbkearly * @param <E> Array中元素类型 */
   public class Array<E> {
      
      private E[] data;
      private int size;
      
      /** * 构造函数,传入数组容量capacity构造Array * @param capacity 数组容量 */
      @SuppressWarnings("unchecked")
      public Array(int capacity) {
      	
      	data = (E[])new Object[capacity];
      	size = 0;
      }
      
      /** * 无参构造函数,默认容量capacity=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;
      }
      
      /** * 向数组第index位置插入一个新的元素e * @param index 要插入新的元素的位置 * @param e 要插入的新元素 */
      public void add(int index, E e) {
      	
      	if(index < 0 || index > size) {
      		throw new IllegalArgumentException("index越界,index范围需为[0,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++;
      }
      
      private void resize(int newCapacity) {
      	
      	@SuppressWarnings("unchecked")
      	E[] newData = (E[])new Object[newCapacity];
      	for(int i = 0; i < size; i++) {
      		newData[i] = data[i];
      	}
      	data = newData;
      }
   
      /** * 向所有元素前添加元素e * @param e 要添加的元素 */
      public void addFirst(E e) {
      	
      	add(0, e);
      }
      
      /** * 向所有元素后添加元素e * @param e 要添加的元素 */
      public void addLast(E e) {
      	
      	add(size, e);
      }
      
      /** * 获取index索引位置的元素 * @param index 要获取的元素的索引 * @return index索引位置的元素 */
      public E get(int index) {
      	
      	if(index < 0 || index > size) {
      		throw new IllegalArgumentException("get失败!index越界,index范围需为[0,size]");
      	}
      	return data[index];
      }
      
      /** * 获取第一个元素 * @return 数组第一个元素 */
      public E getFirst() {
      	
      	return get(0);
      }
      
      /** * 获取数组最后一个元素 * @return 数组最后一个元素 */
      public E getLast() {
      	
      	return get(size - 1);
      }
      
      /** * 修改index索引位置元素为e * @param index 要修改元素的索引 * @param e 修改index索引元素为e */
      public void set(int index, E e) {
      	
      	if(index < 0 || index > size) {
      		throw new IllegalArgumentException("set失败!index越界,index范围需为[0,size]");
      	}
      	data[index] = e;
      }
      
      /** * 查找数组中是否包含元素e * @param e 要判断是否包含的元素e * @return 是否存在元素e */
      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 要查找索引的元素e * @return 元素e的索引,若不存在,则返回-1 */
      public int find(E e) {
      	
      	for(int i = 0; i < size; i++) {
      		if(data[i].equals(e)) {
      			return i;
      		}
      	}
      	return -1;
      }
      
      /** * 从数组中删除index位置的元素,并返回删除的元素 * @param index 要删除元素的索引index * @return 删除的元素 */
      public E remove(int index) {
      	
      	if(index < 0 || index > size) {
      		throw new IllegalArgumentException("remove失败!index越界,index范围需为[0,size]");
      	}
      	E ret = data[index];
      	for(int i = index + 1; i < size; i++) {
      		data[i-1] = data[i];
      	}
      	size--;
      	data[size] = null;
      	
      	if(size == data.length / 4 && data.length / 2 != 0) {
      		resize(data.length / 2);
      	}
      	
      	return ret;
      }
      
      /** * 从数组中删除第一个元素 * @return 原数组中的第一个元素 */
      public E removeFirst() {
      	
      	return remove(0);
      }
      
      /** * 从数组中删除最后一个元素 * @return 原数组中的最后一个元素 */
      public E removeLast() {
      	return remove(size - 1);
      }
      
      /** * 删除数组中值为e的元素 * @param e 待删除的元素e */
      public void removeElement(E e) {
      	
      	int index = find(e);
      	if(index != -1) {
      		remove(index);
      	}
      }
      
      /** * 重写Object类的toString方法 */
      @Override
      public String toString() {
      	
      	StringBuilder stringBuilder = new StringBuilder();
      	stringBuilder.append(String.format("Array: size = %d, capacity = %d\n", 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();
      }
   }
   

总结：实现自己的Array类有助于加深我们对ArrayList的理解。