1. 概述

前面介绍了数组和 Array 类实现的接口。数组的大小是固定的。如果元素个数是动态的，就应使用集合类。

List 是与数组相当的集合类。还有其他类型的集合：队列、栈、链表、字典和集。其他集合类提供的访问集合元素的 API 可能稍有不同，它们在内存中存储元素的内部结构也有差别。本文将介绍所有的集合类和它们的区别，包括性能差异。

2. 集合接口和类型

大多数集合类都可在 System.Collection 和 System.Collection.Generic 名称空间中找到。

泛型集合类位于 System.Collection.Generic 名称空间中；专用于特定类型的集合类位于 System.Collection.Specialized 名称空间中。线程安全的集合类位于 System.Collection.Conscurrent 名称空间中。不可变的集合类在 System.Collection.Immutable 名称空间中。

集合可以根据集合类实现的接口组合为列表、集合和字典。

3. 列表

.NET Framework 为动态列表提供了泛型类 List。这个类实现了 IList、ICollection、IEnumerable、IList、ICollection 和 IEnumerable 接口。

下面的例子将 Racer 类中的成员用作要添加到集合中的元素，以表示一级方程式的一位赛车手。这个类有5个属性：Id、FirstName、LastName、Country 和 Wins 的次数。在该类的构造函数中，可以传递赛车手的姓名和获胜次数，以设置成员。重写 ToString() 方法是为了返回赛车手的姓名。

Racer 类也实现了泛型接口 IComparable，为 Racer 类中的元素排序，还实现了 IFormattable 接口。

• IComparable：IComparable<T> 是一个泛型接口，用于实现对象的比较。它定义了一个方法 CompareTo()，用于比较当前对象与另一个对象的顺序关系。

• IFormattable 是一个接口，用于在自定义类型中实现自定义的格式化字符串输出。通过实现 IFormattable 接口，你可以控制自定义类型在使用格式化字符串输出时的行为。

public class Racer : IComparable<Racer>, IFormattable
{
    public int Id { get; }
    public string FirstName { get; }
    public string LastName { get; }
    public string Country { get; }
    public int Wins { get; }

    public Racer(int id, string firstName, string lastName, string country, int wins)
    {
        Id = id;
        FirstName = firstName;
        LastName = lastName;
        Country = country;
        Wins = wins;
    }

    public override string ToString() => $"{FirstName} {LastName}";

    public int CompareTo(Racer other)
    {
        int compare = LastName?.CompareTo(other?.LastName) ?? -1;
        if (compare == 0)
        {
            return FirstName?.CompareTo(other?.FirstName) ?? -1;
        }

        return compare;
    }

    public string ToString(string format, IFormatProvider formatProvider)
    {
        if (format == null) format = "N";
        switch (format.ToUpper())
        {
            case "N": return ToString();
            case "F": return FirstName;
            case "L": return LastName;
            case "W": return $"{ToString()}, Wins: {Wins}";
            case "C": return $"{ToString()}, Country: {Country}";
            case "A": return $"{ToString()}, Country: {Country} Wins: {Wins}";
            default: throw new FormatException(string.Format(formatProvider, $"Format {format} is not supported"));
        }
    }

    public string ToString(string format) => ToString(format, null);
}

3.1 创建列表

调用默认的构造函数就可以创建列表对象。在泛型类 List 中，必须为声明为列表的值指定类型。

var intList = new List<int>();
var racers = new List<Racer>();

C# 中的List<T>是一个动态数组，它可以根据需要自动调整容量。当向List<T>添加元素时，如果当前容量不足以容纳新的元素， List<T>会根据一定的策略增加其容量。

List<T>扩容的底层原理涉及到List<T>的内部数据结构和算法。List<T>使用一个数组来存储元素，并通过Capacity属性来表示当前数组的容量。当创建一个新的List<T>实例时，它的初始容量为0。随着向列表中添加元素，容量会根据需要进行调整。

当容量不足以容纳新的元素时，List<T>会执行以下操作：

• 分配一个更大的数组。List<T>会根据当前容量选择一个新的容量，通常是当前容量的2倍。这是为了减少频繁调整容量的开销，以提高性能。

• 将现有元素从旧数组复制到新数组。这涉及到内存复制操作，所以当列表中的元素数量较多时，这可能会有一定的性能开销。

• 更新Capacity属性来反映新的容量。

• 释放旧数组的内存。

这个过程称为"扩容"。通过一次扩容操作，List<T>可以存储更多的元素，而不需要每次添加元素时都重新分配内存。

需要注意的是，当从List<T>中删除元素时，并不会立即释放相应的内存。List<T>会保持其容量不变，除非显式调用TrimExcess方法来减小容量以匹配当前元素的数量。这样做可以减少内存的使用，但可能会导致后续的添加操作触发更多的扩容操作。

如果列表的容量改变了，整个集合就要重新分配到一个新的内存块中。为节省时间，如果事先知道列表中元素的个数，就可以用构造函数定义其容量。

List<int> intList = new List<int>(10);
// 使用 Capacity 属性可以获取和设置集合的容量。
intList.Capacity = 20;

