Creating a circularly linked list in C#?

Question

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.

Alb

Answer 1

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.

Appointive

That's just perfect man, thanks ! For improved style, one could use the '??' operator : return current.Next ?? current.List.First; – Irreplaceable

@Irreplaceable Language intricacies don't necessarily aid readability. – Greenling

One thing that is important to note here is that current.List can potentially be null if the node itself is unlinked. See msdn.microsoft.com/en-us/library/h339c45b(v=vs.110).aspx – Bethelbethena

As mentioned by @JamesMcMahon, we can enhance as: static class CircularLinkedList { public static LinkedListNode<T> NextOrFirst<T>(this LinkedListNode<T> current) { if (current != null && current.List != null) { return current.Next ?? current.List.First; } return null; } public static LinkedListNode<T> PreviousOrLast<T>(this LinkedListNode<T> current) { if (current != null && current.List != null) { return current.Previous ?? current.List.Last; } return null; } } – Yellowtail

Instead of current.List.First and .Last, use current.List?.First and ?.Last to handle even extreme cases of unlinked nodes. – Alkalosis

Answer 2

It would likely be a bad idea to derive from the BCL LinkedList class. That class is designed to be a non-circular list. Trying to make it circular will only cause you problems.

You're probably much better off writing your own.

Edie

Answer 3

I don't think a circular linked list is the right data structure for a contacts list. A simple List<> or Collection<> should suffice.

Wetzell

Answer 4

Do you have a specific requirement to use a circularly linked list (i.e. homework)? If not, I would suggest using the simple List<T> class to store your contacts.

Interbedded

Answer 5

Circularly-linked lists are often implemented using arrays which makes them very fast and by their nature do not require dynamic resizing. You just need a quick check on the read and the write indexes to see if they fell off the end and if so, reset it to zero (or one, whatever).

However, they are generally used for things like input buffers, where the data has no real value once read. Contact lists have lasting value and new contacts will overwrite older contacts once the list fills up, which might be ok unless you overwrite your grandmom who is leaving you a bunch of cash in her will.

---

I do not think that a linked list is the most efficient way to go for a circular buffer (the original question).

The purpose of a circular buffer is speed and an array simply cannot be beaten for speed in the context of a circular buffer. Even if you keep a pointer to your last accessed linked list item, an array will still be more efficient. Lists have dynamic resizing capabilities (overhead) that are unneeded for circular buffers. Having said that, I think a circular buffer is probably not the right structure for the application (contact list) you mention.

Douche

arrays which makes them very fast and by their nature do not require dynamic resizing - why do you say that? – Nasya

He most likely says that because if you are using a circular list, you probably have a set capacity and wont need to dynamically resize beyond that. – Luedtke

Answer 6

A modulus based solution.

If the circular buffer is implemented as a raw array (or any other kind of collection for what it matters)

T[] array;

and we store into int current_index the index of the current item, we can cycle up and down the buffer as follows:

T NextOrFirst()
{
    return array[(current_index + 1) % array.Length];
}

T PreviousOrLast()
{
    return array[(current_index + array.Length - 1) % array.Length];
}

The same approach can be used with any XAML binding collection.

Retrospect

Answer 7

How about this CList based circular list.

Potash

Answer 8

I think the most correct data structure for this problem is a circular doubly linked list. With this data structure you can freely up and down through contacts list

Riker

Answer 9

class Program
{
    static void Main(string[] args)
    {
        int[] numbers = { 1, 2, 3, 4, 5, 6, 7 };

        IEnumerable<int> circularNumbers = numbers.AsCircular();

        IEnumerable<int> firstFourNumbers = circularNumbers
            .Take(4); // 1 2 3 4

        IEnumerable<int> nextSevenNumbersfromfourth = circularNumbers
            .Skip(4).Take(7); // 4 5 6 7 1 2 3 
    }
}

public static class CircularEnumerable
{
    public static IEnumerable<T> AsCircular<T>(this IEnumerable<T> source)
    {
        if (source == null)
            yield break; // be a gentleman

        IEnumerator<T> enumerator = source.GetEnumerator();

        iterateAllAndBackToStart:
        while (enumerator.MoveNext()) 
            yield return enumerator.Current;

        enumerator.Reset();
        if(!enumerator.MoveNext())
            yield break;
        else
            yield return enumerator.Current;
goto iterateAllAndBackToStart;
    }
}

If you want go further, make a CircularList and hold the same enumerator to skip the Skip() when rotating like in your sample.

Tracay