collections - Where can I learn about the various types of .NET lists?

Question

Does anyone know a good resource to concisely explain the different types of lists available in C# and when their usage is appropriate?

For example, List, Hashtable, Dictionaries etc.

I'm never quite sure when I should be using what.

Answer 1

These aren't all lists, although they're all collections. Here's a quick summary.

Non-generic collections (API is in terms of object. Values types are boxed.

These are mostly in the System.Collections namespace:

• ArrayList: A list of items, backed by an array. Fast random read/write access. Fast add to the tail end, if the buffer doesn't need resizing.
• Hashtable: Map from key to value. Keys are unique, values don't have to be. Uses the GetHashCode method to achieve near O(1) read/write access (aside from nasty cases where all items have the same hash, or the backing store needs rebuilding). Iterating over the key/value pairs gives an unpredictable order. (Well, effectively unpredictable.)
• SortedList: Like a Hashtable, but the entries are always returned in sorted-by-key order. Stored as a list of key/value pairs.
• Stack: Last-in-first-out collection
• Queue: First-in-first-out collection
• Array: Fixed-size O(1) random-access; non-generic, but has strongly typed forms as well

Generic collections. (Strongly-typed API, will not box value types (assuming suitable T).

These are mostly in the System.Collections.Generic namespace:

• List<T>: Like ArrayList
• Dictionary<TKey, TValue>: like Hashtable
• SortedList<TKey, TValue>: like SortedList
• SortedDictionary<TKey, TValue>: like SortedList, but stored as a tree of key/value pairs which gives better performance in many situations. See docs for more detail.
• LinkedList<T>: Doubly linked list (fast access to head and tail)
• Stack<T>: Like Stack
• Queue<T>: Like Queue
• ReadOnlyCollection<T>: Like List<T> but giving a read-only view

Possibly the most important collection interface is IEnumerable (and IEnumerable<T>). This represents a sequence of items much like a Stream represents a sequence of bytes. There is no random access, just forward-reading. LINQ to Objects is based on this, and pretty much all collection types implement it.