Introduction to Linked Lists in C#

If you are familiar with the concept of pointers, then you probably won’t have any problems understanding the principles by which linked lists work.
Basically, a linked list is an array of objects that however, is quite different from a simple array. A regular array allocates a specific part of the memory automatically. Let’s look at an example:

string[] dataSet = new string[100];for (int i = 0; i < 99; i++){    dataSet[i] = string.Format("Sample Data {0}", i.ToString());}

This code allocates space for 100 string items and fills each one of them with a string. However, there are a few drawbacks in the regular array. What if there are more than 100 items used later on? The array needs to be extended, and if it was hardcoded to a hundred values, there could be some problems with overflowing data. Another problem is the inefficient memory usage when there are less than a hundred elements. In that case, a lot of memory is kept unused.

Linked lists tend to solve the two of the above problems. First of all, a linked list doesn’t have a single field for a value, but rather two – one with the stored data and one referencing the next value. These two fields together build a node, that is – a unit inside the linked list.

Values aren’t stored in any particular order, however the reference to the next value helps finding and inserting the needed values much easier.

In C#, linked lists are handled via the LinkedList<T> class, that contains multiple LinkedListNode<T> instances. After disassembling the LinkedListNode<T>, there is an interesting thing seen:

Take a look at the highlighted fields - in .NET, a linked list node not only keeps a reference to the next node, but also to the previous node. In this case, the linked list scheme shown above would look like this:

Since values 1 and 6 are the limits of the list, for the first element the previous node is equal to NULL, and for the last element the next node is equal to NULL.
To instantiate a linked list, you can use the following code:

LinkedList<string> list = new LinkedList<string>();

The LinkedList<T> class represents a generic collection (member of the System.Collections.Generic namespace), therefore it is safely typed – when used, the developer is aware of the type of the elements inside it.

Since elements are added without an order, every node needs a reference. Initially, you can add nodes via the AddFirst and AddLast methods. For example:

list.AddFirst("Data Value 1");list.AddLast("Data Value 6");

Even if there is already a first and last element, the new node will replace the existing one and the list will adjust accordingly. To prove this, try this code:

list.AddFirst("Data Value 1");list.AddFirst("Data Value 2");LinkedListNode<string> node = list.Find("Data Value 1");Debug.Print(node.Previous.Value.ToString());

Since the node containing “Data Value 2” is placed first, the node containing “Data Value 1” is moved to the second spot. Therefore, the Previous property is automatically set to the new node that was inserted.

Same applies to the AddLast method, although the Next property will be the one modified.

When you want to add nodes between the first and last, you can use the AddBefore and AddAfter methods. AddBefore will add a node before the LinkedListNode instance that you are going to pass and AddAfter will add a node after it.

A way to specify the initial node, that will be considered for the Previous property assignment, the Find and FindLast methods can be used. Find finds the first occurring instance of the node and FindLast finds the last instance of the occurring node, since nodes can have the same value.

Here is a sample on how to use the methods mentioned above:

list.AddAfter(list.Find("Data Value 1"), "Data Value 2");

You have to be very careful when you are looking for a node since if you don’t specify the correct searched value, a null value will be returned and this will cause an exception, since the value cannot be null.

Since the list is not sorted and the values are added dynamically, there is no way to get them by the index, since no actual index value exists for nodes. The only way to find a value is by using the linear search, and that is provided by the Find and FindLast methods.