資料結構 (data structure) 是資料的組成方式，資料可以是字串或是二進位資料 (binary data)，組成方式則要看不同資料整理的需求，可以是分布在記憶體不同位置，然後用特定方法管理，或是以特別的格式排列組合，以達成有效率管理資料的方式，而一般程式設計人員接觸到最多的是資料結構，因為這會決定你在程式中處理資料的方式，簡單的資料當然可以用很簡單的結構來組織，但是如果在寫程式時不在乎資料結構的話，很容易發生寫出的程式效率低落的問題。
只要是資訊類科系出身的，多少都會聽過一句話：程式 = 資料結構 + 演算法，若你是非科班出身，那我現在已經講給你聽了。
演算法 (algorithm) 是一組指令的集合，這些指令可以構成一個完整且有效率的流程，並且解決特定的科學或技術問題。演算法通常是由專精於離散數學以及演算法設計的高級資訊工程專家 (ex: 數學，資訊類博士或是具有演算法設計能力的專才) 所設計，且經過驗證可以在有限時間內完成演算或資料處理的工作。
而資料結構 (data structure) 則是資料的組成方式，資料可以是字串或是二進位資料 (binary data)，組成方式則要看不同資料整理的需求，可以是分布在記憶體不同位置，然後用特定方法管理，或是以特別的格式排列組合，以達成有效率管理資料的方式，而一般程式設計人員接觸到最多的是資料結構，因為這會決定你在程式中處理資料的方式，簡單的資料當然可以用很簡單的結構來組織，但是如果在寫程式時不在乎資料結構的話，很容易發生寫出的程式效率低落的問題，最顯著的有：
1. 排序一千筆資料，但速度總是很慢。
2. 搜尋 100,000 筆資料要花很久時間。
3. 寫錯排序的方法，讓排序的時間超過預期。
善用資料結構可以做到的最顯著改善，或是誤用 (或不使用) 資料結構的程式的顯著問題，就是時間。因為良好的資料結構通常都是已經使用特別設計過的演算法 (針對資料組織方式) 所組成，這些演算法都可以讓資料組織與處理的時間控制在有限時間內，以演算法的時間度量來說，一個設計良好的演算法可以在不限資料個數的情況下，將時間控制在 O(n) 或 O(logn) 內，以排序演算法來說，不同做法的演算法所產生的效率不同，有最好 (best)，最差 (worst) 和平均 (average) 三種，例如以快速排序法 (Quick Sort) 來說，最好和平均時間是 O(nlogn)，但最差是 n^2 (n的平方)，但合併排序法可以控制在三種都是 O(nlogn)，故即便實作方式很相似的演算法，都有可能因為某個條件的不同導致時間效率的差異。
註 2. 演算法還有一個空間複雜度 (space complexity)，但以記憶體和硬碟空間與價格比愈來愈大 (即愈便宜) 的情況來說，空間複雜度相較時間複雜度而言，較不會受重視，甚至會有拿空間來換時間的情況。
另外，資料結構也會限制你使用資料的方式 (包含常見的 FIFO/LIFO)，最常見的資料管理方式是鍵值對 (key-value pair)，例如我們在 .NET Framework 中使用的 Dictionary<Tkey, Tvalue>，就是典型的鍵值對，每筆資料會以一個鍵 (key) 做索引 (key 不可重覆) 以及可有可無的數值 (value) 為一組，在搜尋時會以 key 為基礎，而取值時則是由 key 來取出。由此可知：
- 在 Dictionary<Tkey, Tvalue>，Count > Capability 的情況下，插入資料的時間是 O(1)，否則它會複製一份資料並加長 Capability，此時需要的時間是 O(n)，n 為插入資料時的資料個數。
- 在 Dictionary<Tkey, Tvalue>中刪除資料的時間是 O(1)。
- 在 Dictionary<Tkey, Tvalue>使用鍵值搜尋時 (不論是用 ContainsKey 判斷或是用 [] 取值)，時間為 O(1)。
- 在 Dictionary<Tkey, Tvalue>中使用 ContainsValue() 判斷時，時間為 O(n)，所以應避免使用這個函數。
- Dictionary<Tkey, Tvalue> 中沒有排序功能，要排序需改用 SortedDictionary 或複製 key 出來排序。
再舉個例，我們常見的 List<T>，則是單一資料的集合物件，資料不可以是 null 或 Nothing (Dictionary 則是 key 一定要有值，但 value 可以是 null 或 Nothing)，搜尋和排序時則是以資料值來比對，由此可知：
- 在 List<T>，Count > Capability 的情況下，插入資料的時間是 O(1)，否則它會複製一份資料並加長 Capability，此時需要的時間是 O(n)，n 為插入資料時的資料個數。
- 在 List<T>中刪除資料的時間是 O(n)，因為是線性搜尋 (linear search)。
- 在 List<T>使用鍵值搜尋時，時間為 O(n)。
- 在 List<T>中使用 Contains() 判斷時，時間為 O(n)。
- List<T> 中呼叫 Sort() 排序時，有可能會發生 O(n^2) 的最差情況，平均時間是 O(nlogn)。
以上面的兩個例子來說，當資料有 1,000,000 筆，假設每筆資料巡覽的時間是 0.001ms，現在要搜尋其中一筆資料，則以 List<T> 而言，需要 1 秒才跑的完，但使用 Dictionary<Tkey, Tvalue> 跑，則只要 0.001ms (近乎即時)。
速度相差了 1,000,000 倍！
至於 List<T>.Sort() 的效能差，可以使用針對這個部份最佳化的集合來做替代，.NET Framework 有一個 SortedList<Tkey, Tvalue>，它可以在資料插入時自動進行排序，雖然它會在插入時花費 O(n) 的時間運算，但卻可以保證完成後的值是已排序的值。
由以上的討論可以了解，在寫程式時選用正確的資料結構，可以大幅加速處理資料處理的時間，在這再舉一個例子，我們以前常在用 ADO.NET 的 DataTable 來管理自己的資料，因為它可以使用 DataRow 在單一資料列中容納多種資料，以及具有彙總能力，但 DataTable.Select() 和 DataTable.Compute() 的效能如何？其實遠不如 Dictionary<Tkey, Tvalue>，以一百萬筆的資料而言，Dictionary<Tkey, Tvalue> 的搜尋只要 48 ticks (幾乎即時)，但 DataTable 要 29,753,787 ticks (相當於 2 秒鐘)。
在 .NET Framework 文件中，有一個章節特別有提到在 .NET Framework 中所有資料結構 (集合物件) 的使用方法，只要是 .NET 的開發人員都應該要讀熟它。這裡有一篇寫的很棒的 .NET 資料結構說明，寫的應該比我這裡舉例的還清楚，想看 code demo 的可參考那一篇文章。
至於還有哪些資料結構你必須要知道的，我們待下回分解。
(如有錯誤，歡迎指正)
Reference:
.NET Framework Collections: http://msdn.microsoft.com/zh-tw/library/7y3x785f.aspx