C#之LinkedList使用以及常用容器类

may

LinkedList是很好用的一个工具，可以方便做出前后关系

1. using System;
   
2. using System.Collections.Generic;
   
3. 
   
4. namespace ConsoleApplication
   
5. {
   
6.     class Program
   
7.     {
   
8.         static void Main(string[] args)
   
9.         {
   
10.             LinkedList<int> a = new LinkedList<int>();
    
11.             a.AddFirst(3);
    
12.             a.AddLast(1);
    
13.             a.AddLast(4);
    
14. 
    
15.             foreach (int i in a)
    
16.                 Console.Write(i + " ");
    
17.             Console.WriteLine();
    
18. 
    
19.             LinkedListNode<int> cur = a.Find(3);  //cur对应3所在的位置
    
20.             a.AddBefore(cur, 2);                //在3前面添加2
    
21. 
    
22.             foreach (int i in a)
    
23.                 Console.Write(i + " ");
    
24. 
    
25.             a.Remove(3);
    
26.             a.Clear();
    
27.             Console.Read();
    
28.         }      
    
29.     }
    
30. }

复制代码

插入：O(1) （在头尾部），O(N) （在其他位置）

删除：O(1) （在头尾部），O(N) （在其他位置）

按照索引器访问：没有索引器（因为没有实现IList<T>）

查找：O(N)

除此之外，还有SortedList<K,T>和SortedDictionary<K,T>这两个，是用于排序频繁发生的时候，排序成本O(ln(N))

一些可能会用到的容器类：

线性表和链表（使用最多的对象）：

• Array (T[])：当元素的数量是固定的，并且需要使用索引器时。
• Linked list (LinkedList<T>)：当元素的数量不是固定的，且存在大量列表的头尾添加的动作时。否则使用 List<T>。
• Resizable array list (List<T>)：当元素的数量不是固定的，并且需要使用索引器时。
  

栈和队列（只有在模拟栈和队列时才考虑）：

• Stack (Stack<T>)：当需要实现 LIFO（Last In First Out）时。
• Queue (Queue<T>)：当需要实现 FIFO（First In First Out）时。
  

哈希（需要大规模查找）：

• Hash table (Dictionary<K,T>)：当需要使用键值对（Key-Value）来快速添加和查找，并且元素没有特定的顺序时。有了泛型版本的字典，我们几乎永远不需要使用非泛型的HashTable。
• Tree-based dictionary (SortedDictionary<K,T>)：当需要使用键值对（Key-Value）来快速添加和查找，并且元素总是需要根据 Key 来排序时。
  

集合（保存一组唯一的值/模拟集合运算）：

• Hash table based set (HashSet<T>)：当需要保存一组唯一的值，并且元素没有特定顺序时。
• Tree based set (SortedSet<T>)：当需要保存一组唯一的值，并且元素总是需要排序时。
  

來自：cony138