C#数据结构

一、数组

数组是用来存储数据的集合，具有以下特点：

1. 元素类型相同；
2. 固定长度；
3. 顺序集合。

数组使用的实例：

void arrayTest()
{
    // 定义数组
    int[] array_1;
    int[] array_2 = new int[3];
    int[] array_3 = new int[3] { 1, 2, 3 };
    int[] array_4 = { 1, 2, 3, 4, 5 };
    // 初始化
    array_1 = new int[3];
    Debug.Log(array_1[0]);
    array_1[0] = 5;
    Debug.Log(array_1[0]);
    // 打印数组的长度
    Debug.Log(array_1.Length);
    // 数组的遍历
    for(int i = 0; i < array_3.Length; i++)
    {
        Debug.Log(array_3[i]);
    }
    foreach(var v in array_4)
    {
        Debug.Log(v);
    }
}

二、ArrayList

1. ArrayList的概念

动态数组（ArrayList）对象的有序集合。

2. ArrayList的特点

• 相比于数组，动态数组ArrayList会自动重新调整它的大小。
• 可以使用索引在指定的位置添加和移除项目，它也允许在列表中进行动态内存分配。

3. ArrayList的实例

ArrayList arrayList1 = new ArrayList();
    int[] arr1 = new int[4] { 1, 2, 3, 4 };

void Start()
{
    // 添加元素
    arrayList1.Add(10);
    arrayList1.Add(11);
    arrayList1.Add(12);
    // 将数组元素插入至ArrayList
    arrayList1.AddRange(arr1);
    // 打印元素
    foreach(var v in arrayList1)
    {
        Debug.Log(v);
    }
    // 清除元素
    arrayList1.Clear();
    // 判断是否包含指定元素
    if (arrayList1.Contains(12))
    {
        Debug.Log("包含12");
    }
    // 返回指定元素第一次出现的索引 
    // -1 没有找到
    Debug.Log(arrayList1.IndexOf(12));
    // 插入元素   插入索引 插入的元素
    arrayList1.Insert(3, 67);
    // 移除元素
    arrayList1.Remove(67);
    // 逆置元素
    arrayList1.Reverse();
    // 元素排序
    arrayList1.Sort();
}

三、List

1. List概述

• 泛型类

  集合List<>
• 作用与功能近似 ArrayList
• 无需装箱拆箱，类型转换
• 类型安全

2. List使用示例

// 声明和初始化List
List<int> list_1 = new List<int>();
int[] arr = new int[2] { 1, 2 };

void Start()
{
    // 添加元素
    list_1.Add(10);
    list_1.AddRange(arr);
    // 计算元素个数
    int count = list_1.Count;
    Debug.Log(count);
    // 打印元素
    foreach(var v in list_1)
    {
        Debug.Log(v);
    }
    // 判断是否包含指定元素
    if (list_1.Contains(10))
    {
        Debug.Log("包含10");
    }
    // 移除元素
    list_1.Remove(1);
    // 清除元素
    list_1.Clear();
    // 方法与ArrayList大致相同
}

3. ArrayList和List的区别

1. 由于ArrayList需要先将类型转变为Object也就是装箱和拆箱的操作，而List不需要，所以 List 性能较高，ArrayList性能较低。
2. 在ArrayList中插入不同类型的数据是允许的，（例如插入字符串后再插入数字）因为ArrayList会把所有插入元素当作Object类型处理；而 List 至始至终只能插入一种类型的数据。
3. ArrayList
   不是类型安全的，而 List 是类型安全的。
4. List 需要在初始化时声明元素类型，而ArrayList不需要。
5. 当不知道往集合存多少，也不知道存什么类型时，用ArrayList；知道往集合存什么类型，不知道存多少个时，用 List。

四、Hashtable

1. Hashtable概述

• Hashtable
   类代表了 基于键的哈希代码组织起来的键/值对集合。
• Hashtable使用键
  来访问集合中的元素

2. Hashtable使用示例

// 定义哈希表
Hashtable hashTable1 = new Hashtable();