容量（Capacity）与集合中的元素的个数（Count）不同。集合中的元素个数可以用 Count 属性读取。当然，容量总是大于或等于元素个数，只要不把元素添加到列表中，元素个数就是0。

如果已经将元素添加到列表中，且不希望添加更多的元素，就可以调用 TrimExcess()​​方法，去除不需要的容量。但是，因为重新定位需要时间，所以如果元素个数超过了容量的 90%，TrimExcess()​​方法就什么也不做。

intList.TrimExcess();

3.1.1 集合初始值设定项

List<int> intList = new List<int>() { 1, 2 };
List<string> stringList = new List<string>() { "one", "two" };

注意：集合初始值设定项没有反映在已编译的程序集的 IL 代码中。编译器会把集合初始值设置项转换成对初始值设定项列表中的每一项调用 Add() 方法。

3.1.2 添加元素

// Add 示例：
List<int> intList = new List<int>();
intList.Add(1);
intList.Add(2);

// 使用 List<T> 类的 AddRange() 方法，可以一次给集合添加多个元素。因为 AddRange() 方法的参数是 IEnumerable<T> 类型的对象，所以也可以传递一个数组。
// AddRange 示例：
using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> numbers = new List<int> { 1, 2, 3 };
        List<int> moreNumbers = new List<int> { 4, 5, 6 };

        numbers.AddRange(moreNumbers);

        foreach (int number in numbers)
        {
            Console.WriteLine(number);
        }
    }
}

注意：集合初始值设定项只能在声明集合时使用。AddRange() 方法则可以在初始化集合后调用。如果在创建集合后动态获取数据，就需要调用 AddRange()。

3.1.3 插入元素

使用 Insert() 和 InsertRange() 方法在指定位置插入元素或集合。

• Insert 方法用于在 List 中的指定索引位置插入一个元素。它接受两个参数：要插入的索引位置和要插入的元素。

List<int> numbers = new List<int> { 1, 2, 3, 4 };
numbers.Insert(2, 5); // 在索引位置 2 插入元素 5

// 输出结果：1 2 5 3 4
Console.WriteLine(string.Join(" ", numbers));

• InsertRange 方法用于在 List 中的指定索引位置插入一个集合。它接受两个参数：要插入的索引位置和要插入的集合。

List<int> numbers = new List<int> { 1, 2, 3, 4 };
List<int> moreNumbers = new List<int> { 5, 6, 7 };
numbers.InsertRange(2, moreNumbers); // 在索引位置 2 插入集合 moreNumbers

// 输出结果：1 2 5 6 7 3 4
Console.WriteLine(string.Join(" ", numbers));

在上面的示例中，我们创建了一个 List 类型的 numbers 列表，并使用初始值设定项语法初始化了一些整数。然后，我们使用 Insert 方法在索引位置 2 插入了元素 5。通过这个操作，元素 5 被插入到了索引位置 2，并将后续的元素向后移动。

接下来，我们创建了另一个 List 类型的 moreNumbers 列表，并使用初始值设定项语法初始化了一些整数。然后，我们使用 InsertRange 方法在索引位置 2 插入了 moreNumbers 列表中的元素。通过这个操作，moreNumbers 列表中的元素被插入到了 numbers 列表的索引位置 2，将后续的元素向后移动。

最后，我们使用 string.Join 方法和空格分隔符将 numbers 列表中的元素转换为字符串并打印出来。输出结果反映了元素的插入顺序。

如果索引集大于集合中的元素个数，Insert 和 InsertRange 方法将抛出 ArgumentOutOfRangeException 类型的异常。

这是因为索引表示要插入元素或集合的位置，它必须在合法范围内。如果索引超过了集合的边界，就会导致插入操作无法执行，因此引发 ArgumentOutOfRangeException 异常来指示错误的索引值。

以下是一个示例，演示当索引超出集合边界时会引发异常：

List<int> numbers = new List<int> { 1, 2, 3 };

try
{
    numbers.Insert(5, 4); // 索引 5 超出了集合范围
}
catch (ArgumentOutOfRangeException ex)
{
    Console.WriteLine(ex.Message);
}

上述代码中，我们尝试在索引 5 处插入元素 4，但是索引 5 超出了集合的边界。因此，Insert 方法会引发 ArgumentOutOfRangeException 异常。我们使用 try-catch 块捕获异常并打印异常信息。

运行以上代码，将会输出以下异常信息：

索引超出了集合边界。必须为 non-negative 且小于集合大小的值。

通过捕获和处理这个异常，可以在索引超出集合边界时进行适当的错误处理，例如显示错误消息、日志记录或采取其他必要的操作。

因此，当使用 Insert 和 InsertRange 方法时，请确保索引值在合法范围内，以避免 ArgumentOutOfRangeException 异常的引发。

3.1.4 访问元素

实现了 IList 和 IList 接口的所有类都提供了一个索引器，所以可以使用索引器，通过传递元素号来访问元素。

第一个元素可以用索引值0来访问。

Racer firstEle = racers[0];

