简单模拟Java中的ArrayList

Java中的ArrayList是用数组实现的。
数组是有界的,因此实现最重要的是数组的扩容机制。
扩容机制:

当要存的数据大于数组大小时,会扩容。
在JDK1.8中,会创建一个新数组,新数组大小为原数组的1.5倍,并将原数组复制到该新数组中。

可以发现,扩容过程会消耗大量的时间、空间,应当尽量避免数组扩容。因此在创建ArrayList时,确定一个合适的初始数组大小是很有必要的。


下面是简单的模拟

public class MyArrayList {
	private static final int DEFAULT_CAPACITY = 10;
	private Object[] elementData;
	private int size;

	public MyArrayList() {
		this(DEFAULT_CAPACITY);
	}

	public MyArrayList(int initialCapacity) {
		if (initialCapacity < 0) {
			try {
				throw new Exception();
			} catch (Exception e) {
				e.printStackTrace();
			}
		}

		elementData = new Object[initialCapacity];
	}

	public int size() {
		return this.size;
	}

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

	public void add(Object obj) {
		ensureCapacity();

		elementData[size++] = obj;
	}

	public void add(int index, Object obj) {
		RangeCheckByAdd(index); // add的check不同,add可以在数组尾部添加,所以可以不加=
		ensureCapacity();

		System.arraycopy(elementData, index, elementData, index + 1, size - index);
		elementData[index] = obj;
		size++;
	}

	public Object set(int index, Object obj) {
		RangeCheck(index);

		Object oldValue = elementData[index];
		elementData[index] = obj;
		return oldValue;
	}

	public Object get(int index) {
		RangeCheck(index);

		return this.elementData[index];
	}

	public Object remove(int index) {
		RangeCheck(index);

		Object oldValue = elementData[index];
		int numMoved = size - index - 1;
		if (numMoved > 0)
			System.arraycopy(elementData, index + 1, elementData, index, numMoved);
		elementData[--size] = null;
		return oldValue;
	}

	public boolean remove(Object obj) {
		if (obj == null) {
			for (int i = 0; i < size; i++) {
				if (elementData[i] == null) {
					remove(i);
				}
			}
		} else {
			for (int i = 0; i < size; i++) {
				if (elementData[i].equals(obj)) {
					remove(i);
				}
			}
		}
		return true;
	}

	public void clear() {
		for (int i = 0; i < size; i++) {
			elementData[i] = null;
		}
		size = 0;
	}

	/**
	 * 判断是否达到容量上限==》扩容 ArrayList扩容大小:原数组的1.5倍 扩容原理:创建新数组,将原数组复制过来 本方法未考虑超过int表示范围情况
	 */
	private void ensureCapacity() {
		if (size == elementData.length) {
			Object[] newArray = new Object[size + (size >> 1)];
			System.arraycopy(elementData, 0, newArray, 0, elementData.length);
			elementData = newArray;
		}
	}

	/**
	 * 判断操作位是否越界 index表示操作位,从0开始,最大为size-1
	 * 
	 * @param index
	 */
	private void RangeCheck(int index) {
		if (index >= size || index < 0) {
			try {
				throw new Exception();
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
	}

	/**
	 * 判断操作位是否越界(add) add的越界判断不同。add可以在数组尾部添加,所以index和size相等的情况是可以接受的
	 * 
	 * @param index
	 */
	private void RangeCheckByAdd(int index) {
		if (index > size || index < 0) {
			try {
				throw new Exception();
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
	}

	public static void main(String[] args) {
		MyArrayList list = new MyArrayList();

		list.add(111);
		list.add(222);
		list.add(333);
		list.add(444);

		print(list);
	}

	public static void print(MyArrayList list) {
		for (int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}
	}
}