Monday, June 22, 2009

.NET non-generic collections @ a glance!

Array – IEnumerable, System.Array

Array size is fixed
Can be single dimensional or multidimensional or jagged
All items in the array are of same type (Strongly typed)
Indexed collection

For one-dimensional arrays compilers use built in MSIL code which leads quick and effective processing.
This is the most effective way to keep fixed sized, index based collections.
Value types in an array are stored contiguously in managed heap in its unboxed form.
Reading from and writing to array is very fast because it store data in managed heap contiguously.

Index-based check comes at a slight cost of performance for applications that make a large number of array accesses

ArrayList – IList, System.Collections

Array size is dynamically increased.
Not sorted
Accessed using integer index
Weakly typed collection of objects
Can contain any type of data (as opposed to Arrays)

If the performance does not matter a lot use ArrayList.
Ideal for directly accessing and storing data items
Flexible – so far, no type or size limitations (as opposed to Arrays)

If you only want to handle a collection of specific type it is better to use an array.
Since ArrayList stores items of object type, when you need to read value you have to cast it explicitly.
When storing value types in ArrayList they are boxed and kept as object references in managed heap which degrades performance.

Queue – ICollection, System.Collections

First In First Out collection of objects (FIFO)
Objects are inserted in one end and returned/accesses in the other end
Capacity is increased due to the requirement (ref: growth factor)
Stores heterogeneous elements
Maintains internal circular array
Default capacity – 32 items

Useful for data that requires sequential processing (one element at a time in order)

Limitations on the way data is being accessed (does not allow random access)
Object needs to be cast to its own type instance before use.

Stack – ICollection, System.Collections

Last In First Out collection of objects (LIFO)
Implemented as a circular buffer
Capacity is increased due to the requirement
Count is less than the capacity of the stack, Push is an O(1) operation. If the capacity needs to be increased to accommodate the new element, Push becomes an O(n) operation, where n is Count. Pop is an O (1) operation
Default capacity – 10 items

Computer applications – call stack, parsing

For both Stack and Queue the time needed to add or remove an item is a constant and independent of the number of the items. (Conditions apply!)

SortedList – IDictionary, System.Collections

A collection of key-value pairs which is sorted by keys
Data is accessed by key or index
the index of a specific key/value pair might change as elements are added or removed from the SortedList object
You can access key-value pair using DictionaryEntry object
A hybrid of HashTable and array

If you want your data to be stored in a sorted manner, use this collection.

Usually operations related with SortedList are slower than that of HashTable, yet flexible.

HashTable – IDictionary, System.Collections

Represents a collection of key-value pairs based on the hash code of the key
Each element in the key-value pair can be accessed using a DictionaryEntry object
Both key and the value can be of any type

This should be used when the number of items in the collection is large.
Searching is relatively very fast
All the elements are stored in a contiguous order
Size is limited only by the available disk storage

To be continued...

No comments:

Post a Comment