可以使用 Count 属性确定元素个数，再使用 for 循环遍历集合中的每个元素，并使用索引器访问每一项。

for (int i = 0; i < racers.Count; i++)
{
    Console.WriteLine(racers[i]);
}

注意：可以通过索引访问的集合类有 ArrayList、StringCollection 和 List。

因为 List 集合类实现了 IEnumerable 接口，所以也可以使用 foreach 语句遍历集合中的元素。

3.1.5 删除元素

在 C# 中，List 类型提供了几种方法来删除元素：

• Remove 方法：根据元素的值从 List 中删除第一个匹配项。

List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
numbers.Remove(3); // 删除值为 3 的元素

// 输出结果：1 2 4 5
Console.WriteLine(string.Join(" ", numbers));

• RemoveAt 方法：根据索引位置从 List 中删除元素。

List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
numbers.RemoveAt(2); // 删除索引位置为 2 的元素

// 输出结果：1 2 4 5
Console.WriteLine(string.Join(" ", numbers));

• RemoveRange 方法：根据起始索引和要删除的元素数目，从 List 中删除一系列元素。

List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
numbers.RemoveRange(1, 3); // 从索引位置 1 开始，删除 3 个元素

// 输出结果：1 5
Console.WriteLine(string.Join(" ", numbers));

• RemoveAll 方法：根据指定条件删除 List 中的所有元素。

List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
numbers.RemoveAll(x => x % 2 == 0); // 删除所有偶数元素

// 输出结果：1 3 5
Console.WriteLine(string.Join(" ", numbers));

3.1.6 搜索

在 C# 中，List 类型提供了几种方式来搜索元素：

• IndexOf 方法：查找指定元素在 List 中第一次出现的索引。

List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
int index = numbers.IndexOf(3); // 查找值为 3 的元素的索引

// 输出结果：2
Console.WriteLine(index);

• LastIndexOf 方法：查找指定元素在 List 中最后一次出现的索引。

List<int> numbers = new List<int> { 1, 2, 3, 4, 3, 5 };
int lastIndex = numbers.LastIndexOf(3); // 查找值为 3 的元素最后一次出现的索引

// 输出结果：4
Console.WriteLine(lastIndex);

• Find 方法：根据指定条件查找第一个满足条件的元素。

List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
int foundNumber = numbers.Find(x => x % 2 == 0); // 查找第一个偶数元素

// 输出结果：2
Console.WriteLine(foundNumber);

• FindLast 方法：根据指定条件查找最后一个满足条件的元素。

List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
int lastFoundNumber = numbers.FindLast(x => x % 2 == 0); // 查找最后一个偶数元素

// 输出结果：4
Console.WriteLine(lastFoundNumber);

• FindAll 方法：根据指定条件查找所有满足条件的元素。

List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
List<int> evenNumbers = numbers.FindAll(x => x % 2 == 0); // 查找所有偶数元素

// 输出结果：2 4
Console.WriteLine(string.Join(" ", evenNumbers));

3.1.7 排序

List 类可以使用 Sort() 方法对元素排序。Sort() 方法使用快速排序算法，比较所有的元素，直到整个列表排好序位置。

public void Sort() { }
public void Sort(System.Collections.Generic.IComparer<T> comparer) { } // 传递泛型接口 IComparer<T>
public void Sort(System.Comparison<T> comparison) { } // 传递泛型委托 Comparison<T>
public void Sort(int index, int count, System.Collections.Generic.IComparer<T> comparer) { } // 传递一个范围值和泛型接口 IComparer<T>

只有集合中的元素实现了 IComparable 接口，才能使用不带参数的 Sort() 方法。

RacerComparer 类为 Racer 类型实现了接口 IComparer。这个类允许按名字、姓氏、国籍或获胜次数排序。排序的种类用内部枚举类型 CompareType 定义。CompareType 枚举类型用 RacerComparer 类的构造函数设置。

public class RacerComparer : IComparer<Racer>
{
    public enum CompareType { FirstName, LastName, Country, Wins }
    CompareType m_CompareType;
    
    public RacerComparer(CompareType compareType)
    {
        m_CompareType = compareType;
    }
    
    public int Compare(Racer x, Racer y)
    {
        if (x == null && y == null) return 0;
        if (x == null) return -1;
        if (y == null) return 1;
        int result;
        switch (m_CompareType)
        {
            case CompareType.FirstName: return string.Compare(x.FirstName, y.FirstName);
            case CompareType.LastName: return string.Compare(x.LastName, y.LastName);
            case CompareType.Country:
                result = string.Compare(x.Country, y.Country);
                if (result == 0) return string.Compare(x.LastName, y.LastName);
                return result;
            case CompareType.Wins: return x.Wins.CompareTo(y.Wins);
            default: throw new ArgumentException("Invalid Compare Type");
        }
    }
}

注意：如果传递给 Compare 方法的两个元素的顺序相同，该方法返回0。如果返回值小于0，说明第一个参数小于第二个参数；如果返回值大于0，则第一个参数大于第二个参数。传递 null 作为参数时，Compare 方法并不会抛出一个 NullReferenceException 异常。相反，因为 null 的位置在其他任何元素之前，所以如果第一个参数为 null，该方法返回-1，如果第二个参数为 null，则返回+1。

