阿猩的程式蛋糕店

聚沙成塔 - 資料結構大家族

當資料量增加至一定規模以上時，就需要整併資料，然後收納在同一個地方，方便後續查詢或更改，例如成績單、電話聯絡人清單等。在程式語言的世界裡，稱之為資料結構，例如常聽到的陣列(Array)、列表(list)等、字典(dictionary)等等。他們有部份的基因是相同的，長的有點像，卻又有點不像，可依據程式的需求考量、安全性等因素，決定要使用哪種資料結構料，聽起來還是很抽象對吧，沒關係！我們就逐個介紹，希望可以幫助大家對於資料結構有初步的認識。

MSDN 提供了C# - Collections的說明，裡面列出一些常見的類別

• ArrayList
• Hashtable
• Queue
• Stack

看完敘述….真是簡潔有力，ArrayList看起來比較親切些，我們就從ArrayList做為study的出發點吧。

 

Array、List、ArrayList 傻傻分不清楚

參考了很多資料後，我決定使用條列式的方法整理他們的屬性，包含C#語法、簡單特性說明、優缺點，也會延伸到泛型的概念。另外，因為看到各式各樣奇怪的名字組合，為避免誤人子弟，後續我都直接用英文稱呼。

Array

1. Array會儲存資料在連續的記憶體位置上，故初始化Array時就必須指定儲存空間的長度，利於查詢及修改資料。過長會浪費記憶體，過短則會資料溢位。記憶體空間使用較精準，但當需要存放在Array的資料量有很多的時候，可能會被切成好幾塊較小的連續的記憶體位置。
2. 搜尋某筆資料的時間複雜度為O(N)。
3. Array要實現新增或刪除，必須初始化一個新的Array，資料轉移後再刪除舊的Array，時間複雜度為O(N)。此外，連續的記憶體位置特性，對於排序也不太友善。
4. 在C#中，Array必須指定單一資料型別。
5. 可多維，可設下限。

using system                                  //參考C#內建的物件
int[] array1 = new int[] { 1, 3, 5, 7, 9 };   //初始化array


//或是
int[] array1 = new int[5];
array1[0] = 1;   
array1[1] = 3;
array1[2] = 5;
array1[3] = 7;
array1[4] = 9;

ArrayList
Array必須指定資料型別，情境想像一下，假設我們有學生姓名、成績、平均等資訊，至少就需要string、int、double三種資料型別，看到這裡，你是否能隱約猜到ArrayList的才能了?

1. ArrayList支持儲存空間動態增長，簡單說，就是初始化不用給長度。超過長度時就自動增加長度。實現概念大概會像是: 預設儲存空間為10，有12筆資料，當判定儲存空間不足時，就會觸發增長機制。增加長度的公式可能像: 原長度 * 1.5 = 15。因為是由固定公式試算，所以無法以資料筆數準確的新增儲存空間，例如我舉的例子，就會多建立3個空間，會比Array會更浪費記憶體的空間。
2. 搜尋的時間複雜度是O(N)。
3. ArrayList保有Array使用連續的記憶體位置的屬性，對新增與刪除而言，一樣需要(1)初始化新Array、(2)資料轉移、(3)刪除舊Array，故時間複雜度為O(N)。
4. 在C#中，ArrayList儲存的方式為Object，可儲存不同的資料型別，但也因此而衍生出裝拆箱的效率問題、型別不匹配的安全問題。
5.  一維，下限只能是0。

在C#中，ArrayList的指令會像這樣:

using system.Collections                          
ArrayList table = new ArrayList();    

//插入資料，可放不同資料型別
table.Add(1);
table.Add("Hello");
table.Add(87.78);
table.Add("World");

for (int i = 0; i < table.Count; i++)
{
    Console.WriteLine(table[i]);
}

//在indext為3的地方插入"test"
table.Insert(3, "test"); 
Console.WriteLine("====================");

