C#容器——数组和列表

C# 中数组和列表通常用来存放一系列元素

1. 数组

1.1 数组的常见用法

• 声明和读写

        // 长度固定，在声明时指定
        int[] intArr = new int[5];

        // 使用下标读写
        intArr[0] = 100;
        int value = intArr[1];

• 三种遍历方法

        // 遍历数组
        for (int i = 0; i < intArr.Length; i++)
        {
            Debug.Log(string.Format("{0}:{1}", i, intArr[i]));
        }

        int index = 0;
        // 使用迭代器遍历
        IEnumerator enumerator = intArr.GetEnumerator();
        while (enumerator.MoveNext())
        {
            Debug.Log(string.Format("{0}:{1}", index++, enumerator.Current));
        }

        index = 0;
        // 另外一种遍历
        foreach (int v in intArr)
        {
            Debug.Log(string.Format("{0}:{1}", index ++, v));
        } 

• 数组的克隆，数组的 Clone 方法是深复制实现

        int[] anotherArr = intArr.Clone() as int[]; 

1.2 抽象类 Array

Array源码

• 抽象类Array是所有数组的基类
  Array 实现 IList 和 ICollection 接口，但屏蔽了部分接口如Add，Contains等方法的实现，所以数组对象并不具备这些能力（如何屏蔽可查看源码中对应方法的实现）
• Array 抽象类提供了大量的静态方法操作数组，包括查找、排序、复制、二分查找、数组反转等

        // 排序
        Array.Sort(intArr);

        // 查找下标
        int indexOf2 = Array.IndexOf<int>(intArr, 2);

        // 反转数组
        Array.Reverse(intArr);

        // 二分查找
        int indexOf3 = Array.BinarySearch<int>(intArr, 3);

        // 复制
        Array.Copy(intArr, anotherArr, intArr.Length);

1.3 数组优缺点

Array(数组)的特点

• 使用一片连续的存储空间
• 数组的长度是固定的，必须在数组对象定义时确定
• 数组元素的类型必须相同，在对象定义时确定

优点：

• 可使用下标访问元素，查找时间复杂度O(1)
• 元素类型固定，读写时不需要做类型转换，不涉及装拆箱等性能损耗

缺点：

• 元素个数固定，不适用于数量不确定的场景

2. ArrayList

ArrayList源码
ArrayList 是一个非泛型类，实现了 IList 和 IEnumerable 接口

2.1 ArrayList的常见用法

        // 添加元素
        al.Add(1);
        al.Add("one");

        // 下标访问
        al[1] = 100;
        string value = al[2] as string;
        
        // 遍历,同样可以用 foreach 和迭代器来遍历
        for (int i = 0; i < al.Count; i ++)
        {
            Debug.Log(string.Format("{0}:{1}", i, al[i]));
        }        

        // 删除元素
        al.Remove("one");
        al.RemoveAt(0);

        // 是否包含元素
        bool contains = al.Contains("one");

        // 清除列表
        al.Clear();

，用来存放数据列表，元素可以是不同类型（存储时都使用了 object 类型）

2.2 ArrayList 的底层存储结构

查看源码可以看到，ArrayList的存储字段是

public Object[] _items;

可见，它的底层存储结构是 object类型数组，当添加或插入值类型对象时，会进行一次装箱，类似的，读取时会进行一次拆箱

2.3 ArrayList的扩容

• ArrayList实例化时可以指定初始容量，默认容量是4
• 添加或插入元素时，如果超过当前 _items 的容量，会触发 扩容逻辑，扩容的逻辑大概是：申请一个当前容量2倍的数组，把当前的元素全部搬过去，再插入元素

2.4 ArrayList 添加元素

Add 、AddRange方法在尾部添加元素

• 若未触发扩容，时间复杂度O(1)
• 若触发扩容，会搬运元素，时间复杂度O(n)
  添加元素触发扩容前的时间复杂是 O(1)，触发扩容则是 O(n)，详情可以查看源码中相关方法实现，插入元素则会导致数组元素的位置变化，复杂度 O(n)

2.5 ArrayList 插入元素

Insert、InsertRange 方法在指定位置插入元素
无论是否触发扩容，都需要搬运元素（无扩容时，所有插入位置后的元素要搬运到对应的下标处），时间复杂度 O(n)

2.6 ArrayList 查找元素

Contains方法返回列表中是否存在元素，可定制 comparer，IndexOf 方法找到元素下标，BinarySearch方法返回元素下标，查找方法的时间复杂度都是 O(lg n)

3.3 ArrayList 移除元素

包括Remove和RemoveAt方法
Remove 参数为元素对象时，先调用方法 IndexOf 找到下标，再调用 RemoveAt 方法进行移除，该方法会导致数组元素的位置变化，所以移除时间复杂度O(n)

3.4 ArrayList 优缺点

优点：

• 类型通用，更灵活
• 长度不固定，更灵活
• 可以通过下标访问，查询复杂度 O(1)