racers.Sort(new RacerComparer(RacerComparer.CompareType.Country));

排序的另一种方式是使用重载的 Sort() 方法，该方法需要一个 Comparison 委托：

public void List<T>.Sort(Comparison<T>);
public delegate int Comparison<T>(T x, T y);

Comparison 是一个方法的委托，该方法有两个 T 类型的参数，返回类型为 int。如果参数值相等，该方法就必须返回0。如果第一个参数比第二个参数小，它就必须返回一个小于0的值；否则，必须返回一个大于0的值。

// 现在可以把一个 Lambda 表达式传递给 Sort() 方法，按获胜次数排序。
racers.Sort((r1, r2) => r2.Wins.CompareTo(r1.Wins));

3.2 只读集合

创建集合后，它们就是可读写的，否则就不能给它们填充值了。但是，在填充完集合后，可以创建只读集合。

List 集合的 AsReadOnly() 方法返回 ReadOnlyCollection 类型的对象。ReadOnlyCollection 类实现的接口与 List 集合相同，但所有修改集合的方法和属性都抛出 NotSupportedException 异常。除了 List 的接口之外，ReadOnlyCollection 还实现了 IReadOnlyCollection 和 IReadOnlyList 接口。因为这些接口的成员，集合不能修改。

C# 提供了几种只读集合的实现，其中一些是：

• ReadOnlyCollection<T>：这是一个包装其他可变集合的只读包装器。它提供了一个不可修改的视图，但不会阻止原始集合的修改。

• ReadOnlyDictionary<TKey, TValue>：这是一个只读的字典实现，提供了对字典中键值对的只读访问权限。

• ReadOnlyList<T>：这是一个包装其他可变列表的只读包装器。它提供了对列表元素的只读访问权限，但不会阻止原始列表的修改。

这些只读集合的实现方式是通过封装可变集合并限制对其修改的访问权限来实现的。它们提供了一种方便的方式来确保数据的只读性，同时保持与可变集合的兼容性。

使用只读集合有几个好处：

• 只读集合提供了更安全的访问方式，可以防止不小心修改数据。

• 它们可以提高代码的可靠性和可维护性，因为只读集合的行为是确定的，不会受到外部修改的影响。

• 只读集合通常比复制可变集合的方式更高效，因为它们只是提供了对现有集合的只读视图，而不需要额外的内存开销。

要创建只读集合，可以使用相应的构造函数或者通过调用可变集合的AsReadOnly方法来创建只读包装器。例如：

List<int> mutableList = new List<int>() { 1, 2, 3 };
ReadOnlyCollection<int> readOnlyCollection = mutableList.AsReadOnly(); // 使用 AsReadOnly() 方法来创建只读包装器

Dictionary<string, int> mutableDictionary = new Dictionary<string, int>() { { "key1", 1 }, { "key2", 2 } };
ReadOnlyDictionary<string, int> readOnlyDictionary = new ReadOnlyDictionary<string, int>(mutableDictionary); // 使用构造函数创建只读包装器

需要注意的是，只读集合提供的只读性仅限于集合本身，而不包括集合中的元素。如果只读集合包装的可变集合被修改，只读集合也会反映这些修改。如果需要确保集合中的元素不可修改，可以使用不可变集合的方式，例如使用ImmutableList<T>或ImmutableDictionary<TKey, TValue>等类。

以下是一个示例，说明了通过修改可变集合来间接修改只读集合的行为：

List<int> mutableList = new List<int>() { 1, 2, 3 };
ReadOnlyCollection<int> readOnlyCollection = mutableList.AsReadOnly();

mutableList[0] = 10; // 修改可变集合中的元素

Console.WriteLine(readOnlyCollection[0]); // 输出为 10，只读集合反映了可变集合的修改

如果你需要修改集合中的元素，你需要使用可变的集合类型，如List<T>或Dictionary<TKey, TValue>。只读集合通常是通过对可变集合进行包装来实现的，所以只读集合本身不支持修改操作。

以下是一个示例，说明了只读集合无法修改其中元素的情况：

List<int> mutableList = new List<int>() { 1, 2, 3 };
ReadOnlyCollection<int> readOnlyCollection = mutableList.AsReadOnly();

readOnlyCollection[0] = 10; // 这里会引发编译错误，因为只读集合不支持修改操作

4. 队列

在 C# 中，队列（Queue）是一种先进先出（First-In-First-Out，FIFO）的数据结构。队列中的元素按照添加的顺序排列，并且只能在队列的末尾添加元素（入队），在队列的开头移除元素（出队）。

队列的例子有：排队、打印机待处理的打印任务以及按循环方式等待 CPU 处理的线程。另外，还常常有元素根据其优先级来处理的队列。

C# 中的队列数据结构使用 System.Collection.Generic 名称空间中的泛型类Queue<T>实现，其中T是要存储在队列中的元素的类型。在内部，Queue<T>类使用T类型的数组，这类似于List<T>类型。它实现 IColletion 和 IEnumerable 接口，但没有实现 ICollection 接口，因为这个接口定义的 Add() 和 Remove() 方法不能用于队列。