void Start()
{
    // 添加元素 键值对
    hashTable1.Add("1", 100);
    hashTable1.Add(1, 99);
    hashTable1.Add(2, 9);
    // 判断是否存在键为“1”的值
    if (hashTable1.ContainsKey("1"))
    {
        Debug.Log("包含key为1的数据");
    }
    // 计算键值对的数量
    int count = hashTable1.Count;
    // 移除元素 key
    hashTable1.Remove("1");
    // 取出指定key的值
    Debug.Log(hashTable1[1]);
    // 修改
    hashTable1[1] = 90;
    // 遍历
    ICollection key = hashTable1.Keys; 
    foreach(var k in key)
    {
        Debug.Log(hashTable1[k]);
    }
    // 清除元素
    hashTable1.Clear();
}

五、字典

1. 字典定义

• 字典，是一个泛型容器，是用于存储键值对数据的集合。

2. 字典使用示例

Dictionary<string, string> dic1 = new Dictionary<string, string>();

void Start()
{
    // 添加键值对
    dic1.Add("1", "100");
    dic1.Add("2", "200");
    dic1.Add("3", "300");
    // 判断键是否存在
    if (dic1.ContainsKey("1"))
    {
        Debug.Log("键存在");
    }
    // 修改值
    dic1["1"] = "1000";
    // 遍历
    foreach(KeyValuePair<string, string> kvp in dic1)
    {
        Debug.Log(kvp.Key + " " + kvp.Value);
    }
    // 移除
    dic1.Remove("2");
    // 清除
    dic1.Clear();
}

六、HashSet

HashSet 是一个包含不重复项的无序列表。

使用示例：

HashSet<int> hashset1 = new HashSet<int>();
HashSet<int> hashset2 = new HashSet<int>();

void Start()
{
    // 添加数据
    hashset1.Add(1);
    hashset1.Add(2);
    hashset2.Add(2);
    hashset2.Add(3);
    // 计算数量
    Debug.Log(hashset1.Count);
    // 集合操作
    // 取交集
    hashset1.IntersectWith(hashset2); 
    // 取并集
    hashset1.UnionWith(hashset2); 
    // 差集：该集合中去除两集合中的交集元素剩下的元素
    hashset1.ExceptWith(hashset2); 
    // 对称差集：两个集合中去除交集元素剩下的元素
    hashset1.SymmetricExceptWith(hashset2); 
    // 遍历
    foreach (var v in hashset1)
    {
        Debug.Log(v);
    }
    // HastSet中没有sort
}

Hashtable 、HashSet 和字典的区别：

• Hashtable
  与Dictionary的区别

1. Hashtable
   不支持泛型，而字典支持泛型；
2. Hashtable
   中 key-value键值对均为 object 类型，故在存储或检索时会发生装箱拆箱操作，性能较差，而字典使用泛型，读取性能更好。
3. 单线程
   程序中推荐使用 Dictionary, 有泛型优势, 且读取速度较快, 容量利用更充分。
   多线程程序中推荐使用 Hashtable, 默认的 Hashtable 允许单线程写入, 多线程读取。
4. 对 Hashtable 进一步调用 Synchronized() 方法可以获得完全线程安全的类型；
   而 字典 非线程安全, 必须人为使用 lock 语句进行保护, 效率大减。
5. 在通过代码测试的时候发现key是整数型，Dictionary的效率比Hashtable快，
   如果key是字符串型，Dictionary的效率没有Hashtable快。

• HashSet
  
  HashSet<T>

  类主要是设计用来做高性能集运算的，
  例如对两个集合求交集、并集、差集等。
  集合中包含一组不重复出现且无特性顺序的元素，HashSet拒绝接受重复的对象。

七、链表

C# 中的链表一般是 双向链表。

1. LinkedList<T>的特性

• LinkedList<T>无法通过下标查找元素
  ，在查找链表元素时，总是从头结点开始。
• LinkedList<T>
   容量是链表最大包含的元素数，会根据元素增减而动态调整容量。
• LinkedList<T>
   中的每个节点都属于 LinkedListNode<T>类型。
• LinkedList<T>
   的值可以为 null， 并允许重复值。
