Creating a Circularly Linked List in C#

Creating a circularly linked list in C#?

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.

Is the LinkedList in .NET a circular linked list?

No. It is a doubly linked list, but not a circular linked list. See MSDN for details on this.

LinkedList<T> makes a good foundation for your own circular linked list, however. But it does have a definite First and Last property, and will not enumerate around these, which a proper circular linked list will.

Create circular doubly linked list

I'm not sure why you don't use the exact code provided in the answer at Creating a circularly linked list in C#?

Be that as it may, you can fix your immediate problem by adding a ? null-conditional operator. This is because Previous might be null, and that would be the basis of coalescing to null using ??.

runner = items.Find(runner).Previous?.Value ?? items.Last.Value;

Converting singly linked list to circular linked list by pointing last node to middle node

The only way you would be able to get this to work would be to change:

currentNode = middleNode

This line simply replaces the reference to the currentNode object to be the reference to the middleNode object.

You would need to change this to:

currentNode.Next = middleNode

Unfortunately--unless in your CustomLinkedListNode you've added a setter to the "Next" property, currentNode.Next is readonly, meaning you cannot set it. Thus what you want is not possible.

Fastest algorithm for a 'circular linked list builder'

You can do it the following way:

static IEnumerable<Edge<T>> OrderEdges<T>(this IEnumerable<Edge<T>> edges)
    where T : IEquatable<T>
{
    Debug.Assert(edges.Any());
    var map = new Dictionary<T, Edge<T>>();

    foreach (var e in edges)
    {
        if (map.ContainsKey(e.Node1))
        {
            Debug.Assert(!map.ContainsKey(e.Node2));
            map.Add(e.Node2, e);
        }
        else
        {
            map.Add(e.Node1, e);
        }
    }

    var current = edges.First();
    var orderedEdges = new HashSet<Edge<T>>();

    while (true)
    {
        orderedEdges.Add(current);
        yield return current;

        if (orderedEdges.Count == map.Count)
            break;

        var next = map[current.Node2];
        current = orderedEdges.Contains(next) ? map[current.Node1] : next;
    }
}

Where the Edge<T> class is simply:

class Edge<T> where T: IEquatable<T>
{
    public T Node1 { get; }
    public T Node2 { get; }
    public string Name { get; }
    public Edge(string name, T node1, T node2)
    {
        Name = name;
        Node1 = node1;
        Node2 = node2;
    }

    public override string ToString() => Name;
}

If we run this little guy:

var edges = new List<Edge<int>>() {
    new Edge<int>("A", 4, 9), new Edge<int>("B", 6, 1),
    new Edge<int>("C", 1, 3), new Edge<int>("D", 3, 10),
    new Edge<int>("E", 7, 2), new Edge<int>("F", 4, 2),
    new Edge<int>("G", 9, 8), new Edge<int>("H", 10, 5),
    new Edge<int>("I", 7, 5), new Edge<int>("J", 6, 8) };

Console.WriteLine(string.Join(" -> ", edges.OrderEdges()));

We get the expected result:

A -> G -> J -> B -> C -> D -> H -> I -> E -> F

Do note that this solution presupposes that the input data is well formed.

Circular singly-linked list

Think about what each node in a singly linked list "knows" (i.e. what data it stores). Then think about what it means to make a circular list. What's the "next" element after the last one?

Hopefully that's enough of a hint to get you started.

---

Related Topics