因为 Queue 类没有实现 IList 接口，所以不能用索引器访问队列。队列只允许在队列中添加元素，该元素会放在队列的尾部（使用 Enqueue() 方法），从队列的头部获取元素（使用 Dequeue() 方法）。

Queue 类的方法如下：

Count: Count 属性返回队列中的元素个数。
Enqueue: Enqueue() 方法在队列一端添加一个元素。
Dequeue: Dequeue() 方法在队列的头部读取和删除元素。如果在调用 Dequeue() 方法时，队列中不再有元素，就抛出一个 InvalidOperationException 类型的异常。
Peek: Peek() 方法从队列的头部读取一个元素，但不删除它。
TrimExcess: TrimExcess() 方法重新设置队列的容量。Dequeue() 方法从队列中删除元素，但它不会重新设置队列的容量。要从队列的头部去除空元素，应使用 TrimExcess() 方法。

类似 List 类，队列的容量也总是根据需要成倍增加。

以下是使用队列的基本示例：

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Queue<string> queue = new Queue<string>();

        // 入队操作
        queue.Enqueue("Apple");
        queue.Enqueue("Banana");
        queue.Enqueue("Cherry");

        // 出队操作
        string firstItem = queue.Dequeue();

        Console.WriteLine("出队元素：{0}", firstItem);

        // 获取队列的长度
        int count = queue.Count;
        Console.WriteLine("队列长度：{0}", count);

        // 查看队头元素（不移除）
        string peekItem = queue.Peek();
        Console.WriteLine("队头元素：{0}", peekItem);

        // 遍历队列中的元素
        Console.WriteLine("队列中的元素：");
        while (queue.Count > 0)
        {
            string item = queue.Dequeue();
            Console.WriteLine(item);
        }
    }
}

队列在很多场景中都非常有用，如任务调度、消息队列等。它提供了一种有序管理元素的方式，使得可以按照特定的顺序处理和访问元素。

5. 栈

在 C# 中，栈（Stack）是一种后进先出（Last-In-First-Out，LIFO）的数据结构。栈中的元素按照添加的顺序排列，并且只能在栈顶进行插入和删除操作。

C# 中的栈数据结构可以使用 Stack<T> 类实现，其中 T 是要存储在栈中的元素的类型。

与Queue<T>类相似，Stack<T>类实现 IEnumerable 和 ICollection 接口，所以Add()和Remove()方法同样不能用于栈。

Stack 类的成员：

Count: 返回栈中的元素个数。
Push: 在栈顶添加一个元素。
Pop: 从栈顶删除一个元素，并返回该元素。如果栈是空的，就抛出 InvalidOperationException 异常。
Peek: 返回栈顶的元素，但不删除它。
Contains: 确定某个元素是否在栈中，如果是，就返回 true。

说明一下后进先出的例子：

var alphabet = new Stack<char>();
alphabet.Push('A');
alphabet.Push('B');
alphabet.Push('C');
Console.Write("第一次迭代");
foreach (char item in alphabet)
{
    Console.Write(item.ToString()); // CBA
}

Console.Write("第二次迭代");
while (alphabet.Count > 0)
{
    Console.Write(alphabet.Pop().ToString()); // CBA
}

以下是使用栈的基本示例：

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Stack<string> stack = new Stack<string>();

        // 入栈操作
        stack.Push("Apple");
        stack.Push("Banana");
        stack.Push("Cherry");

        // 出栈操作
        string topItem = stack.Pop();

        Console.WriteLine("出栈元素：{0}", topItem);

        // 获取栈的长度
        int count = stack.Count;
        Console.WriteLine("栈长度：{0}", count);

        // 查看栈顶元素（不移除）
        string peekItem = stack.Peek();
        Console.WriteLine("栈顶元素：{0}", peekItem);

        // 遍历栈中的元素
        Console.WriteLine("栈中的元素：");
        while (stack.Count > 0)
        {
            string item = stack.Pop();
            Console.WriteLine(item);
        }
    }
}

/*
出栈元素：Cherry
栈长度：2
栈顶元素：Banana
栈中的元素：
Banana
Apple
*/

栈在很多场景中都非常有用，如函数调用栈、表达式求值、撤销操作等。它提供了一种有序管理元素的方式，使得可以按照特定的顺序处理和访问元素。

6. 链表

LinkedList<T>是一个双向链表，其元素指向它前面和后面的元素。这样一来，通过移动到下一个元素可以正向遍历整个链表，通过移动到前一个元素可以反向遍历整个链表。

链表的优点是，如果将元素插入列表的中间位置，使用链表就会非常快。在插入一个元素时，只需要修改上一个元素的 Next 引用和下一个元素的 Previous 引用，使它们引用所插入的元素。在 List 类中，插入一个元素时，需要移动该元素后面的所有元素。

当然，链表也有缺点。链表的元素只能一个接一个地访问，这需要较长的时间来查找位于链表中层或尾部的元素。

