Java实现ArrayList

package adt.array;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 
 * @author 数据结构与算法分析
 * @param <T>  AnyType T 任何类型
 */
public class MyArrayList<T> implements Iterable<T>{

	//集合初识长度
	private static final int DEFAULT_CAPACITY = 10;
	
	//当前List数据长度
	private int theSize;
	
	//底层数组集合
	private T[] theItems;
	
	//长度
	public int size() {
		return theSize;
	}
	
	//List判空
	public boolean isEmpty() {
		return size() == 0;
	}
	
	/***
	 * 扩充长度
	 */
	public void trimToSize() {
		ensureCapacity(size());
	}
	
	/***
	 *根据下标获取数据，如果下标为负数或大于当前数组长度，抛出数组越界异常。
	 * @param idx
	 * @return 
	 */
	public T get(int idx) {
		if(idx < 0 || idx >= size()) {
			throw new ArrayIndexOutOfBoundsException();
		}
		return theItems[ idx ];
	}
	
	//初始化
	public  MyArrayList() {
			doClear();
	}
	
	//清除长度，将当前集合长度变为初始值
	private void doClear() {
		theSize = 0;
		ensureCapacity(DEFAULT_CAPACITY);
	}
	
	
	/***
	 * 如果当前需要扩充的长度小于当前数组长度，那么程序将不往下执行
	 * 否则获取当前数组，创造新的数组，新的数组长度根据newCapacity进行初始化，
	 * 然后将旧的数组赋给新的数组
	 * @param newCapacity
	 */
	@SuppressWarnings("unchecked")
	private void ensureCapacity(int newCapacity) {
		if(newCapacity < theSize)
			return;
		
		T[] old = theItems;
		
		theItems = (T []) new Object[ newCapacity ];
		for(int i = 0; i < size(); i++)
			theItems[i] = old[i];
	}

	//清空集合
	public void clear() {
		doClear();
	}
	
	/**
	 * 更新数据，根据下标，判断下标是否越界，接着根据下标获取当前下标的数据进行覆盖
	 * @param idx
	 * @param newVal
	 * @return
	 */
	public T set(int idx, T newVal) {
		if(idx < 0 || idx >= size()) {
			throw new ArrayIndexOutOfBoundsException();
		}
		T old = theItems[ idx ];
		theItems[idx] = newVal;
		return old;
	}
	
	//添加一个数据，在最后
	public boolean add(T x) {
		add(size(), x);
		return true;
	}
	
	/**
	 * 在上一个add方法中将数组长度传入，如果当前长度满了，那么扩充一倍(+1用于大小是0的情况)
	 * 接着将所有数据向后移一位，将输入插入到第一位index0，长度自增。
	 * @param idx
	 * @param x
	 */
	public void add(int idx,T x) {
		
		if(theItems.length == size()) 
			ensureCapacity(size()*2+1);
		
		for(int i = theSize; i > idx; i--)
			theItems[i] = theItems[i-1];
		
		theItems[idx] = x;
		
		theSize++;
	}
	
	/**
	 * 都差不多
	 * @param idx
	 * @return
	 */
	public T remove(int idx) {
		T removeItem = theItems[idx];
		for(int i = idx; i < size() -1; i++)
			theItems[ i ] = theItems[ i +1 ];
		
		theSize--;
		return removeItem;
	}
	
	//实现迭代器
	@Override
	public Iterator<T> iterator() {
		return new ArrayListIterator();
	}
	
	//具体实现
	private class ArrayListIterator implements Iterator<T>{

		private int current = 0;
		
		@Override
		public boolean hasNext() {
			return current < size();
		}

		@Override
		public T next() {
			if(!hasNext())
				throw new NoSuchElementException();
			return theItems[current ++];
		}
		
		public void remove() {
			MyArrayList.this.remove(-- current);
		}
	}
	
	
	
}
package adt.array;