• LinkedList<T>
   不自带排序方法。
• LinkedList<T>
   查询复杂度为 O(n)，操作复杂度为O(1)。

2. LinkedList<T> 使用示例

// 定义双向链表
LinkedList<int> linkList = new LinkedList<int>();
LinkedListNode<int> node;

void Start()
{
    // 在头部添加值
    node = linkList.AddFirst(1);
    // 在某个节点后添加值
    linkList.AddAfter(node, 2);
    // 在节点前添加值
    linkList.AddBefore(node, 0);
    // 在尾部添加值
    linkList.AddLast(3);

    // 打印链表的长度
    Debug.Log(linkList.Count);
    // 打印链表头节点的值
    Debug.Log(linkList.First.Value);
    // 打印链表尾节点的值
    Debug.Log(linkList.Last.Value);
    // 打印前一个节点的值
    Debug.Log(node.Previous.Value); // 0
    // 打印当前节点的值
    Debug.Log(node.Value); // 1
    // 打印后一个节点的值
    Debug.Log(node.Next.Value); // 2
}

八、堆栈

栈Stack 先进后出的对象集合

1. 堆栈使用示例：

// 定义
Stack st1 = new Stack();

void Start()
{
    // 入栈
    st1.Push("a");
    st1.Push("b");
    st1.Push("c");
    st1.Push("d");
    // 计算栈内元素数量
    Debug.Log(st1.Count);
    // 出栈
    string p = (string)st1.Pop();
    Debug.Log(p);
    // 获取栈顶元素的值，但不会出栈
    string peek = (string)st1.Peek();
    // 遍历
    foreach(var v in st1)
    {
        Debug.Log(v);
    }
}

2. 实现栈

// 实现栈
class MyStack
{
    class StackData
    {
        public StackData nextItem;
        public object topData;
        public StackData(StackData next, object data)
        {
            this.nextItem = next;
            this.topData = data;
        }
    }

    StackData top;
    public void Push(object data)
    {
        top = new StackData(top, data);
    }
    public object Pop()
    {
        object rs1 = top.topData;
        top = top.nextItem;
        return rs1;
    }
}
// 验证
private void Start()
{
    MyStack ms = new MyStack();
    ms.Push(1);
    ms.Push(2);
    ms.Push(3);

    Debug.Log(ms.Pop());
    Debug.Log(ms.Pop());
    Debug.Log(ms.Pop());
}

九、队列

队列Queue 先进先出的对象集合

1. 队列的使用示例：

// 声明队列，未指定类型故使用Object
Queue queue_1 = new Queue();
// 指定特定类型，减少装箱拆箱操作
Queue<int> queue_2 = new Queue<int>();

void Start()
{
    // 入队
    queue_1.Enqueue("1");
    queue_2.Enqueue(1);
    queue_2.Enqueue(2);
    queue_2.Enqueue(3);
    // 出队
    int q = queue_2.Dequeue();
    // 遍历
    foreach(var v in queue_2)
    {
        Debug.Log(v);
    }
    // 清空队列
    queue_2.Clear();
}

2. 实现队列

// 实现队列
class MyQueue
{
    class QueueData
    {
        public QueueData nextItem;
        public object topData;

        public QueueData(QueueData last, object data)
        {
            last.nextItem = this;
            this.topData = data;
        }
        public QueueData(object data)
        {
            this.topData = data;
        }
    }

    QueueData top;
    QueueData lastData;
    public void Enqueue(object data)
    {
        if (top == null)
        {
            top = new QueueData(data);
            lastData = top;
        }
        else
        {
            lastData = new QueueData(lastData, data);
        }
    }

    public object Dequeue()
    {
        object rs1 = top.topData;
        top = top.nextItem;
        return rs1;
    }

}
// 验证
void Start()
{
    MyQueue q = new MyQueue();
    q.Enqueue(1);
    q.Enqueue(2);
    q.Enqueue(3);
    Debug.Log(q.Dequeue());
    Debug.Log(q.Dequeue());
    Debug.Log(q.Dequeue());
}

队列的应用：对象池

阅读原文：原文链接