链表不能在列表中仅存储元素。存储元素时，链表还必须存储每个元素的下一个元素和上一个元素的信息。这就是 LinkedList 包含 LinkedListNode 类型的元素的原因。使用 LinkedListNode 类，可以获得列表中的下一个元素和上一个元素。LinkedListNode 定义了属性 List、Next、Previous 和 Value。List 属性返回与节点相关的 LinkedList 对象，Next 属性、Previous 属性用于遍历链表，访问当前节点之后和之前的节点。Value 返回与节点相关的元素，其类型是 T。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        LinkedList<string> linkedList = new LinkedList<string>();

        // 添加元素到链表尾部
        linkedList.AddLast("Apple");
        linkedList.AddLast("Banana");
        linkedList.AddLast("Cherry");

        // 遍历链表中的元素
        Console.WriteLine("链表中的元素：");
        foreach (string item in linkedList)
        {
            Console.WriteLine(item);
        }

        // 在指定节点之前插入新节点
        LinkedListNode<string> bananaNode = linkedList.Find("Banana");
        linkedList.AddBefore(bananaNode, "Grape");

        // 在指定节点之后插入新节点
        LinkedListNode<string> cherryNode = linkedList.Find("Cherry");
        linkedList.AddAfter(cherryNode, "Lemon");

        // 遍历链表中的元素
        Console.WriteLine("插入后的链表中的元素：");
        foreach (string item in linkedList)
        {
            Console.WriteLine(item);
        }

        // 移除指定节点
        linkedList.Remove("Banana");

        // 遍历链表中的元素
        Console.WriteLine("移除节点后的链表中的元素：");
        foreach (string item in linkedList)
        {
            Console.WriteLine(item);
        }
    }
}

/*
链表中的元素：
Apple
Banana
Cherry
插入后的链表中的元素：
Apple
Grape
Banana
Cherry
Lemon
移除节点后的链表中的元素：
Apple
Grape
Cherry
Lemon
*/

在上述示例中，我们创建了一个 LinkedList<string> 类型的链表实例，并使用 AddLast 方法将元素添加到链表的尾部。然后，我们使用 foreach 循环遍历链表中的元素，并将其输出。

接下来，我们使用 Find 方法找到指定节点，并使用 AddBefore 方法在该节点之前插入新节点，使用 AddAfter 方法在该节点之后插入新节点。

然后，我们再次使用 foreach 循环遍历链表中的元素，并将插入新节点后的链表输出。

最后，我们使用 Remove 方法移除指定的节点，并再次遍历链表中的元素。

7. 有序列表

在 C# 中，SortedList 是一种集合类，它实现了 IDictionary 接口，并提供了按照键的排序顺序来存储和访问键值对的功能。

SortedList 使用红黑树数据结构来保持键值对的有序性，这意味着在插入和删除操作后，键值对会按照键的顺序重新排序。由于 SortedList 维护了有序状态，因此在访问和搜索键值对时，它具有较高的性能。

以下是使用 SortedList 的基本示例：

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        SortedList sortedList = new SortedList();

        // 添加键值对
        sortedList.Add("apple", "苹果");
        sortedList.Add("banana", "香蕉");
        sortedList.Add("cherry", "樱桃");

        // 获取键值对的数量
        int count = sortedList.Count;
        Console.WriteLine("键值对数量：{0}", count);

        // 检查是否包含指定键
        bool containsKey = sortedList.ContainsKey("banana");
        Console.WriteLine("是否包含键 'banana'：{0}", containsKey);

        // 获取指定键的值
        string value = (string)sortedList["apple"];
        Console.WriteLine("键 'apple' 的值：{0}", value);

        // 修改指定键的值
        sortedList["cherry"] = "樱桃果";

        // 遍历键值对
        Console.WriteLine("键值对列表：");
        foreach (DictionaryEntry entry in sortedList)
        {
            Console.WriteLine("键：{0}，值：{1}", entry.Key, entry.Value);
        }

        // 移除指定键的键值对
        sortedList.Remove("banana");

        // 清空所有键值对
        sortedList.Clear();

        // 检查是否包含任何键值对
        bool isEmpty = sortedList.Count == 0;
        Console.WriteLine("是否为空：{0}", isEmpty);
    }
}

/*
键值对数量：3
是否包含键 'banana'：True
键 'apple' 的值：苹果
键值对列表：
键：apple，值：苹果
键：banana，值：香蕉
键：cherry，值：樱桃
是否为空：True
*/

8. 字典

字典表示一种非常负责的数据结构，这种数据结构允许按照某个键来访问元素。字段也成为映射或散列表。字典的主要特征是能根据键快速查找值。也可以自由地添加和删除元素，这有点像 List 类，但没有在内存中移动后续元素的性能开销。

.NET Framework 提供了几个字典类。可以使用的最主要的类是 Dictionary<TKey, TValue>。

8.1 字典初始化器

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 使用字典初始化器创建并初始化字典
        Dictionary<string, int> ages = new Dictionary<string, int>()
        {
            { "Alice", 25 },
            { "Bob", 30 },
            { "Charlie", 35 }
        };

        // 遍历字典中的键值对
        foreach (KeyValuePair<string, int> kvp in ages)
        {
            Console.WriteLine("键: {0}, 值: {1}", kvp.Key, kvp.Value);
        }
    }
}

