Here we are going to talk about algorithms and data structures using CSharp. Here we will see the most common data structures used in the programming languages and the algorithms that are associated with these data structures. Let’s start off with the most basic nodes and linked list data structure.

Nodes and Nodes Chain

This is the basic building block of most of the data structures we will be seeing here. We will then see how these nodes link up together to form the Node chains and then how these node chains form the basics of the Linked Lists. We will also see Linked list and extensions of Linked list and how the linked list is structured in .NET.

The node provides two functions

• It provides a mechanism to hold a piece of data.
• It provides a mechanism to hold the object reference of the next node. Also known as the Next pointer for the Node.

As we can see in the image below we have a Node with value 3 and a next pointer which is currently pointing to nothing.

C# Node

Now let’s create another node with value 5. The next pointer of this node is null as well.

C# Node

Now if you join these nodes and set the next pointer of the first node as the second node we could see something like below.

C# Node Chain

Let’s create another node and link the next pointer of the second node to the third node.

C# Node Chain

We have seen above this will work functionally. Now let’s write some code for the same.

Create a new console project named Nodes Application. Create a class named Node with the following code. As we saw the above the node class has 2 responsibilities: to hold a value (an integer in this case) and a pointer to the next node in the chain.

C# Node Class

Now let’s use the node class to create the first node and the second node. So we have node with value 1 and a null next pointer and a second node with value 2 and a null next pointer

C# Create Node

But these nodes are still not a chain. To make these nodes as a chain we need to create set the next pointer of the first node as the second node.

C# Set Node Next Pointer

Now let’s create the third and node and set the next pointer of the second node to this third node.

C# Set Node Next Pointer

As we have the chain of 3 nodes now, let’s print the nodes. We pass the first node as the parameter to the print method and enumerate and print through it till the next reference of the node becomes null.

C# print Node Chain

Let’s call this print method.

C# print Node Chain

The result that we will see on running the application is as below.

C# print Node Chain

Linked Lists

A Linked List is a single chain of nodes. Linked list have a well-known starting point known as the head and the list provides the pointer to the first node of the list. Linked list also exposes a pointer to the last node of the list known as the tail. And also liked list provides operations that allow linked list to be managed, searched and enumerated. These are the operations make the list truly useful as a collection.

Add to Front

The first operations that you are most likely to perform on the list is adding and item to the list, so let’s have a look as to how we can an item to the front of the list. We would start from an empty linked list. A linked list is nothing but a single node chain with head and tail pointers initially set as null. The first step to adding a node is allocating the value to the node. Let’s assume we have assigned a value of 3 to the node. Now next thing to do is to point the head and tail of the linked list to this node as the list has only one item

LinkedList Add To Front

Now if we add another node at the front of this Linked list then we need to do 2 things.

• Assign the next pointer of the new node to the node after it.
• Set the head pointer to this node as this node is added at the front of this list.

We are adding the node to the end of the list so we do not need to change the tail pointer of the list.

LinkedList Add To Front

Let’s have a look at the code for this. The first thing that we do is store the head node into a temporary variable and then point the head pointer to the new node being added to the front of the list. Also we point the next pointer of the head node to the temp so that the rest of the list added behind the new node. If the linked list has only one node then the node has the same pointer as tail.

LinkedList Add To Front Code

This operation is very easy and the complexity of this operation is constant no matter how many nodes exist. If this was an array then this operation would be very complex as each item would be moved to the next position.

Add to End

The process of adding a node to the end is similar to adding to the front. The difference here is that when we are adding the second node we need to set the tail pointer instead of the head pointer.

LinkedList Add To End

Let’s see the code for this. There are only 2 cases if a new node is added to the empty list or non-empty list.

• If the list is empty we point the head pointer to the node.
• If the list is not empty then the node being added is added to the end.

In either case the tail pointer points to the added node and the counter which keeps track of the number of nodes in the list.

LinkedList Add To End Code

Remove at the End

Like add the node can be removed from the front or the end. Let’s take an example of the list which has 3 elements as shown below. To remove 7 from the list we need to node and delete all references to the node as well. This seems simple.

LinkedList Remove at End

The way that it will look after the removal of the 7 node is as below.

LinkedList Remove at End

Let’s see the code for removing the element at the end of the list. We need to update the second last element in the list and this will require us to iterate through the list and this operation will increase in complexity along with the number of elements in the list.

LinkedList Remove at End Code

Remove at the Front

Remove a node from the front is fairly simple as it just involves setting the head pointer of the list to the second node.

LinkedList Remove at Front Code

Enumerating a List

Another major operation in the list is enumeration. Enumerating over the list done very frequently as most of the time you are not dealing with the first element in the list. The key to enumeration is have a next pointer available to the next node. Lets enumerate the list as shown below.

Enumerating a List

Let’s have a look at the code. We will use the Get Enumerator pattern using the C# yield syntax. In the while loop we keep track of the next node in a local variable named current. When the while loop starts then the current is set the first node of the list and since it is not null then the value of this node is yielded and the current is set to the next node and the cycle continues till current is null.

Enumerating a List Code

Doubly Linked List

Doubly linked list is quite similar to the Single linked list the only difference is that we have two pointers in the nodes – one having a reference of the next node and one having a reference to the previous node. This makes it easier to add and remove items. It looks something like below.

Doubly Linked List

Let’s see the implementation of a doubly linked list. You would see in the code that the implementation is not a lot different from the singly linked list. The doubly linked list node class just has an additional pointer to the previous node.

Doubly Linked List Code

The implementation of the other method will also change accordingly. You can a look at the code and analyze the same.

Everything we just implemented is present in the .NET generic class named LinkedList.

.NET Linked List Class

The souce code for this post can be found here.