How to Implement a LinkedList in C#

In this article, we are going to explore the main concepts behind a linked list. We are going to see how to implement a LinkedList in C# using the LinkedList and LinkedListNode classes and then, how to implement custom linked list classes and methods.

We have a lot to cover, so let’s start.

What is a Linked List?

A linked list is a data structure to store items in a linear way. It is composed of nodes that connect with the next and previous items.

The .NET Framework provides us with the LinkedList generic class under the System.Collection.Generic namespace. This class represents a doubly linked list. It means that any node points to a previous and a next node where the previous and/or the next can be null. It is slightly different from the singly linked list, where each node point only to the next node. 

This class implements the ICollection interface, hence, it contains methods like Remove(), Clear(), CopyTo(), and properties such as Count and IsReadOnly.

As with every linked list, this class works with nodes and .NET has a LinkedListNode generic class to represent it.

LinkedList<T> Constructors

The LinkedList class has three constructors. Let’s check them:

Constructor	Description
LinkedList()	Initializes an empty LinkedList.
LinkedList(IEnumerable)	Initializes a LinkedList with the elements of parameter IEnumerable.
LinkedList(SerializationInfo, StreamingContext)	Initializes an empty LinkedList with SerializationInfo and StreamingContext instances to specify how to serialize the LinkedList.

For this article, we are going to initialize an empty LinkedList of int:

var linkedList = new LinkedList<int>();

LinkedList<T> Properties

The .NET LinkedList class has three properties:

Property	Description
Count	An integer that represents the number of nodes in the linked list instance.
Last	A LinkedListNode that represents the last node within the linked list instance.
First	A LinkedListNode that represents the first node within the linked list instance.

It is good to mention that when we insert or remove any LinkedListNode<T> from the list, the insertion/removal method updates the Count property.  That said, when we need this information, it is not necessary to loop through the entire list by counting the number of elements.

Also, it is worth mentioning that the First and the Last property always updates when we insert/remove a node at the beginning or at the end of the list.

LinkedList<T> Main Methods

The LinkedList<T> class contains several methods. For this article, we are going to learn how to use the seven main methods from this class.

Add a Value Using the AddFirst() Method

Let’s use the AddFirst() method:

linkedList.AddFirst(1);

This method replaces the linked list’s first position with the new value, making the old first element the second node in the list.

The AddFirst() method provides us with an overload in case we need to insert a LinkedListNode instead of a value. Let’s check how to use this overload:

linkedList.AddFirst(new LinkedListNode<int>(2));

When we call the method passing a value as a parameter, the AddFirst() method returns the LinkedListNode created to insert. On the other hand, when we provide a LinkedListNode instance, it has no return.

Let’s see our list’s elements after these two insertions:

==> 2 ==> 1

Use the Find() Method

Now we have two elements in our linked list, let’s use the Find() method to find any node inside our linked list:

var node = linkedList.Find(2);

This method returns a LinkedListNode with the element we want to retrieve. If the element doesn’t exist in our list, this method returns null.

Insert a Value With the AddAfter() Method

Now that we know how to find any element inside our linked list, let’s add the third element after the value 2, using the AddAfter() method:

var node = linkedList.Find(2);
if (node is not null)
    linkedList.AddAfter(node, 3);

Once we want to add a new element after the value 2, first we need to find the LinkedListNode with this value. Then, after checking if this value is not null, we use the method AddAfter() method passing as a parameter the LinkedListNode we found and the value we want to insert.

Let’s check the results:

2 ==> 3 ==> 1

Add a Value With the AddBefore() Method

Very similar to the AddAfter() method, we have the AddBefore() method. Let’s check it:

var node = linkedList.Find(1);
if (node is not null)
    linkedList.AddBefore(node, 4);

This time, we are going to insert the value 4 before the value 1. To accomplish it, we need to find the value 1, then, use the AddBefore() method to insert the value 4.

==> 2 ==> 3 ==> 4 ==> 1

Add a Value With the AddLast() Method

Let’s add a new element in our linked list’s last position:

linkedList.AddLast(5);

Now, let’s check our list’s elements:

==> 2 ==> 3 ==> 4 ==> 1 ==> 5

Remove Elements From the Linked List

Let’s check how to remove elements from our linked list:

linkedList.Remove(1);

This method is going to remove the first occurrence from the linked list. Once it successfully removes the element from the list, it returns true, otherwise, if the list doesn’t contain the element we want to remove, this method returns false. 

After removing the element, let’s check the result:

==> 2 ==> 3 ==> 4 ==> 5

Clear the Entire Linked List

