【玩转数据结构 从入门到进阶】不要小瞧数组

数组，看似是最简单的数据结构，但是，大多数语言为我们提供的都是静态数组，如何封装一个属于我们自己的动态数组，将是这一章讨论的重点。同时，我们也将探讨泛型，复杂度分析，乃至复杂度的震荡，等相关高级话题

package Arr;

public class Array <E>{

	private E[] data;
	private int size;   //数组大小

	// 构造函数，传入数组的容量capacity构造Array
	public Array(int capacity) {
		data = (E[])new Object[capacity];
		size = 0;
	}

	// 默认构造方法,默认数组的容量capacity=10
	public Array() {
		this(10);
	}

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

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

	// 返回的数组是否为空
	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);
		}
		for (int i = size - 1; i >= index; i--) {
			data[i + 1] = data[i];
		}
		data[index] = e;
		size++;
	}
	// 向数组中添加元素
	public void addList(E e) {
		if (size == data.length) {
			throw new IllegalArgumentException("AddLast failed. Array is full.");
		}
		data[size] = e;
		size++;
	}

	// 向数组头添加元素
	public void addFirst(E e) {
		add(0, e);
	}
    //取出index索引位置的元素
	public E get(int index) {
		if(index<0||index>=size) {
			throw new IllegalArgumentException("Get failed. Index is illegal");
		}
		return data[index];
	}
	//取出最后一个元素
	public E getLast() {
		return get(size-1);
	}
	//取出第一个元素
	public E getFirst() {
		return get(0);
	}
	
	
	//修改index索引位置的元素e
	public void set(int index,E e) {
		if(index<0||index>=size) {
			throw new IllegalArgumentException("Get failed. Index is illegal");
		}
		data[index]=e;
	}
	//查找数组中是否存在元素e
	public boolean contains(E e) {
		for (int i = 0; i <size; i++) {
			if(data[i]==e) {
				return true;
			}	
		}
		return false;
	}
	//查找数组中的元素e所在的索引，如果不存在元素e,返回-1
	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. Index id illegal");
		}
		E ret=data[index];
		for (int i = index+1; i <size; i++) {
			data[i-1]=data[i];	
		}
		size--;
		
		if(size==data.length/2) {    //缩小数组容量
			resize(data.length/2);
		}
		return ret;
	}
	//从数组中删除第一个元素
	public E removeFirst() {
		return remove(0);
	}
	//从数组中删除最后一个元素
	public E removeLast() {
		return remove(size-1);
	}
	//从数组中删除元素e
	public void removeElement(E e) {
		int index=find(e);
		if(index!=-1) {
			remove(index);
		}
	}
	
	
	@Override
	public String toString() {
		StringBuffer res=new  StringBuffer();
		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();		
	}
	
	
	private void resize(int newCapacity) {
		E[] newData=(E[]) new Object[newCapacity];
	    for (int i = 0; i < size; i++) {
			newData[i]=data[i];
		}
	    data=newData;
	}
		
	
}