Creating a circularly linked list in C#?

Kredns picture Kredns · Apr 4, 2009 · Viewed 23.6k times · Source

What would be the best way to create a circularly linked list in C#. Should I derive it from the LinkedList< T> collection? I'm planning on creating a simple address book using this Linked List to store my contacts (it's gonna be a suck-y address book, but I don't care cause I'll be the only one to use it). I mainly just want to create the crucially linked list so that I can use it again in other projects.

If you don't think the Linked List is the right way to go let me know which way would be better.

Answer

Clueless picture Clueless · Apr 19, 2010

As most of these answers don't actually get at the substance of the question, merely the intention, perhaps this will help:

As far as I can tell the only difference between a Linked List and a Circular Linked List is the behavior of iterators upon reaching the end or beginning of a list. A very easy way to support the behavior of a Circular Linked List is to write an extension method for a LinkedListNode that returns the next node in the list or the first one if no such node exists, and similarly for retrieving the previous node or the last one if no such node exists. The following code should accomplish that, although I haven't tested it:

static class CircularLinkedList {
    public static LinkedListNode<T> NextOrFirst<T>(this LinkedListNode<T> current)
    {
        return current.Next ?? current.List.First;
    }

    public static LinkedListNode<T> PreviousOrLast<T>(this LinkedListNode<T> current)
    {
        return current.Previous ?? current.List.Last;
    }
}

Now you can just call myNode.NextOrFirst() instead of myNode.Next and you will have all the behavior of a circular linked list. You can still do constant time removals and insert before and after all nodes in the list and the like. If there's some other key bit of a circular linked list I am missing, let me know.