/*
键: Alice, 值: 25
键: Bob, 值: 30
键: Charlie, 值: 35
*/

8.2 键的类型

在 C# 中，用作字典中键的类型需要重写 Object 类的 GetHashCode() 方法和 Equals() 方法。

GetHashCode() 方法用于生成对象的哈希码，它将对象映射到哈希表中的一个桶。在字典中，哈希码用于确定键值对应的存储位置，以便进行快速的查找和访问。

Equals() 方法用于比较对象的相等性。在字典中，它用于检查两个键是否相等，以便处理冲突的情况。

以下是一个示例，展示了如何定义一个自定义类型作为字典的键，并重写 GetHashCode() 和 Equals() 方法：

using System;
using System.Collections.Generic;

class Person
{
    public string Name { get; set; }
    public int Age { get; set; }

    public override int GetHashCode()
    {
        return Name.GetHashCode() ^ Age.GetHashCode();
    }

    public override bool Equals(object obj)
    {
        if (obj == null || GetType() != obj.GetType())
            return false;

        Person other = (Person)obj;
        return Name == other.Name && Age == other.Age;
    }
}

class Program
{
    static void Main()
    {
        Dictionary<Person, string> personDict = new Dictionary<Person, string>();

        Person person1 = new Person { Name = "Alice", Age = 25 };
        Person person2 = new Person { Name = "Bob", Age = 30 };

        personDict[person1] = "Entry 1";
        personDict[person2] = "Entry 2";

        // 访问字典中的值
        Console.WriteLine("person1 的值: {0}", personDict[person1]);
        Console.WriteLine("person2 的值: {0}", personDict[person2]);
    }
}

在上述示例中，我们定义了一个 Person 类，其中包含 Name 和 Age 属性。我们重写了 GetHashCode() 方法，将 Name 和 Age 属性的哈希码进行异或运算，并重写了 Equals() 方法，比较了两个 Person 对象的 Name 和 Age 属性是否相等。

然后，我们创建了一个 Dictionary<Person, string> 类型的字典 personDict，并使用 Person 对象作为键，将键值对添加到字典中。通过访问 personDict[person1] 和 personDict[person2]，我们可以获取相应键的值。

需要注意的是，在重写 GetHashCode() 和 Equals() 方法时，需要保证相等的对象具有相同的哈希码。这样可以确保在字典中进行查找和比较时得到正确的结果。

Object.GetHashCode 方法 (System) | Microsoft Learn

8.3 字典实例

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 创建一个字典
        Dictionary<string, int> studentGrades = new Dictionary<string, int>();

        // 添加键值对
        studentGrades["John"] = 90;
        studentGrades["Alice"] = 85;
        studentGrades["Bob"] = 95;

        // 获取字典中的值
        int johnsGrade = studentGrades["John"];
        Console.WriteLine("John's grade: " + johnsGrade);

        // 修改字典中的值
        studentGrades["Alice"] = 88;

        // 检查字典中是否包含某个键
        if (studentGrades.ContainsKey("Bob"))
        {
            // 删除字典中的键值对
            studentGrades.Remove("Bob");
        }

        // 迭代字典中的键值对
        foreach (var kvp in studentGrades)
        {
            Console.WriteLine(kvp.Key + ": " + kvp.Value);
        }
    }
}

8.4 Lookup 类

在 C# 中，Lookup 类是一种用于表示多值的数据结构，它提供了一种将一个键映射到多个值的能力。与 Dictionary 不同，Lookup 不允许重复的键，而是将每个键与一个或多个值的序列关联起来。

Lookup 类实现了 ILookup<TKey, TValue> 接口，它提供了一组方法和属性来操作和查询多值数据。

以下是使用 Lookup 类的示例：

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        List<Person> persons = new List<Person>()
        {
            new Person { Name = "Alice", City = "New York" },
            new Person { Name = "Bob", City = "London" },
            new Person { Name = "Charlie", City = "Paris" },
            new Person { Name = "Alice", City = "Berlin" }
        };

        // 使用 ToLookup 方法创建 Lookup 对象，按照 Name 属性进行分组
        ILookup<string, Person> lookup = persons.ToLookup(p => p.Name);

        // 查询指定键的值集合
        string name = "Alice";
        IEnumerable<Person> alicePersons = lookup[name];

        Console.WriteLine("键 '{0}' 的值集合：", name);
        foreach (Person person in alicePersons)
        {
            Console.WriteLine("Name: {0}, City: {1}", person.Name, person.City);
        }
    }
}

class Person
{
    public string Name { get; set; }
    public string City { get; set; }
}

/*
键 'Alice' 的值集合：
Name: Alice, City: New York
Name: Alice, City: Berlin
*/

8.5 有序字典

SortedDictionary<TKey, TValue>是一个二叉搜索树，其中的元素根据键排序。该键类型必须实现 IComparable 接口。如果键的类型不能排序，则还可以创建一个实现了 IComparer 接口的比较器，将比较器用作有序字典的构造函数的一个参数。