for (int i = 0; i < table.Count; i++)
{
    Console.WriteLine(table[i]);
}

/*輸出結果
1
Hello
87.78
World
====================
1
Hello
87.78
test
World
*/

/*
其他功能:
Remove()
Reverse()
Sort()
Clone()
...
*/

Linked List
以下為Linked List的特性介紹，但我不確定在C#中，List是如何實現的。​

1. Linked List以node的方式儲存資料，node中會包含data及Pointer的訊息，Pointer用於記錄下一筆data存放的記憶體位址。搜尋某資料時，Linked List只公開第一個node，透過第一個node裡面的Pointer，對應找到下一個node，以此類推直到某筆資料的位址，故不需要連續的記憶體位置，但需要額外的記憶體空間儲存pointer。
2. 搜尋的時間複雜度是O(N)。
3. Linked List要新增、刪除時，只要先找到對應的Index，並調整後續受影響的node中的Pointer即可，但Array、ArrayList要以全部的長度，建立或調整儲存空間，。
4. 在C#中，初始化List須指定資料型別，因此安全性較高。

在C#中，List的指令會像這樣:

using system.Collections.Generic                          
List<string> list = new List<string>();

//加入資料，注意!!!只能放單一資料型別阿!!!!所以這裡全部都是string
list.Add("1");
list.Add("Hello");
list.Add("78.87");
list.Add("Wolrd");

foreach (string s in list)
{
    Console.WriteLine(s);
}

list.Reverse();
Console.WriteLine("========================");

foreach (string s in list)
{
    Console.WriteLine(s);
}

/*
結果顯示
1
Hello
78.87
Wolrd
========================
Wolrd
78.87
Hello
1
*/

/*
其他功能:
RemoveAt(in)
Reverse()
Sort()
ToArray()
.....
*/

單就工作的功能而言，Array、List、ArrayList其實不少功能是重疊的，所以我的感覺是，重點應該放在特性的差異上，才能選擇合適的時機出場。例如:只用查詢、修改時，Array絕對是首選，要查詢、修改，但希望能有不同資料型別，例如成績單中會有姓名與成績，成績又分成int與double，ArrayList會是不錯的考量，對於資料量不固定的情況，例如儲存目前客戶端登入的資訊，List可能首選，組合使用可能類似，初期先用List建立表單，後續有別用需求，例如查詢或想省記憶體，可以再考慮轉換成Array之類的。

 

其他的資料結構

讓人感到無法親近的Queue、Stack、Hash Tabel，其實他們像是一種概念，用來設計不同的資料結構，透過Array或List都可以實現。

Queue
Linked List只公開第一個node，找到pointer為null的時候就判定為結束。假設要找最後一筆資料時，必須從第一筆資料開始直到最後。Queue新增了back pointer，可快速的在資料的末端進行新增或刪除。另外，先進先出是最核心的概念，常用於被多個程式分享的資源，例如多台電腦連同一台印表機，但多人列印時卻不會錯亂。

Stack
使用指標記錄Top的資料，無法得知更之前的資料或狀態。如果要查看更之前的資料，必須逐個取出，跟Linked List的node概念有點像，例如瀏覽器的上一頁、或是在編輯文字時，不小心修改到，想恢復上一個狀態時，會使用undo，或使用快捷鍵Ctrl + z。最核心的概念跟Queue相反，為後進先出。

Hash Table
前面提到的都是值的結構關係，這裡出現鍵與值的觀念，例如得知一個人的身分證字號，就該知道他的姓名，Dict就在鍵與值的概念下出現囉。Hash Tabel又稱雜湊表，就是用來儲存鍵值關係的資料結構。鍵與值連結的實現概念是，透過某種方式(Hash Function)轉換，例如以Key鍵的字元，換成ASCII、或UniCode再相加，輸出結果作為Hash鍵，並在一個的陣列存放對應的值。但有可能不同Key值，經轉換後結果卻是相同的(collision)，解決collision問題又是另外一門學問囉。