之前，一直在談.NET框架方面的問題，今天來談談關於Array和List的使用問題，這應該 算是屬於算法的最基礎的東西了。只是提醒大家對這個問題稍加注意。
寫這個是因為一個同學的求助，事情是這樣的，他去負責公司的一個培訓模塊，在培訓模 塊中，有一個功能是自動成卷。然後，我們會很容易地想到洗牌算法。於是我給他大概解釋 了洗牌算法的過程和步驟，然後他給出了這樣的代碼，還很驕傲地告訴我，他使用了泛型… …
List<int> list = new List<int>();
for (int i = 0; i < 10; i++)
{
list.Add(i);
}
Random r = new Random();
for (int j = 0; j < 100; j++)
{
int temp;
int x1 = r.Next(10);
int x2 = r.Next(10);
temp = list[x1];
list[x1] = list[x2];
list[x2] = temp;
}
我委婉地告訴他，他這個方法不好，然後寫下了下面的代碼：
int[] array = new int[10];
for (int i = 0; i < 10; i++)
{
array[i] = i;
}
Random r = new Random();
for (int j = 0; j < 100; j++)
{
int temp;
int x1 = r.Next(10);
int x2 = r.Next(10);
temp = array[x1];
array[x1] = array[x2];
array[x2] = temp;
}
他很不屑地對我說，不是都一樣麼！而且還在以使用了泛型為豪！我無語……
我僅僅把List(鏈表)換成了Array(數組)，有人會說，這樣的關系大麼？
讓我們先來簡單地回顧一下基礎知識。
Array和List都屬於順序表。
Array是一段連續的存儲結構，如int[] i=new int[3]，i其實記錄的是數組的首地址，而 i[1]其實相當於在i的地址的基礎上加上1個整數的地址偏移，然後再取這塊地址中的值。也 就是相當於*(&i[0]+4);
而List則是不連續的存儲結構，List的每個節點都有著一個Next屬性，這個屬性則記錄著 他的下一個節點的地址。也就是說當我們想找第100個節點的時候，他還是需要從第一個節點 ，然後做99次Next操作，才能找到list[99]節點。這是個蠻痛苦的過程。
很多人會說，那無論是List還是Array，不都是一個索引麼！讓我們來請出IL:
先來看Array查找某個元素的IL:
IL_0020: ldloc.0
IL_0021: ldc.i4.3
IL_0022: ldelem.i4
IL_0023: stloc.2
然後讓我們來看下List查找某個元素的IL:
IL_0022: ldloc.0
IL_0023: ldc.i4.3
IL_0024: callvirt instance !0 class [mscorlib] System.Collections.Generic.List`1<int32>::get_Item(int32)
IL_0029: stloc.2
我們可以發現，雖然他們的寫法是一樣的，但是在IL中卻有著很大的差別。
通過這兩段IL，我只是希望證明List和Array對索引元素的方式是不同的。當然，我們無 從知道Microsoft對List方法get_Item的實現。但是我們不難想象：
因為List是一個鏈表，所以我需要從第一個元素開始逐個Next到所需索引的元素。這是一 個耗時的過程。
因此，在使用洗牌算法時，使用List是個很差勁的做法。再進一步說，當我們需要大量的 索引步驟時，使用List是個很差勁的做法。
那List和Array各自應該用在什麼情況下呢？我來做個簡單的總結：
1. 從空間擴展角度上來說：
數組必須要在初始化時分配固定的大小，比如說int[] a=new int[3];如果我們僅僅寫 int[] a=new int[];編譯器就會無情地給我們報錯。但是List由於空間不必連續，所以無須 指定初始大小。
總結1： 當不確定大小時，最好使用List代替Array。
2. 從操作角度上來看：
關於索引這個就不贅述了。
總結2：當需要大量的查找操作時，最好使用Array。
對於插入（刪除）操作，很多人是從插入（刪除）的時間上分析，說List優於Array，我 覺得是不合理的。
更合理的解釋應該是從兩個角度分析（以插入為例）：
<1> 指定位置插入指定元素：
對於Array講，有兩套解決方案：
A. 使用一個新數組，N+1個元素重新賦值的過程。一個for循環，時間復雜度O(n)。
B. 在原數組上操作，那麼首先需要為該數組預留空間，這是個很難辦的事情。而且其後 續元素的移動耗費時間復雜度仍未O(n)。
對於List來講，很多人說復雜度就是O(1)。這其實是不合理的，因為List插入元素固然容 易，但是在指定位置的插入，需要一個時間復雜度為O(n)的查找過程。
但是只考慮時間復雜度是不夠的，我們要考慮總體的情況。如果使用新數組，不僅浪費了 新的空間，而且需要反復的賦值過程，是N+1次。如果不使用新數組，預留空間實在太麻煩， 因此綜上所述，還是List好。
（補充下：很多同事和朋友都問我，說為什麼要學那麼多的排序和搜索算法，排序學個快 速排序，搜索學個二分搜索，這樣就夠了呗！但是我想說的是，所說的最快，不過是他們的 平均（或最壞）情況下的時間復雜度，並不能代表通用的情況，我們在實際工作中，還是要 根據實際情況去選擇最適用的算法，這就是我們學習很多算法的目的）
<2> 給出前一個節點，然後在後面插入元素。這個我的意思就是不僅僅給出了 PreviousNode的Value，還給出了他的Next。這個情況我就不廢話了，List的優勢太大了。可 是在實際情況中，這種情況的可能性幾乎為零。
因此，總結3：當需要進行頻繁的插入，刪除操作時，最好使用List代替Array。
另外，給出個不太重要的補充，由於List需要存儲他下一個節點的地址，所以List比 Array相對起來浪費了更多的空間。
這次關於List和Array的用法區別就先寫到這。希望大家有什麼不同意見的多多指教！