Now that we have a linked list full of elements, let’s remove every element from it:

linkedList.Clear();

This method removes all nodes from the linked list. From now, our linked list is empty.

Implement a Custom Linked List in C#

Now that we know how the LinkedList<T> and LinkedListNode<T> classes work in C#, let’s implement our own custom linked list.

We are going to separate it into pieces and implement class by class.

Create the Node<T> Class

Let’s start by creating the Node generic class:

public class Node<T>
{
    public T Value { get; set; }
    public Node<T>? Next { get; set; }
    public Node<T>? Prev { get; set; }

    public Node(T value)
    {
        Value = value;
    }
}

Here we have the Value public property representing the value we want to store within the node. The Next property represents the next node from our linked list and the Prev property represents the previous node.

Note that the Next and Prev property must be nullable, because, in a doubly linked list, the Prev property from the first node and the Next property from the last node points to null.

Custom Linked Class and IEnumerable Interface Members

Now that we have the generic Node class, let’s create the CustomLinkedList class:

public class CustomLinkedList<T> : IEnumerable<Node<T>>
{
    public Node<T>? First { get; set; }
    public int Count { get; set; }
    
    public IEnumerator<Node<T>> GetEnumerator()
    {
        Node<T>? currentNode = First;

        while (currentNode is not null)
        {
            yield return currentNode;
            currentNode = currentNode.Next;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Once we are talking about a list, we probably want to use it inside a foreach loop and System.Linq methods. For that, we are going to implement the IEnumerable interface methods.

Also, it is necessary to create at least two properties, a nullable First property representing the first node from the linked list and an integer Count, representing the number of elements within the list.

Next, let’s implement a couple of methods in our CustomLinkedList class.

Implement the AddFirst() Method

Let’s implement a method to add an element to our list first position:

public void AddFirst(Node<T> nodeToAdd)
{
    if (First is null)
    {
        First = nodeToAdd;
    }
    else
    {
        nodeToAdd.Next = First;
        First.Prev = nodeToAdd;

        First = nodeToAdd;
    }

    Count++;
}

This method receives, as a parameter, the node we want to insert into the list. To begin, we need to check if the First property is null. In case it is null, we know that our list is empty, so, the First property becomes the node we want to insert into the list.

In case our list already has elements, first, it is necessary to make the Next property from the node (parameter) point to the first node from our list. Secondly, we need to make the Prev property from the First property point to the node we receive as a parameter. To finish, we need to make our list’s first node becomes the node we receive as a parameter.

Once we are done adding elements to our list, we need to increase the Count property by one.

Create the Find() Method

Now, let’s retrieve an element from the list:

public Node<T>? Find(T valueToFind)
{
    var aux = First;

    while (aux is not null)
    {
        if (EqualityComparer<T>.Default.Equals(aux.Value, valueToFind))
        {
            return aux;
        }

        aux = aux.Next;
    }

    return default;
}

In the first step, we create an auxiliary variable (aux) to represent the list’s first element.

In the second step, we create a while loop to iterate through the list comparing the current element with the value we want to retrieve. Once we find the element with the same value, we return it. In case we don’t find any element with the same value, we return default (null). 

Remove Elements

Now that we know how to find a value from the list, let’s implement a Remove() method:

public void Remove(T valueToRemove)
{
    var find = Find(valueToRemove);

    if (find is null)
    {
        return;
    }

    var next = find.Next;
    var prev = find.Prev;

    if (prev is not null)
    {
        prev.Next = next;
    }

    if (next is not null)
    {
        next.Prev = prev;
    }

    Count--;
}

This method receives, as a parameter, the value we want to remove from the list.

The first step consists of finding the first node with the value within our list. The Find() method may return null, so we need to check if the value we want to remove exists within the list.

As the next step, we are assigning the next and the previous value inside two variables (next, prev).

If the prev variable is null, it means that we are at the list’s first position. That said, we don’t need to do anything with the prev node.

In the same way, if the next variable is null, we are dealing with the list’s last position, so, no action is necessary with the next node.

Once the prev variable is not null, we need to assign the next variable to the prev.Next node. Likewise, we need to assign prev variable to the next.Prev node.

Then, as we removed a node from the list, we need to decrease the Count property by one. 

You can check the full CustomLinkedList implementation here.

Conclusion

In this article, we have learned that a linked list is a data structure to store items in a linear way and the linked list composition.

Then, we learned that .NET Framework provides us with a full linked list implementation with the LinkedList class. We studied the main methods, properties, and constructors.

Additionally, we created our own Node and CustomLinkedList classes and implemented a couple of methods.