什麼是 泛型 ?

什麼是 泛型 ?
　
　泛型（C++叫template，Java和.NET Framework叫Generic）
在以前還沒有泛型這個東西之前，所有的程式都是和資料型別綁在一起的，也就是說，不同的資料型別就算邏輯一樣也要寫成不一樣的程式（如果不用的話，算是運氣好），泛型的目的就是把這塊抽象化，只把邏輯寫下來， 資料型別當作參數傳進去就可以了
　
　
其實沒有泛型也不是不行，只要有個通用的型別就可以，像C/C++的void*或Java/.NET Framework的object，不過還要做資料型別轉換，速度會比較慢，而且型別不對要到執行時期才會知道，例如進去的資料是文字，出來卻強迫轉成數字之類的bug。
　
　
1. Array<T>： 陣列，起始化後長度固定，不可增刪任何元素。搜尋指定位置元素的時間：O(1)。
　
2. List<T>： 在.NET Framework裡其實是動態陣列，比較接近教科書上定義的List的資料結構是LinkedList<T>。增加一個元素在指定位置的時間成本：O(n)，如果加在尾巴則是O(1)，如果需要重新配置記憶體是O(n)；刪除一個指定位置元素的時間：O(n)；搜尋指定位置元素的時間：O(1)（所以很明顯是用陣列的方式實作）；搜尋某特定元素位置所需時間：liear search，所以是O(n)；刪除一個指定元素的時間：O(n)。 這個算是我最常用的，彈性夠大，只要不要搜尋特定的資料和刪除，效能相當好，尤其是對每個資料要做相同處理的時候，List<T>算是首選（其實Array<T>會快一點點，但是長度不能增減，有時候很麻煩）。
　
3. SynchronizedCollection<T>： 是List<T>的一個變形，唯一差別是thread safe。不過MSDN上面有人不太同意這個說法。沒用過，不知道。
　
4. LinkedList<T>： 鏈結串列。.NET Framework的實作是雙向鏈結。增加一個元素在指定位置的時間：O(1)；刪除一個指定位置元素的時間：O(1)；搜尋某特定元素位置所需時間：liear search，O(n)。缺點：要把資料包裝成LinkListNode<T> ==> 要比較多記憶體。
　
5. Stack<T>： 堆疊。先放進去的資料後拿出來。增加一個元素的時間：O(1)（只能加在尾巴）；刪除一個元素的時間：O(1)（只能刪掉尾巴那一個）；不可搜尋。
　
6. Queue<T>： 貯列。先放進去的資料先拿出來。增加一個元素的時間：O(1)（只能加在尾巴）；刪除一個元素的時間：O(1)（只能刪掉最前面那一個）；不可搜尋。
　
7. Dictionary<S,T>： 是STL的Map，實際上是Hash table，利用S型別做索引存取T型別。增加一個元素的時間：O(1)；刪除一個元素的時間：O(1)；指定索引值搜尋元素的時間：O(1)。
　
8. HashSet<T>： 在.NET Framework 3.5以後加入，還是一個Hash table，但是沒辦法用索引值直接存取，主要用於集合運算。增加一個元素的時間：O(1)；刪除一個元素的時間：O(1)；無法直接存取資料，只能用Enumerator。如果一堆資料有需要刪除的動作，我會選這個資料結構，比List<T>快得多。
　
9. SortedList<S,T>： 顧名思義，是個排序過的List，內部基本上是個binary tree，以S型別為索引值。增加一個元素的時間：O(n)，如果加在尾巴則是O(log(n))，如果需要重新配置記憶體是O(n)，O(log(n))其實很容易理解，最佳的排序法能做到的也不過就是O(n log(n))，每一個元素剛好分到O(log(n))　；刪除一個指定位置元素的時間：O(n)；刪除一個指定元素的時間：O(n)；搜尋指定元素的時間：O(log(n))（binary search）。
　
10. SortedDictionary<S,T>：. NET Framework 2.0後加入，還是個binary tree，以S型別為索引值。增加一個元素的時間：O(log(n))；刪除一個指定位置元素的時間：O(log(n))；刪除一個指定元素的時間：O(log(n))；搜尋指定元素的時間：O(log(n))（binary search）。沒有非泛型，原因是沒必要，泛型是.NET Framework 2.0版後的功能。
　
　
　
　時間複雜度
簡單地說，O(.)代表的是當資料量很大的時候，在最不好的情況下，運算次數（假設每次運算都一樣的話，運算次數就是運算所需的時間）和資料量n的關係。最棒的當然是O(1)，代表運算次數和資料量多少無關，有最好的scalability；最糟的大概就是O(2^n)或是O(n!)這類恐怖的東西。不過平平是O(1)，速度還是有可能差到好幾百倍，因為O(1)表示的只是和資料量多少無關而已。像LinkedList<T>的增加元素和搜尋就會比List<T>來得慢一點，原因是在絕大多數的情況下List<T>所佔的記憶體是連續的，新增元素時亦不用配置新的記憶體。