从C#开始的编程入门——范型集合类

文章索引

数组已经是我们的老朋友了。数组提供了一种保存多个同类型对象的数据结构，并且提供了常见的存取方法以及搜索和查找方法，支持通过索引器随机访问（指哪儿打哪儿）。但是数组并不能满足所有需求，其中最大的缺点是它不能动态增减数组中的元素。

实际上在计算机世界中还有很多由基本元素构建起来的抽象数据结构，它们可以满足不同的需求。学习了类和范型的基础知识之后，我们来了解一下基础类库中提供的常见集合类。这些类位于System.Collections.Generics命名空间。

实际上C#不是一开始就支持范型，因此残留了一些不是范型类型的集合类，现在基本不再使用，下面为了方便我可能回省略范型类型的类型参数直接说名称，请不要忘记范型类型的范型参数。

范型集合类中的接口

System.Collections.Generics命名空间中的集合类几乎都实现了一些非常基础的接口，这些接口定义了常见集合类的共同特点。代表数组的Array类虽然不在这个命名空间，但是它也实现了集合类实现的很多接口，在适当的时候我可能会把它也视作集合类。

IEnumerable<T>

IEnumerable是一个范型接口。它是所有可枚举的集合都实现了接口，其中只包含了一个方法GetEnumerator，enumerator被称作枚举器，它表明一个集合（甚至可以不是集合）类应当怎样告知外界如何获得其中的每一个T类型的元素。它是foreach循环的实现基础，有关枚举器的实现我们在后面的文章中详细讲解。

ICollection<T>

Collection定义了集合类的一些基本集合属性和操作。其中主要定义了Count属性，代表集合中元素的个数。Add方法顾名思义，负责向集合中添加新的元素。Contains方法检查给定对象是否在集合中。Remove方法删除第一次出现的某个元素。

IList<T>

IList接口由ICollectin扩展而来。除了ICollection中提供的成员之外。该接口中还提供了索引器用于按索引访问元素，Insert方法用于在指定位置插入元素，RemoveAt用于移除指定位置的元素。简单来说，该接口主要由支持随机访问的集合类实现。

下面我们来介绍这个命名空间中常用的具体的集合类。

List

顾名思义，List一种线性列表，并且可以动态增减元素，它就像是一种动态数组，是非常常用的类型。

List<int> list = new List<int>(){1, 2, 3, 4, 5};

T是其元素类型，另一方面暗示了这种集合中的所有元素必须是同一个类型（对于类来说必须是同一个基类，或者是实现了同一个接口的类型）。

它实现了IList接口，它提供了和数组一样的索引器。

var n = list[2]; // 3

List是可以动态修改的数据结构：

list.Add(6); // 1,2,3,4,5,6
list.Remove(1); // 2,3,4,5,6
list.RemoveAt(3); // 2,3,4,6
System.Console.WriteLine(list.Count); // 4

LinkedList

LinkedList是双向链表。链表是一种元素相互链接的线性数据结构。链表中每一个元素（称节点，node）都有一个指向下一个（或前一个）节点的指针，使得可以快速访问链表的某个位置。由于链表只记录相对位置，通过引用直接访问相邻节点，因此不提供索引器。

T是链表中节点数据的类型，不是链表元素的类型，链表的元素实际上是另一个范型类型：LinkedListNode。这实际上就是代表节点的类型。它的主要属性就是当前节点的前一个和后一个节点，以及其中的值。

LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddFirst(1); // 1
linkedList.AddLast(2); // 1<->2
linkedList.AddBefore(linkedList.Find(2), 3); // 1<->3<->2
LinkedListNode<int> node = linkedList.Find(3);
System.Console.WriteLine(node.Previous.Value); // 1

Queue

Queue是队列。队列是一种先进先出（first in first out，FIFO）的数据结构。和它的名字一样，就像我们买奶茶排队一样。后来的永远只能站在最后，而每次离开队列的永远是队列最前面的（当然你买奶茶可能不见得先来先做好）。移除队首的操作被称为离队（出队，dequeue），进入队列的操作被称为入队（enqueue）。

Queue<string> queue = new Queue<string>();
queue.Enqueue(“火星烧仙草”); // 火星烧仙草（队首）
queue.Enqueue(“老八芋圆奶茶”); // 老八芋圆奶茶，火星烧仙草
queue.Enqueue(“先辈红茶”); // 先辈红茶，老八芋圆奶茶，火星烧仙草
queue.Dequeue(); // 先辈红茶，老八芋圆奶茶

同样由于其特殊性，它只实现ICollection，不提供随机访问。

Stack

Stack是范型栈。在前面介绍引用时我提到了栈。栈是一种先进后出（first in last out，LIFO）的数据结构，你可以认为它是一种被限制了的List。添加的新元素永远在最后面，而每次只能取出最上面的元素。

Stack<int> stack = new Stack<int>();
stack.Push(1); // 1
stack.Push(2); // 1, 2
stack.Pop();   // 1
stack.Push(3); // 1, 3

栈的操作限制比较严格。它实现了ICollection，因此也不提供索引器。可以通过Count获得栈有多少元素。Peek方法就是瞄一眼栈顶元素而不弹出。

Dictionary

这可以说是我们见到的第一个有两个类型参数的范型类。Dictionary是字典。C#中的字典是一种哈希表，简单来说哈希表可以通过键快速查询其对应的值，哈希表通过一种哈希函数根据键值算出对应的值。键和值通过哈希函数得到了一种对应关系。字典是一个很形象的名字，就像我们查字典首先在索引中查到想查的东西的页码，然后直接翻过去就是了。这样的哈希表在其他语言、技术中也称为映射、关联数组等等。

TKey是键的类型，TValue是值的类型。要注意的是，字典也可枚举，但是其元素是一个KeyValuePair对象，即键值对，它把键和值包装在一起。

Dictionary<int, string> dictionary = new Dictionary<int, string>();
dictionary.Add(1, “Tokino Sora”);
dictionary.Add(2, “Minato Aqua”);
dictionary[3] = “Sakura Miko”;
System.Console.WriteLine(dictionary[2]); // Minato Aqua

Add方法用于添加新的键值对。字典是重写索引器的典例。字典的索引器接受的参数类型是TKey，也就是键是什么类型就可以通过什么类型索引到值，因此也就不必是数值类型。通过字典的索引器我们可以方便地存取值。索引器的set会在键不存在时添加一个新键。

要获取所有键的集合或者值的集合，使用Keys属性和Values属性。Contains相关方法用于检查是否存在某个键或值。

这里我们简单地了解了基础类库中的一些常用集合类，一个合格程序员需要根据实际需求来选择合适的数据结构，数据结构本身也是一个非常有深度的领域。