C#数据结构入门（动态数组、泛型列表、字典、栈、队列、双向链表）

动态数组（ArrayList）：

代表了可被单独索引的对象的有序集合。
它基本上可以替代一个数组。但是，与数组不同的是，您可以使用索引在指定的位置添加和移除项目，动态数组会自动重新调整它的大小。它也允许在列表中进行动态内存分配、增加、搜索、排序各项。
实例：

class ArrayList {
static void Main(string[] args)
        {
            ArrayList al = new ArrayList();

            Console.WriteLine("Adding some numbers:");
            al.Add(45);
            al.Add(78);
            al.Add(33);
            al.Add(56);
            al.Add(12);
            al.Add(23);
            al.Add(9);

            Console.WriteLine("Capacity: {0} ", al.Capacity);
            Console.WriteLine("Count: {0}", al.Count);

            Console.Write("Content: ");
            foreach (int i in al)
            {
                Console.Write(i + " ");
            }
            Console.WriteLine();
            Console.Write("Sorted Content: ");
            al.Sort();
            foreach (int i in al)
            {
                Console.Write(i + " ");
            }
            Console.WriteLine();
            Console.ReadKey();
        }
}

泛型列表（List）:

List< T >类是 ArrayList 类的泛型等效类。
该类使用大小可 按需动态增加 的数组实现 IList< T > 泛型接口。

泛型的好处：
它为使用c#语言编写面向对象程序增加了极大的效力和灵活性。
不会强行对值类型进行装箱和拆箱，或对引用类型进行向下强制类型转换，性能得到提高。

    //定义
    List< T > NAME = new List< T >();
    //以一个集合作为参数创建List
    List< T > NAME =new List< T > (IEnumerable< T > collection);      

字典（Dictionary）：

Dictionary< string ,string > 是一个泛型
描述：
1、从一组键（Key）到一组值（Value）的映射，每一个添加项都是由一个值及其相关连的键组成
2、任何键都必须是唯一的
3、键不能为空引用null（VB中的Nothing），若值为引用类型，则可以为空值
4、Key和Value可以是任何类型（string，int，custom class 等）
他本身有集合的功能有时候可以把它看成数组
他的结构是这样的：Dictionary<[key], [value]>
他的特点是存入对象是需要与[key]值一一对应的存入该泛型
通过某一个一定的[key]去找到对应的值
举个例子：

//实例化对象
Dictionary<int, string> dic = new Dictionary<int, string>();
//对象打点添加
dic.Add(1, "one");
dic.Add(2, "two");
dic.Add(3, "one");
//提取元素的方法
string a = dic[1];
string b = dic[2];
string c = dic[3];
//1、2、3是键，分别对应“one”“two”“one”
//上面代码中分别把值赋给了a,b,c
//注意,键相当于找到对应值的唯一标识，所以不能重复
//但是值可以重复

栈（Stack）和 队列（Queue）：

栈（Stack）：
代表只有一个出口后进先出对象集合，栈只能在一端插入和删除数据，栈进行遍历时，会开辟临时空间，比较耗费性能

 Stack st = new Stack();
 st.Push(1);
 st.Push("nihao");
 st.Push(3);

  foreach (var item in st)
  {
      Console.Write(item+"\t");
  }
  Console.WriteLine();
  Console.WriteLine(st.Peek());
  st.Pop();
  Console.WriteLine(st.Peek());

  Console.ReadKey();

队列（Queue）：
代表一个先进先出的对象集合，队列只能在一端进行插入操作，在另一端进行删除操作，队列是通过地址指针进行遍历的，只能从头或者从尾开始遍历，但不能同时开始遍历，无需开辟临时空间

Queue qu = new Queue();
qu.Enqueue(1);
qu.Enqueue("w");
qu.Enqueue(2);
qu.Dequeue();
qu.Peek();
string str = "qwer";
Console.WriteLine(str.Substring(0,1)); 
Console.WriteLine(qu.Peek());

双向链表（LinkedList）：

里面每个元素都是一个LinkedListNode

