C#集合 -- Lists，Queues， Stacks 和 Sets

List<T>和ArrayList

Generic的List和非Generic的ArrayList類支持可變化大小的對象數組，它們也是最常見的集合類。ArrayList實現了IList接口，而List<T>實現了IList<T>和IList接口（以及新增的IReadonlyList<T>）。與數組不同，所有的接口實現都是公開的，并且Add和Remove方法也對外公開；它們會按照你的希望執行。

在List<T>和ArrayList內部，維護了一個內部的數組對象，當這個內部數組對象的大小超過時，創建一個新的數組來替代原數組。附加元素效率很高（因為通常有一個空閑插槽結尾），但插入的元素可能會很慢（因為有插入點之后的所有元素將位移以產生一個空閑插槽）。對于數組而言，如果集合如果是排好序的，那么執行BinarySearch方法非常高效，但從另一個方面而言，這又不高效，因為在執行BinarySearch之前，需要檢查每個元素（以排序）。

對于值類型，List<T>的比ArrayList快幾倍，這是因為List<T>避免了裝箱和拆箱的開銷。

List<T>和ArrayList都提供了構造器方法，以接收元素集合；構造器方法遍歷集合的元素到新的List<T>或ArrayList對象中。List<T>的定義大致如下：

public class List<T> : IList<T>, IReadOnlyList<T>{public List ();public List (IEnumerable<T> collection);public List (int capacity);// Add+Insertpublic void Add (T item);public void AddRange (IEnumerable<T> collection);public void Insert (int index, T item);public void InsertRange (int index, IEnumerable<T> collection);// Removepublic bool Remove (T item);public void RemoveAt (int index);public void RemoveRange (int index, int count);public int RemoveAll (PRedicate<T> match);// Indexingpublic T this [int index] { get; set; }public List<T> GetRange (int index, int count);public Enumerator<T> GetEnumerator();// Exporting, copying and converting:public T[] ToArray();public void CopyTo (T[] array);public void CopyTo (T[] array, int arrayIndex);public void CopyTo (int index, T[] array, int arrayIndex, int count);public ReadOnlyCollection<T> AsReadOnly();public List<TOutput> ConvertAll<TOutput> (Converter <T,TOutput>converter);// Other:public void Reverse(); // Reverses order of elements in list.public int Capacity { get;set; } // Forces expansion of internal array.public void TrimExcess(); // Trims internal array back to size.public void Clear(); // Removes all elements, so Count=0.}

除了上述方法之外，List<T>還提供了與Array類一樣的搜索和排序的實例方法。下面的例子演示了List的屬相和方法：

static void Main(string[] args){    List<string> Words = new List<string>();    words.Add("melon");    words.Add("avocado");    words.AddRange(new[] { "banana", "plum" });    words.Insert(0, "lemon");    words.InsertRange(0, new[] { "peach", "nashi" });    words.Remove("melon");    words.RemoveAt(3);    words.RemoveRange(0, 2);    words.RemoveAll(s => s.StartsWith("n"));    Console.WriteLine(words[0]);    Console.WriteLine(words[words.Count - 1]);    foreach (string s in words)        Console.WriteLine(s);    string[] wordsArray = words.ToArray();    string[] existing = new string[1000];    words.CopyTo(0, existing, 998, 2);    List<string> upperCastwords = words.ConvertAll(s => s.ToUpper());    List<int> lenghts = words.ConvertAll(s => s.Length);        Console.ReadLine();}

而非generic的ArrayList主要用于和Framework1.x的代碼兼容，因為其要求一個類型轉換，比如下面的代碼

ArrayList al = new ArrayList();al.Add ("hello");string first = (string) al [0];string[] strArr = (string[]) al.ToArray (typeof (string));

而這樣的轉換不能被編譯器驗證，因此下面的代碼可以通過編譯，但是在運行時卻會報錯

int first = (int) al [0];

ArrayList和List<Object>類似。兩者在處理混合類型的集合時非常有用。有一種場景特別適合使用ArrayList，那么就是處理反射時。

如果你引用了System.Linq命名空間，那么你就使用LINQ的Cast方法把一個ArrayList轉換成一個Generic的List

ArrayList al = new ArrayList();al.AddRange(new[] { 1, 5, 9 });List<int> list = al.Cast<int>().ToList();

Cast和ToList方法時System.Linq.Enumerable類的擴展方法。Cast方法首先嘗試直接把ArrayList轉換成List，如果轉換不成功，那么遍歷ArrayList，轉換每個元素，并返回IEnumerable<T>。而ToList()方法則是直接調用List<T>的構造函數public List (IEnumerable<T> collection)；從而實現IEnumerable<T>轉換成List<T>。

List<T>接收值為null的引用類型；此外List<T>還允許重復的元素。

List<T>既適用相等性比較器，也使用排序比較器。當調用Contains, IndexOf, LastIndeoxOf, Remove等方式時，會使用相等性比較器。List<T>會使用T類型的默認相等比較器。如果T類型實現了IEquatable<T>接口，那么調用該接口的Equals(T)方法；否則調用Object.Equals(Object)方法進行相等性比較。List<T>的BinarySearch、Sort方法使用排序比較器。同相等性比較器一樣，List<T>會使用T類型的默認排序比較器，如果T類型實現了IComparable<T>接口，那么調用該接口的CompareTo(T)方法，否則使用非Generic接口IComparable的CompareTo(Object)方法。

List<T>的靜態成員是線程安全的，而實例成員不能確保類型安全。多線程讀取IList<T>是線程安全的，但是如果在讀的過程中被修改了，那么就會引發問題，比如下面的代碼：

class Program{    static List<int> numbers = new List<int>();    static void Main(string[] args)    {        numbers.Add(0);        Thread t1 = new Thread(GetNum);        t1.Start();        Thread t2 = new Thread(SetNum);        t2.Start();        Console.ReadLine();    }    static void GetNum()    {        Console.WriteLine("t1->" + numbers[0]);  // -> 0        Thread.Sleep(1000);        Console.WriteLine("t1->" + numbers[0]); // -> 2    }    static void SetNum()    {        numbers[0] = 2;        Console.WriteLine("t2->" + numbers[0]); // ->2    }}

在GetNum方法中，兩次讀取List<Int>的第一個元素時，值發生變化。因此，我們需要手動實現線程同步。一般常用的方式時使用lock鎖住List<T>對象

class Program{    static List<int> numbers = new List<int>();    static object locker = new object();    static void Main(string[] args)    {        numbers.Add(0);        Thread t1 = new Thread(GetNum);        t1.Start();        Thread t2 = new Thread(SetNum);        t2.Start();        Console.ReadLine();    }    static void GetNum()    {        lock (locker)        {            Console.WriteLine("t1->" + numbers[0]);  // ->             Thread.Sleep(1000);            Console.WriteLine("t1->" + numbers[0]); // -> 0        }    }    static void SetNum()    {        lock (locker)        {            numbers[0] = 2;            Console.WriteLine("t2->" + numbers[0]); // ->2        }    }}

另外，微軟在System.Collection.Concurrent命名空間下，提供了幾個用于并發的集合類

LinkedList<T>

LinkedList<T>是雙向鏈表列表。所謂雙向鏈表列表就是這樣節點鏈條，每個節點都包含前一個節點引用，后一個節點引用，以及自己的引用。它最大的益處就是可以高效地插入元素到列表的任意位置，因為它值需要創建一個新的節點，然后更新相關引用（前一個節點的引用和后一個節點的引用）。然后向鏈表列表的第一個位置插入新的節點可能會很慢，這是因為在鏈表內部沒有內在的索引機制，因此每次節點都需要遍歷，而且也不能使用二進制印章（binary-chop）搜索。下圖是LinkedList<T>示意圖

LinkedList<T>實現了IEnumerable<T>接口和ICollection<T>接口，但沒有實現IList<T>接口，所以其不支持索引。

LinkedListNode的代碼大致如下：

public sealed class LinkedListNode<T> {    internal LinkedList<T> list;    internal LinkedListNode<T> next;    internal LinkedListNode<T> prev;    internal T item;        public LinkedListNode( T value) {        this.item = value;    }    internal LinkedListNode(LinkedList<T> list, T value) {        this.list = list;        this.item = value;    }    public LinkedList<T> List {        get { return list;}    }    public LinkedListNode<T> Next {        get { return next == null || next == list.head? null: next;}    }    public LinkedListNode<T> Previous {        get { return prev == null || this == list.head? null: prev;}    }    public T Value {        get { return item;}        set { item = value;}    }    internal void Invalidate() {        list = null;        next = null;        prev = null;    }           }

當向LinkedList<T>添加一個節點時，你可以致命節點的位置，或者相對于另一個節點的位置，或者列表的開始/結束位置。LinkedList<T>提供了下面的方法添加節點

public void AddFirst(LinkedListNode<T> node);public LinkedListNode<T> AddFirst (T value);public void AddLast (LinkedListNode<T> node);public LinkedListNode<T> AddLast (T value);public void AddAfter (LinkedListNode<T> node, LinkedListNode<T> newNode);public LinkedListNode<T> AddAfter (LinkedListNode<T> node, T value);public void AddBefore (LinkedListNode<T> node,