缺点：

• 使用 object[] 来存储，对于值类型元素，在添加和读取时涉及到装箱和拆箱操作，性能损耗
• 类型安全性，在处理某个元素时可能当成错误的类型处理
• 长度不固定，添加元素导致扩容时，性能和空间损耗
• 添加和插入元素时的复杂度 O(n)

4. List

List源码
List 是一个泛型类，在初始化时必须指定元素的类型

4. 1 List常见用法

        // 声明
        List<int> l = new List<int>();

        // 添加元素
        l.Add(1);
        l.AddRange(new int[] { 1, 2, 3 });

        // 下标访问
        l[2] = 5;
        int value = l[3];

        // 插入元素
        l.Insert(1, 56);

        // 查找
        int index = l.IndexOf(56);
        bool contains = l.Contains(56);

        // 遍历
        List<int>.Enumerator enumerator = l.GetEnumerator();
        while (enumerator.MoveNext())
        {
            Debug.Log("value:" + enumerator.Current);
        }

        // 移除
        l.RemoveAt(0);
        l.Remove(1);

4.1 List 的存储结构

• List的存储结构也是数组

public T[] _items;

• 实例化时默认数组长度是4
• 添加元素时，可能会触发扩容，扩容逻辑和 ArrayList类似

4.2 元素添加和移除

执行逻辑和 ArrayList 一样，方法为 Add, AddRange, Remove, RemoveAt, RemoveAll 等，时间复杂度也一样

4.3 List 的元素查找

和 ArrayList 一样，Contains 和 IndexOf 、BinarySearch方法都是二分查找，时间复杂度 O(lg n)

4.4 List 的优缺点

的优点：

• 长度不固定，更灵活
• 元素类型固定，读写时不会有装箱拆箱的性能损耗
• 可以下标访问，查询复杂度 O(1)

缺点：
扩容导致的性能和空间损耗
插入元素导致的元素移位，复杂度O(n)

5. LinkedList

LinkedList源码
LinkedList不再实现 IList接口，但实现了 ICollection 接口，LinkedList 是一个泛型类，使用时需要指定元素类型

5.1 LinkedList 的常见用法

        // 声明
        LinkedList<int> ll = new LinkedList<int>();

        // 在头尾添加元素
        ll.AddFirst(1);
        ll.AddLast(100);

        // 在对应节点前后添加元素
        ll.AddBefore(ll.Find(1), 2);
        ll.AddAfter(ll.Find(100), 101);

        // 遍历
        LinkedList<int>.Enumerator enumerator = ll.GetEnumerator();        
        while (enumerator.MoveNext())
        {
            Debug.Log(enumerator.Current);
        }

        // 另外一种遍历方法
        LinkedListNode<int> cur = ll.First;
        while (cur.Next != null)
        {
            Debug.Log(cur.Value);
            cur = cur.Next;
        }

        // 长度
        int count = ll.Count;

        // 移除
        ll.Remove(100);
        ll.RemoveFirst();
        ll.RemoveLast();

        // 查找
        bool contains = ll.Contains(100);
        LinkedListNode<int> node = ll.Find(100);  

5.2 LinkedList 的存储结构

LinkedList的存储结构是双向链表，关联结构体 LinkedListNode:

internal LinkedListNode<T> head;

使用双向链表来存储数据，保留了表头的引用，需要配合链表类型 LinkedListNode 来使用

5.3 LinkedList 的添加和插入

AddAfter 和 AddBefore 方法，在某节点的前面或后面插入节点，时间复杂度 O(1)
AddFirst 和 AddLast 方法，在头部或尾部插入节点，时间复杂度 O(1)

5.4 LinkedList 的删除

Remove、RemoveFirst 和 RemoveLast 都是重置节点的 next 和 last 指针，时间复杂度 O(1)

5.5 LinkedList 的查找

Contains 和 Find 方法，都是从头指针开始遍历，时间复杂度 O(n)

5.6 LinkedList 的优缺点

优点：

• 不需要预先分配空间，且没有额外占用空间，不会触发扩容
• 添加和移除的时间复杂度 O(1)

缺点：

• 不支持下标快速访问，查找时间复杂度 O(n)

6. 总结

容器类型	存储方式	类型固定	下标访问	额外空间	添加和插入复杂度	删除复杂度	查找复杂度
数组Array	连续内存存储	类型固定	支持	固定长度，无额外空间	x	x	二分查找 O(lgn)
ArrayList	数组	类型灵活	支持	2倍扩容，可能产生额外空间	O(n)	O(n)	二分查找 O(lgn)
List<T>	数组	类型固定	支持	2倍扩容，可能产生额外空间	O(n)	O(n)	二分查找 O(lgn)
LinkedList<T>	双向链表	类型固定	不支持	每个元素额外两个指针;无需扩容	O(1)	O(1)	从头指针遍历O(n)

参考：
C#容器源码