資料結構——ArrayList

重新手動梳理一遍資料結構中的一些例程的實作。首先是ArrayList：

class Test {
	public static void main(String[] args) {
		MyArrayList<Integer> lst = new MyArrayList<Integer>();
		for (int i = 0; i < 10; i++)
			lst.add(i);
		for (int i = 20; i < 30; i++)
			lst.add(0, i);
		lst.remove(0);
		lst.remove(lst.size() - 1);
		System.out.println(lst);
	}
}

class MyArrayList<AnyType> implements Iterable<AnyType> {
	private static final int DEFAULT = 10;
	private int theSize;
	private AnyType[] theItems;

	public MyArrayList() {
		clear(); // 構造方法
	}

	public void clear() {
		theSize = 0;
		ensureCapacity(DEFAULT); // 清除同時改變大小
	}

	public void ensureCapacity(int newCapacity) { // 擴充容量
		if (newCapacity < theSize)
			return;
		AnyType[] old = theItems; // 存儲源數組的一個引用
		theItems = (AnyType[]) new Object[newCapacity]; // 為新數組配置設定記憶體，因不清除類型，引用超類型。（會産生警告，不可避免）
		for (int i = 0; i < size(); i++) {
			theItems[i] = old[i];
		}
	}

	public int size() {
		return theSize;
	}

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

	public void trimToSize() { // 将此ArrayList的執行個體容量調整為清單的目前大小。
		ensureCapacity(size());
	}

	public AnyType get(int idx) {
    if(idx<0 || idx>=size()) throw new ArrayIndexOutOfBoundsException();
    return theItems[idx];
}

	public AnyType set(int idx, AnyType newVal) {	//注意傳回類型。
    if(idx<0 || idx>=size()) throw new ArrayIndexOutOfBoundsException();
    AnyType old = theItems[idx];
    theItems[idx] = newVal;
    return old;		//傳回的是位于該位置上元素。
}

	public boolean add(AnyType x) { // 添加到表的末端
		add(size(),x);
		return true;
	}

	public void add(int idx, AnyType x) { // 添加到指定位置，add方法要求增加容量，如擴充容量，它就要變成原來大小的兩倍，以便面不得不再次改變。
		if (theItems.length == size())
			ensureCapacity(size() * 2 + 1); // +1用來表示防止大小是0的情況。
		for (int i = theSize; i > idx; i--) {
			theItems[i] = theItems[i - 1];
		}
		theItems[idx] = x;
		theSize++;
	}

	public AnyType remove(int idx) { // 删除操作，位于指定上或指定位置後的元素向低位移動一個。
		AnyType removeItem = theItems[idx];
		for (int i = idx; i < size() - 1; i++)
			theItems[i] = theItems[i + 1];
		theSize--;
		return removeItem;
	}

	public java.util.Iterator<AnyType> iterator() { // 該方法傳回一個ArrayListIterator類的一個執行個體
		return new ArrayListIterator();
	}

	private class ArrayListIterator implements java.util.Iterator<AnyType> { // 存儲目前位置，目前位置即要被檢視的下一進制素（的數組下标）
		private int current = 0;
		private boolean ok = false;

		public boolean hasNext() {
			return current < size();
		}

		public AnyType next() {
			if (!hasNext())
				throw new java.util.NoSuchElementException();
			ok = true;
			return theItems[current++];
		}

		public void remove() {
			if (!ok)
				throw new IllegalStateException();
			MyArrayList.this.remove(--current);
			ok = false;
		}
	}

	// 這裡說明一下，ArrayListIterator是内部類，private可見性是為了隻能讓其外部内通路。
	// 删除調用的是MyArrayList的remove來實作疊代器的remove方法，原因是避免remove可能與MyArrayList的remove沖突。

	public String toString() {
		StringBuilder sb = new StringBuilder("[");
		for (AnyType x : this)
			sb.append(x + " ");
		sb.append("]");
		return new String(sb);
	}
	// 這裡不得不說一下String，StringBuffer和StringBuilder的差別了，其實說起來挺多，總結起來就是：
	// 1）String是不可變的對象，每次對String類型進行改變的時候都等同于生成了一個新的String對象，
	// 然後将指針指向新的對象，是以經常改變的字元串最好不要用String，因為每次生成對象都會算上産生一次垃圾，GC收集起來麻煩。
	// 2）StringBuffer則是對對象本身進行操作，是可變的。
	// 3）StringBuilder是jdk1.5之後新增加的，它是支援單線程的，StringBuffer則可以支援多線程，它可以處理同步問題。
}
           

OK。搞完了。準備下一個。