C# Data Structures

Hi,

Array, ArrayList, List, LinkedList, Dictionary, HashSet, Stack, Queue
Data Structures
C#.Net has a lot of different data structures, for example, one of the most common ones is an Array. However C# comes with many more basic data structures. Choosing the correct data structure to use is part of writing a well structured and efficient program.
Array
The perhaps simplest and most common data structure is the array. A C# array is basically a list of objects. Its defining traits are that all the objects are the same type and there is a specific number of them. A C# array is defined like this:
[object type][] myArray = new [object type][number of elements]
Some examples:
int[] myIntArray = new int[5];
int[] myIntArray2 = { 0, 1, 2, 3, 4 };
As you can see from the example above, an array can defined empty or with preset elements.
ArrayList
The C# data structure, ArrayList, is a dynamic array. What that means is an ArrayList can have any amount of objects and of any type.
(Under the hood, the ArrayList is an Object array that is expanded as more items are added.)
ArrayList myArrayList = new ArrayList();
myArrayList.Add(56);
myArrayList.Add("String");
myArrayList.Add(new Form());
The downside to the ArrayList data structure is one must cast the retrived values back into their original type:
int arrayListValue = (int)myArrayList[0];
List<>
The List C# data structure is in short a typed ArrayList. By that I mean it is too a dynamic array, but the different between a List and ArrayList is the List data structure must contain the same type of objects:
List intList = new List();
intList.Add(45);
intList.Add(34);
Since the List<> object is tailored to a specific data type, there is no need to cast when retrieving values:
int listValue = intList[0];
For primative data types (int, bool, etc.) using a List is much faster than ArrayList.
LinkedList<>
Now for a completely different type of C# data structure, the LinkedList. A LinkedList is a series of objects which instead of having their references indexed (like an Array), stay together by linking to each other, in Nodes.
A LinkedList Node has basically three values: the Object's Value, a reference to the Next node, and a reference to the Previous Node.
What is the point of such C# data structure? Well, adding values to the middle of the list is extremely fast compared to any other Array type of data structure. It also keeps memory costs down to a minimum. Lists on the other hand use extra space to make future insertions as fast as possible.
LinkedList list = newLinkedList();
list.AddLast(6);
Retrieving a value is not as straight forward:
list.First.Value or
list.Last.Value
Dictionary<>
The Dictionary C# data structure is extremely useful data structure since it allows the programmer to handle the index keys. What does that mean? Well an ArrayList automatically makes its "keys" integers that go up one by one, 1, 2, etc, so to access a value in an ArrayList one goes like: myArrayList[2];
So what the C# Dictionary data structure does is let us specify the keys, which can be any type of object. For example:
Dictionary myDictionary = new Dictionary();
myDictionary.Add("one", 1);
myDictionary.Add("twenty", 20);
Retrieving a value is pretty straight forward:
int myInt = myDictionary["one"];
Notice how convenient the Dictionary data structure is, in that there is no need to cast between types. Also there is nothing stopping you from creating a Dictionary like so:
Dictionary> nestedDictionary =
new Dictionary>();
That is a nested Dictionary C# data structure and it is fair game.
I understand that it can be confusing on how to go about getting all the values out of a Dictionary data structure since we have no way to knowing the pattern in the keys. Luckily we don't have to, here is the code to transverse a C#.Net Dictionary:
//List<[same type as index]>
List keyList = new List(myDictionary.Keys);
for (int i = 0; i < keyList.Count; i++)
{
int myInt = myDictionary[keyList[i]];

}
You can read about C# Dictionary in a little more detail if you are interested.
Hashtable
The C# Hashtable data structure is very much like the Dictionary data structure. A Hashtable also takes in a key/value pair, but it does so as generic objects as opposed to typed data.
Values are then stored in order according to their key's HashCode. Meaning that the order in which items are added to a C# Hashtable is not preserved. On the other hand, the Dictionary data structure does keep items in the same order.
The reason is speed. A C# Hashtable stores items faster than a C# Dictionary, which sacrifices speed for the sake of order..
(For those Java programmers, a Dictionary is more or less a TreeMap and a Hashtable is a HashMap).
Hashtable myTable = new Hashtable();
HashSet
The HashSet data structure was introduced in C# Net 3.5. This particular C# data structure very strongly resembles the List<> data strucuture.
So what is the difference? A HashSet has the very important characteristic that it does not allow duplicate values. For example:
HashSet mySet = new HashSet();
mySet.Add(3);
mySet.Add(5);
mySet.Add(3);
mySet.Add(10);

List myListFromSet = mySet.ToList();
int myInt = myListFromSet[2];
If mySet were a regular List data structure, the index 2 should return the value 3 (count it out). But if you run the example you will see that myInt actually returns the value 10. This is because the HashSet C# data structure ignored the duplicate addition of the value 3.
Stack
The Stack class is one of the many C# data structures that resembles an ArrayList. Like an ArrayList, a stack has an add and get method, with a slight difference in behavior.
To add to a stack data structure, you need to use the Push call, which is the Add equivalent of an ArrayList. Retrieving a value is slightly different. The stack has a Pop call, which returns and removes the last object added. If you want to check the top value in a Stack, use the Peek call.
The resulting behavior is what is called LIFO, which stands for Last-In-First-Out. This particular data structure is helpful when you need to retrace your steps so to speak.
There are two formats to define a Stack in C#:
Stack stack = new Stack();
Stack stack = new Stack();
The different between the data structures being that the simple Stack structure will work with Objects while the Stack<> one will accept only a specified object.
Here is the C# code to add and traverse through a Stack data structure:
Stack stack = new Stack();
stack.Push("1");
stack.Push("2");
stack.Push("3");

while (stack.Count > 0)
{
MessageBox.Show(stack.Pop());
}
If you run the C# code you see that the list is returned in the order: 3, 2, 1.
Queue
Another one of the many C# data structures is the Queue. A Queue is very similar to the Stack data structure with one major difference.
Rather than follow a LIFO behavior, a Queue data structure goes by FIFO, which stands for First-In-First-Out. Whenever you submit an article to be approved on a website for example, the site adds your submittion to a queue. That way the first objects added are the first ones to be processed.
The Add call for a queue (or the Push version) is Enqueue:
queue.Enqueue("1");
The Remove call is Dequeue:
queue.Dequeue();
Similarly the Peek call allows you to view the top value without removing it. This specific data structure is very often used in conjucture with stack data structures.
Here is some simple C# code to add items to a queue and the transverse it:
Queue queue = new Queue();
queue.Enqueue("1");
queue.Enqueue("2");
queue.Enqueue("3");

while (queue.Count > 0)
{
MessageBox.Show(queue.Dequeue());
}
Also keep in mind the queue data structure can be defined as a general Queue and as a type-specific Queue<>...