.Net Collections

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

Collection

Ordering

Contiguous Storage?

Direct Access?

Lookup Efficiency

Manipulate

Efficiency

Notes

Dictionary

Unordered

Yes

Via Key

Key:

O(1)

O(1)

Best for high performance lookups.

SortedDictionary Sorted No Via Key Key:

O(log n)
O(log n)

Compromise of Dictionary speed and ordering, uses binary search tree.

SortedList

Sorted

Yes

Via Key

Key:

O(log n)

O(n)

Very similar to SortedDictionary, except tree is implemented in an array, so has faster lookup on preloaded data, but slower loads.

List

User has precise control over element ordering

Yes

Via Index

Index: O(1)

Value: O(n)

O(n)

Best for smaller lists where direct access required and no sorting.

LinkedList

User has precise control over element ordering

No

No

Value:

O(n)

O(1)

Best for lists where inserting/deleting in middle is common and no direct access required.

HashSet

Unordered

Yes

Via Key

Key:

O(1)

O(1)

Unique unordered collection, like a Dictionary except key and value are same object.

SortedSet

Sorted

No

Via Key

Key:

O(log n)

O(log n)

Unique sorted collection, like SortedDictionary except key and value are same object.

Stack

LIFO

Yes

Only Top

Top: O(1)

O(1)*

Essentially same as List<T> except only process as LIFO

Queue

FIFO

Yes

Only Front

Front: O(1)

O(1)

Essentially same as List<T> except only process as FIFO

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s