[C#] 主要容器及其数据结构

C# 容器可以分为无Generic时代 和 Generic时代。Generic是C# 2.0时的产物。

在System.Collections.Generic，也就是泛型命名空间出现以前。常用的是System.Collections 命名空间下的容器，包括ArrayList，Stack, SortedList, Queue等等。这些容器有一个共同特点：其存储的元素都是object。这就意味着，比如ArrayList，它可以同时存放各种类型的数据，因为所有的类型都会转化为object存储，访问元素时会自动提出数据。这样的过程，我们称其为“装箱”和“拆箱”(boxing and unboxing)。

因此，System.Collections中的容器好处在于：不是严格类型的，可以放不同类型的值。坏处在于：因为对存放数据没有类型要求，所以不是类型安全的；另外，装箱和拆箱会是一个很耗费时间的工作。

arraylist vs List<> in c#

http://stackoverflow.com/questions/2309694/arraylist-vs-list-in-c-sharp

List is a generic class. It supports storing values of a specific type without casting to or from object (which would have incurred boxing/unboxing overhead when T is a value type in the ArrayList case). ArrayList simply stores object references. As a generic collection, it implements the generic IEnumerable interface and can be used easily in LINQ (without requiring any Cast or OfType call).

ArrayList belongs to the days that C# didn't have generics. It's deprecated in favor of List. You shouldn't use ArrayList in new code that targets .NET >= 2.0 unless you have to interface with an old API that uses it.

引申出generic。

引申出LINQ，

List 等属于 Generics，Arraylist等属于早期的容器

The List class is the generic equivalent of the ArrayList class. It implements the IList generic interface by using an array whose size is dynamically increased as required.

我们都知道List的Add是O(1)的操作，但之所以它是O(1)，是因为它的“扩容”操作被均摊了（amortized），但每次扩容时其实还是需要复制所有元素，次数越少越好

http://blog.zhaojie.me/2013/01/think-in-detail-why-its-o-1.html

In deciding whether to use the List or ArrayList class, both of which have similar functionality, remember that the List class performs better in most cases and is type safe. If a reference type is used for type T of the List class, the behavior of the two classes is identical. However, if a value type is used for type T, you need to consider implementation and boxing issues.

来自http://msdn.microsoft.com/en-us/library/6sh2ey19(v=vs.110).aspx

衍生出装箱和拆箱。。。

Benefits of Generics

http://msdn.microsoft.com/en-us/library/b5bx6xee.aspx

LINQ Query

http://www.cnblogs.com/greenerycn/archive/2010/10/22/linq_intro.html