Performance Implications on Collections

When you want additions, removals, and lookups to be very quick, and when you are not concerned about the order of the items in the collections, your first inclination should be to use a System.Collections.Generic.Dictionary.

On the other hand, with a List, inserting and removing items can take a variable amount of time. (List stores items in an underlying array that maintains order. If your usage pattern requires few deletions and mostly additions, and if it is important for you to keep the collection in order, you may still want to choose a List.

Using the new LinkedList collection can potentially help you improve performance in scenarios where you need to maintain order yet still achieve fast inserts. Unlike List, LinkedList is implemented as a chain of dynamically allocated objects. In comparison to List, inserting an object in the middle only requires updating two connections and adding the new item. The downside of a linked list from a performance point of view is increased activity by the garbage collector as it has to traverse the entire list to make sure objects were not disposed of. Additionally, performance problems can arise with large linked lists due to the overhead associated with each node as well as where in memory each node lives.

SortedDictionary, uses a balanced tree implementation as the underlying data store; this provides relatively fast lookups and maintains items in a sorted order, but insertions will most likely be slower.

From CLR Inside Out: Collections Best Practices by Inbar Gazit.