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,