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.

Show Comments (0)

Comments

Related Articles

Adaptive Filters

How To Make Adaptive Median Filter For Images With C#

Adaptive median filter is much more effective at removing impulse noise, also known as salt and pepper noise, than traditional median filter.

Posted on by Andraz Krzisnik
Sorting Algorithms

How To Make Insertion Sort Algorithm In C# – Made Easy

Insertion sort is one of the simplest sorting algorithms for sorting single dimensional arrays of various different data types.

Posted on by Andraz Krzisnik