C# Programming > Data

C# Data Structures

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.

In this article I will go over the built-in C# data structures, including the new ones introduces in C#.NET 3.5. Note that many of these data structures apply for other programming languages.

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 (in most cases) and there is a specific number of them. The nature of an array allows for very fast access to elements based on their position within the list (otherwise known as the index). 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 be intialized with no elements or from a set of existing values. Inserting values into an array is simple as long as they fit. The operation becomes costly when there are more elements than the size of the array, at which point the array needs to be expanded. This takes longer because all the existing elements must be copied over to the new, bigger array.

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. This data structure was designed to simplify the processes of adding new elements into an array. Under the hood, an ArrayList is an array whose size is doubled every time it runs out of space. Doubling the size of the internal array is a very effective strategy that reduces the amount of element-copying in the long run. We won't get into the proof of that here. The data structure is very simple to use:

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 was introduced in the .NET Framework 2.0 as part of the new set of generic collections. List is the generic version of ArrayList, which means that it behaves exactly the same way, but within a specified type. So for example, a List of integers would work as follows:

List<int> intList = new List<int>();
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];

This results in much cleaner, and in my times, faster code. This is especially true when working with primative types. Unless you are using the .NET Framework 1.1, you should always use List over ArrayList. (Note that List<Object> is perfectly legal, although it defeats the purpose of having a generic dynamic array collection).

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 much faster 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<int> list = new LinkedList<int>();
list.AddLast(6);

Retrieving a value is not as straight forward:

list.First.Value 
or
list.Last.Value

Since inserting and removing elements is done by updating a couple references, they can be done in constant time. The tradeoff is that accessing elements is no longer a constant time operation. In an array, with a given index an element can be instantly accessed. With a linked list, the references between nodes need to be followed until the desired element is found.

With that we can move on to more complex data structures.

Continue C# Data Structures - Page 2
Dictionary, Hashtable, HashSet >>>

 

Back to C# Article List