How to implement a Linked List in C#

This is a continuation (a very delayed continuation) on my series covering data structures. In this post, we will cover Linked Lists.

What is a Linked List Structure?

Link Lists are a collection of nodes connected in a linear ordering. Each node is an object that stores some piece of data, as well as a reference to the next node in the list.

Unlike arrays, linked lists don't have a fixed size. The space they take up is determined by the number of items in the list. Also, items cannot be accessed by an index in a linked list as they can in an array.

Singly vs Doubly Linked List

There are two types of Linked Lists, Singly and Doubly. Singly is how I described above, with a reference to the next node in the list. Doubly has this same behavior, but additionally each node as a reference to the previous node in the list.

Doubly has the advantage of easier insertion/removal of nodes into the front, middle, and end of the list.

For this post, we will be focusing on Singly Linked Lists. I may have a follow up post later with some examples of Doubly Linked Lists.

The Linked List Node Class

Here is a very simple example of a Node class.

public class Node
{
    public Node Next;
    public string Element;
}

We store the data for this node in a variable named Element, which is just a simple string. The reference to the next node in the list is the variable Next. You will notice that the type of the Next variable is the same type as the class it is a property of. This might seem strange at first. But these references are the "links" in our linked list.

Linked List Class

The singly linked list class contains 3 properties and 4 methods. The properties are Head, Tail, and Count. The Head & Tail nodes track the first and last nodes in the list respectively. The Count property is used to keep track of the number of nodes in the list.

public class LinkedList
{
    public Node Head;
    public Node Tail;
    public int Count;

    public LinkedList()
    {
        head = tail = null;
        count = 0;
    }
...

There are four main methods of a Singly Linked List: AddToFront, AddToEnd, RemoveFromFront, RemoveFromEnd. The first three are fairly straight forward. We will show later how the RemoveFromEnd has a bit more complexity.

Methods of a Linked List

AddToFront method takes the data to be stored in the node as a parameter. We build a new node for the list, assign the value to the element, then tell it that the next node in the list is the node at the head of the list. Then, we make the node we just created the new head of the list. Finally, we increment the count.

    //O(1)
    public void AddToFront(string element)
    {
        var node = new Node();
        node.Element = element;
        node.Next = head;

        head = node;
        count++;
    }

The first half of the AddToEnd method behaves similar to the AddToFront method. We pass the value in then create the node, then assign it.

Next we must add some checks for the instance of an empty list. While adding to the front of an empty list simply creates the new list, trying to add to the end before the head or tail properties are set would cause an exception. If the head is empty, we initialize it and the tail with the newly created node.

    //O(1)
    public void AddToEnd(string element)
    {
        var node = new Node();
        node.Element = element;
        node.Next = null;

        if (head == null)
        {
            head = tail = node;
            count++;
            return;
        } 
        else if (tail == null)
        {
            tail = head;
        }

        tail.Next = node;
        tail = node;
        count++;
    }

The first of the remove functions, RemoveFromFront, first checks the head variable to see if it is null. If it is, we have an empty list, and return null.

Next, we create a temporary variable to store the head node. We do this so we don't lose it once we remove the head from the list. Then, we assign the value in head.Next as the new head of the list. Finally, we set the next in our temporary variable to null, decrement our count, and return the string value from our temp node.

    //O(1)
    public string RemoveFromFront()
    {
        if (head == null)
            return null;

        var tmp = head;
        head = head.next;
        tmp.next = null;
        count--;

        return tmp.Element;
    }

Finally, we have RemoveFromEnd. This function is more complex due to the fact that we do not have references to the previous node from our tail node. This is where a doubly linked list would come in handy.

While we can immediately access the tail of the list through the tail variable, we are not able to take the node before it and set its Next node reference to null. Therefore, we will need to loop through the entire list, starting from the head, until we reach the second to last node. We do this with a while loop.

We then do 2 checks. One to see if the node we assume to be previous to the tail is null. If it is, we have an empty list, so return null. Then, we check if the node after that (the assumed tail) is null. If it is, then we only have one item in the list. We can set the head & tail to null and return the node value.

Finally, we can Next reference to null, and assign our node to be the new tail of the list.

	//Θ(n)
    public string RemoveFromEnd()
    {
        Node current = head;
        while (current?.Next?.Next != null)
        {
            current = current.Next;
        }

        if (current == null)
            return null;

        var result = current?.Next?.Element;
        if (current.Next == null)
        {
            result = head.Element;
            head = null;
            tail = null;
            return result;
        }

        current.Next = null;
        tail = current;

        return result;
    }

Final Thoughts

As with some of the other data structures we went over, you are better off leveraging the Linked List provided with the framework you are using. But, it is always fun to try to implement things on your own once in a while.

But I hope you found this to be a helpful example of seeing how linked lists work under the hood. Please reach out to share your thoughts on this post. And feel free to share this post with others!