List:返回该节点所在的集合
Next:返回下一个节点
Previous:返回上一个节点
Value:返回存储数据
属性：
Count——–返回元素个数
First——返回链表中第一个节点
Last——返回链表中最后一个节点
方法：
AddFirst(T value)——在第一个位置添加一个节点，并把value保存到节 点中
AddLast(T value)——-在尾部添加一个节点，并把value存储到该节点中
Remove(T value)——删除查找到的第一个元素
RemoveFirst()——删除第一个节点
RemoveLast()——删除最后一个节点 C
ontains(T value)——-检索value是否存在，存在返回true，否则返回 false
Find(T value)——返回第一个检索到存储了value的节点
FindLast(T value)——返回最后一个检索到存储了value的节点
AddAfter(LinkedListNode node,LinkedListNode newnode) ——-在node后面添加一个newNode;
AddBefore(LinkedListNode node,LinkedListNode newnode)—– 在node前面添加一个newNode
AddFirst(node)——在第一个位置添加一个节点
AddLast(node)——在最后一个位置添加一个节点
Rmove(node)——删除指定节点

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _集合和索引器
{
    /// <summary>
    /// 链表节点
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class BdNode<T>
    {
        public T Data { get; set; }
        public BdNode<T> Next { get; set; }
        public BdNode<T> Prev { get; set; }
        public BdNode(T data, BdNode<T> next, BdNode<T> prev)
        {
            Data = data;
            Next = next;
            Prev = prev;
        }

    }
    class DoubleLink<T>
    {
        //表头
        private readonly BdNode<T> _linkHead;
        //节点个数
        private int _size;
        public DoubleLink()
        {
            _linkHead = new BdNode<T>(default(T), null, null);//双向链表 表头为空
            _linkHead.Prev = _linkHead;
            _linkHead.Next = _linkHead;
            _size = 0;
        }
        public int GetSize() => _size;

        public bool IsEmpty() => (_size == 0);
        //通过索引查找
        private BdNode<T> GetNode(int index)
        {
            if (index < 0 || index >= _size)
                throw new IndexOutOfRangeException("索引溢出或者链表为空");
            if (index < _size / 2)//正向查找
            {
                BdNode<T> node = _linkHead.Next;
                for (int i = 0; i < index; i++)
                    node = node.Next;
                return node;
            }
            //反向查找
            BdNode<T> rnode = _linkHead.Prev;
            int rindex = _size - index - 1;
            for (int i = 0; i < rindex; i++)
                rnode = rnode.Prev;
            return rnode;
        }
        public T Get(int index) => GetNode(index).Data;
        public T GetFirst() => GetNode(0).Data;
        public T GetLast() => GetNode(_size - 1).Data;
        // 将节点插入到第index位置之前
        public void Insert(int index, T t)
        {
            if (_size < 1 || index >= _size)
                throw new Exception("没有可插入的点或者索引溢出了");
            if (index == 0)
                Append(_size, t);
            else
            {
                BdNode<T> inode = GetNode(index);
                BdNode<T> tnode = new BdNode<T>(t, inode.Prev, inode);
                inode.Prev.Next = tnode;
                inode.Prev = tnode;
                _size++;
            }
        }
        //追加到index位置之后
        public void Append(int index, T t)
        {
            BdNode<T> inode;
            if (index == 0)
                inode = _linkHead;
            else
            {
                index = index - 1;
                if (index < 0)
                    throw new IndexOutOfRangeException("位置不存在");
                inode = GetNode(index);
            }
            BdNode<T> tnode = new BdNode<T>(t, inode, inode.Next);
            inode.Next.Prev = tnode;
            inode.Next = tnode;
            _size++;
        }
        public void Del(int index)
        {
            BdNode<T> inode = GetNode(index);
            inode.Prev.Next = inode.Next;
            inode.Next.Prev = inode.Prev;
            _size--;
        }
        public void DelFirst() => Del(0);
        public void DelLast() => Del(_size - 1);
        public void ShowAll()
        {
            Console.WriteLine("******************* 链表数据如下 *******************");
            for (int i = 0; i < _size; i++)
                Console.WriteLine("(" + i + ")=" + Get(i));
            Console.WriteLine("******************* 链表数据展示完毕 *******************\n");
        }
    }
    class Text
    {
        public static void _main()
        {

        }
    }
}

SortedDictionay< key,value >

有序的键值对集合，跟字典非常相似； 

SortedList< key,value >

有序的键值对集合，内部存储用数组存储 

SortedSet< T >

有序集合，非关联性集合