Navigation

Related Articles

Back to Latest Articles

Everything About Circular Linked Lists In C# – Made Easy

Circular linked lists are an upgrade to generic double linked lists. They can loop around when navigating to adjacent elements.


Andraz Krzisnik
Everything About Circular Linked Lists In C#...

Circular linked lists are an upgrade to double linked lists. In case you don’t know about linked lists, may I suggest you check out the post I made about them. Basically, they are lists which allow us to navigate through elements without using index positions.

In other words, we can use Next and Previous methods to get adjacent elements in it. Furthermore, with double linked lists, method Next on the last element will return null as will method Previous on the first element.

However, this is where circular linked lists differ from double linked lists. This is where we upgrade double linked lists by making them loop around rather than just return null.

Circular linked lists in C#

Unfortunately, this type of lists is not included in the System.Collections.Generic namespace. Therefore, we’re going to need to implement it ourselves. However, we won’t need to do it completely from scratch, because we can still use the LinkedList class for it.

Now, let’s take a look at the code implementation in C#.

public class CircularLinkedList<T> : LinkedList<T>
{
    public new IEnumerator GetEnumerator()
    {
        return new CircularLinkedListEnumerator<T>(this);
    }
}

public class CircularLinkedListEnumerator<T> : IEnumerator<T>
{
    private LinkedListNode<T> _current;
    public T Current => _current.Value;
    object IEnumerator.Current => Current;

    public CircularLinkedListEnumerator(LinkedList<T> list)
    {
        _current = list.First;
    }

    public bool MoveNext()
    {
        if (_current == null)
        {
            return false;
        }

        _current = _current.Next ?? _current.List.First;
        return true;
    }

    public void Reset()
    {
        _current = _current.List.First;
    }

    public void Dispose() { }
}

public static class CircularLinkedListExtensions
{
    public static LinkedListNode<T> Next<T>(this LinkedListNode<T> node)
    {
        if (node != null && node.List != null)
        {
            return node.Next ?? node.List.First;
        }

        return null;
    }

    public static LinkedListNode<T> Previous<T>(this LinkedListNode<T> node)
    {
        if (node != null && node.List != null)
        {
            return node.Previous ?? node.List.Last;
        }
        return null;
    }
}

We can implement it with a generic class which inherits the LinkedList class. Because this type of enumerator doesn’t exist in a generic library, we need to code it ourselves. For this to work, we need to implement properties, methods and explicit interface implementations.

Don’t worry, Microsoft Visual Studio will tell you what methods are missing, so you can implement accordingly.

Once we set up the enumerator, we only need to add extension methods that will allow us to navigate with Next and Previous methods.

Note: As you can see from the code I used an operator ?? on multiple occurences. In case you’ve never seen it before, it’s basically a shortened version of if-else statement.

However, it does check for one specific thing, which is, if the value on left side equals to null, it sets variable to the value on the right side. On the other hand, if the left doesn’t equal to null, then this value will we set for the variable.

Conclusion

I hope this short tutorial helped you gain a better understanding about circular linked lists in C#.

If you want to try it out yourself, you can also download the project I set up for demonstration.

Related Articles

Image Noise

How To Make Gaussian Noise On Image – C# Guide

Gaussian noise on images is generated with Gaussian probability distribution function. It simulates noise that appears in practice.

Posted on by Andraz Krzisnik
Morphological Processes

How To Make Convex Hull In Image Processing With C#

Convex hull in image processing is a morphological operation, where we encapsulate a shape or and object in an image into a convex shape.

Posted on by Andraz Krzisnik