.NET，你忘記了麼？（三）——關于Array和List的使用

系列文章目錄索引：《.NET，你忘記了麼》

之前，一直在談.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<T>的了解大錯特錯，在成文前，首先做下自我批評，然後也對造成的不良影響表示道歉。

首先開始的就是對List的重新認知。在這裡，讓我們先從構造方法來重新認識List<T>的本質，先來看下上文中我所粘出的代碼：

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;
}      

在上文中，我對這個List大批特批，現在，我們來重新看下這個List的構造：      

public List()
{
    this._items = List<T>._emptyArray;
}      

先來看無參的構造方法，當無參的時候，.NET Framework其實是用一個_emptyArray來初始化了List中的items集合。那麼_emptyArray又是什麼呢？我們繼續向下看：

private static T[] _emptyArray;      

恩，他是一個靜态字段，然後我們看下List<T>的靜态構造方法：

static List()
{
    List<T>._emptyArray = new T[0];
}      

我們看到，_emptyArray其實是一個T類型的數組，個數為0。那麼也就是說，當我們執行0參數的構造方法時，系統是把items集合給指派為了一個T類型的個數為0的數組。

那麼items又是什麼？我們繼續向下看：

public void Add(T item)
{
    if (this._size == this._items.Length)
    {
        this.EnsureCapacity(this._size + 1);
    }
    this._items[this._size++] = item;
    this._version++;
}      

這是List<T>中一個Add(T item)方法，但是我們可以從方法中敲出些端倪來。

在這裡，我并不是想解釋這個方法的原理，隻是想說，在List中，其實維護這一個items，然後很多操作，是基于items的操作。

恩，是以在上文中，List<int> list=new List<int>();和Array a=new int[10]();的操作其實差别并不大。

我們肯定還記得在《Effective C#》中有這樣一條規則，就是說：在初始化List之前最好對List初始化大小。

讓我們從源碼中來找到這一條規則的答案。

private void EnsureCapacity(int min)
{
    if (this._items.Length < min)
    {
        int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2);
        if (num < min)
        {
            num = min;
        }
        this.Capacity = num;
    }
}      

我們來看，在這個方法體中，List會建立一個數組，然後把數組的長度設定為原來的二倍（如果原有的數組長度為0，那就預設将數組的長度設定為4）。

是以，這種，讓List的方法自己去調用EnsureCapacity(int min)方法，不僅浪費了構造數組的時間，還浪費了大量的空間（因為将原有的數組空間擴充了二倍）。

是以，請記得：在初始化List之前最好指定List的大小。

為了證明上述的觀點，我們再來随便看一些代碼：

public int IndexOf(T item)
{
    return Array.IndexOf<T>(this._items, item, 0, this._size);
}      

public int FindIndex(int startIndex, int count, Predicate<T> match)
{
    if (startIndex > this._size)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
    }
    if ((count < 0) || (startIndex > (this._size - count)))
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
    }
    if (match == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
    }
    int num = startIndex + count;
    for (int i = startIndex; i < num; i++)
    {
        if (match(this._items[i]))
        {
            return i;
        }
    }
    return -1;
}      

由上面的代碼，我想證明的是：其實List<T>不過是對Array的進一步封裝，說得再直接點，我願意了解List<T>為Array的可擴充版本，然後擴充了一些方法;

那關于Array和List的選擇，我重新做一個說明：

List是基于Array存在的，是以，在建立一個List對象時，需要耗費比Array相對更多的時間，以及更大的空間，因為List除了初始化内部的items外還需要初始化一些其他的屬性。而且在方法調用時，這點我沒有證明，隻是一個猜測，List需要的是再去調用Array的相關方法，是以也許會存在方法調用的時間消耗問題。

是以，我的建議是：

如果初始化時确定大小，那麼就使用Array。

如果初始化時不确定大小，那麼就使用List。當然，其實完全可以自己去實作List中的數組擴充功能的，也許會更棒，因為我們沒有必要去将Array每次都擴充為原來的二倍。

另外的補充，Array相對于List還有個優勢就是：多元數組比List的嵌套更容易了解，也就是說int[][]（或者是int[,]）要強于List>，也就說在類型确定且多元的情況下，用Array要優于List。

本文來自：http://www.cnblogs.com/xinyuperfect/archive/2009/03/05/1403578.html 和http://www.cnblogs.com/xinyuperfect/archive/2009/03/09/1406657.html