大家一開始學習程式語言的時候，一定會學到陣列(array)，array有一個蘿蔔一個坑的特性，透過每個坑的index來控制讀取與寫入：

int[] array = new int[10];
for(int i = 0; i < 10; i++){
    array[i] = i + 1;
}
int num01 = array[0]; // you will get 1 in num01

array[10] = 11; // you'll get ArrayIndexOutOfBoundsException
int num11 = array[10]; // you'll get ArrayIndexOutOfBoundsException

陣列最致命的缺點就是你必須一開始就定義出一個長度，如果有超過此長度的需求時，很抱歉，你就得額外加大，才能繼續做事。

如果你是寫Java的可能會想說，那就用ArrayList呀：

List<Integer> list = new ArrayList<>();
for(int i = 0; i < 10; i++){
    list.add(i + 1);
}
int num01 = list.get(0); // you'll get 1 in num01;

list.add(10) = 11;
int num11 = list.get(10); // you'll get 11 successfully

貌似不用宣告初始長度，但其實Java背地裡幫你宣告了10為初始長度，並在ArrayList裝滿後會自動偵測到並增加長度。(關於如何增加長度會在後續的AList章節探討)

有沒有可能解決這個限制呢？那就是LinkedList的概念了，不過這邊我們要自己想辦法手刻一個LinkedList出來。為了方便，我們先只讓這個List儲存Integer型別的元素，所以簡稱IntList：

public class IntList{
	int first;
	IntList next;

	public IntList(int f, IntList r){
		first = f;
		next = r;
	}

}

每一個物件IntList會儲存當前的int元素，這邊命名為first變數；然後後續的元素就再用另一個IntList儲存，所以當我們把下一個IntList拿出來時，也會有一個first變數代表當前的int，然後又會有下一串IntList，如此就達成了不需要先定義長度的List實作。

再來我們實作出如get, size等方法：

public class IntList{
	int first;
	IntList next;

	public IntList(int f, IntList r){
		first = f;
		next = r;
	}
	
	public int size(){
		if(next == null){
			return 1;
		}
		return 1 + next.size();
	}
	
	public int get(int i){
		if(i == 0){
			return first;
		}
		return next.get(i - 1);
	}
	
}

LinkedList的結構很適合使用遞迴(Recursion)的方式優雅地實作，可以看到以上的code彷彿是咒語般，短短的但是裡面蘊藏著無窮無盡的可能。

Recursion對於一開始接觸的人會覺得有點難想像，不過老師提供了一個訣竅，就是先想想最後一步會長什麼樣子？以此為基礎後，再去想下一步的衍生條件並回call。

就像上面的例子，會先有if statement來定義當最後一步時會是什麼情況，通常這一步想到後，回call的條件通常不難想到。

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