.NET has a lot of complex data structures. Unfortunately, some of them are quite similar, and I'm not always sure when to use one and when to use another. Most of my C# and Visual Basic books talk about them to a certain extent, but they never really go into any real detail.
What's the difference between Array, ArrayList, List, Hashtable, Dictionary, SortedList, and SortedDictionary?
Which ones are enumerable (IList -- can do 'foreach' loops)? Which ones use key/value pairs (IDict)?
What about memory footprint? Insertion speed? Retrieval speed?
Are there any other data structures worth mentioning?
I'm still searching for more details on memory usage and speed (Big-O notation).