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

.net, collections

Solution

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.

Problem

Original source