如前所述，SortedDictionary<TKey, TValue>和SortedList<TKey, TValue>的功能类似。但因为SortedList<TKey, TValue>实现为一个基于数组的列表，而SortedDictionary<TKey, TValue>类实现为一个字典，所以它们有不同的特征。

• SortedList<TKey, TValue> 使用的内存比 SortedDictionary<TKey, TValue> 少。

• SortedDictionary<TKey, TValue> 的元素插入和删除操作比较快。

• 在用已排好序的数据填充集合时，若不需要修改容量，SortedList<TKey, TValue> 就比较快。

以下是使用有序字典的示例：

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 创建一个有序字典，并添加键值对
        SortedDictionary<string, int> ages = new SortedDictionary<string, int>();

        ages.Add("Bob", 30);
        ages.Add("Alice", 25);
        ages.Add("Charlie", 35);

        // 遍历有序字典的键值对
        foreach (KeyValuePair<string, int> kvp in ages)
        {
            Console.WriteLine("键: {0}, 值: {1}", kvp.Key, kvp.Value);
        }

        // 根据键获取值
        int aliceAge = ages["Alice"];
        Console.WriteLine("Alice 的年龄: {0}", aliceAge);

        // 检查字典中是否包含指定键
        bool containsBob = ages.ContainsKey("Bob");
        Console.WriteLine("是否包含 Bob: {0}", containsBob);
    }
}

/*
键: Alice, 值: 25
键: Bob, 值: 30
键: Charlie, 值: 35
Alice 的年龄: 25
是否包含 Bob: True
*/

9. 集

包含不重复元素的集合称为“集（set）”。.NET Core 包含两个集（HashSet 和 SortedSet），它们都实现 ISet 接口。HashSet 集包含不重复元素的无序列表，SortedSet 集包含不重复元素的有序列表。

ISet 接口提供的方法可以创建合集、交集，或者给出一个集是另一个集的超集或子集的信息。

HashSet 集实现 ICollection 接口。但是在该类中，Add() 方法是显式实现的，还提供了另一个 Add() 方法。Add() 方法的区别是返回类型，它返回一个布尔值，说明是否添加了元素。如果该元素已经在集中，就不添加它，并返回false。

• HashSet<T>：HashSet<T> 实现了 ISet<T> 接口，它提供了基于哈希表的集合功能。HashSet<T> 内部使用哈希表来存储元素，因此具有快速的插入、删除和查找操作。HashSet<T> 不保持元素的顺序，元素的顺序是根据哈希算法决定的。它是最常用的集合类型之一。

示例代码：

HashSet<string> set = new HashSet<string>();

set.Add("apple");
set.Add("banana");
set.Add("orange");

foreach (string item in set)
{
    Console.WriteLine(item);
}

• SortedSet<T>：SortedSet<T> 实现了 ISortedSet<T> 接口，它提供了有序集合的功能。SortedSet<T> 内部使用红黑树数据结构来存储元素，并且保持元素的有序状态。插入、删除和查找操作的时间复杂度都是 O(log n)。SortedSet<T> 可以按照元素的自然顺序或者通过自定义的比较器进行排序。

示例代码：

SortedSet<int> set = new SortedSet<int>();

set.Add(5);
set.Add(2);
set.Add(8);

foreach (int item in set)
{
    Console.WriteLine(item);
}

HashSet 类 (System.Collections.Generic) | Microsoft Learn

SortedSet 类 (System.Collections.Generic) | Microsoft Learn

10. 性能

• O(1) 表示无论集合中有多少数据项，这个操作需要的时间都不变。

  例如，ArrayList 类的 Add() 方法就具有 O(1) 行为。无论列表中有多少个元素，在列表末尾添加一个新元素的时间都相同。Count 属性会给出元素个数，所以很容易找到列表末尾。

• O(n) 表示对于集合执行一个操作需要的时间在最坏情况时是 N。如果需要重新给集合分配内存，ArrayList 类的 Add() 方法就是一个 O(n) 操作。改变容量，需要复制列表，复制的时间随元素的增加而线性增加。

• O(log n) 表示操作需要的时间随集合中元素的增加而增加，但每个元素需要增加的时间不是线性的，而是呈对数曲线。在集合中执行插入操作时，SortedDictionary<TKey, TValue> 集合类具有 O(log n) 行为，而 SortedList<TKey, TValue> 集合类具有 O(n) 行为。这里 SortedDictionary<TKey, TValue> 集合类要快得多，因为它在树型结构中插入元素的效率比列表高得多。

11 总结

本章介绍了如何处理不同类型的泛型集合。

数组的大小是固定的，但可以使用列表作为动态增长的集合。

队列以先进先出的方式访问元素，栈以后进先出的方法访问元素。

链表可以快速地插入和删除元素，但搜索操作比较慢。

通过键和值可以使用字典，它的搜索和插入操作比较快。

集（set）用于唯一项，可以是无序的 HashSet，也可以是有序的 SortedSet。