這章節來探討AList，array list的意思。

首先提到當我們要使用get(index)從list中拿出元素時，SLList就會比AList慢，因為SLList的結構會需要從各個node開始慢慢去追尋到目標index的node；而AList因為有紀錄index，所以不管list長度有多長，都可以瞬間提取出目標index的元素。

再來提到removeLast：

public class AList{
	int[] items;
	int size;

	public AList(){
		items = new int[100];
		size = 0;
	}
	
	public void addLast(int item){
		items[size] = item;
		size += 1;
	}

	public int getLast(){
		return items[size - 1];
	}
	
	public int removeLast(){
		int lastItem = getLast();
		// items[size - 1] = 0;
	  size -= 1;
	  return lastItem;
  }
}

直覺上會認為既然要remove那應該真的去做items[size - 1] = 0這行，真的把最後一個元素消滅掉，但其實還有另一種做法，就是改變size即可。

因為我們有用AList包裹起來，裏頭的操作只要能符合使用AList的期待就行；這代表說我們在removeLast的時候其實只要更改size就好了，不用真的把最後一個元素從items中消滅掉，因為我們的addLast或者getLast其實也都是透過size來操作的。

接著就是重頭戲了，因為array的特性勢必得在初始化的時候指定一個長度，當我們要塞進的元素數量超過初始化長度該如何處理呢？

其實也沒有什麼神奇的做法，就是必須得在碰到邊界值時把array加大。所以接著該討論的問題是，我們可以有哪些加大的策略？

首先第一個方法是直接把長度加倍，這也是python的做法：

public class AList{
...
	public void addLast(int item){
			if(size == items.length){
				int[] temp = new int[size * 2];
				System.arraycopy(items, 0, temp, 0, size);
				items = temp;
			}
			items[size] = item;
			size += 1;
	}
...
}

但是這樣還是會有個問題，就是記憶體上的空間有點浪費，假設我們一口氣add了100萬的元素，接著又刪除了90萬個元素，就變成有閒置的90萬個空間佔在那邊。這時就需要去考量usage ratio的問題：

R = size / items.length

size是實際儲存了多少個元素，items.length是array佔了多少記憶體空間。有個經驗法則是說當

R < 0.25時，那就要把items減半。

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License