26

I need a circular linked list, so I am wondering if LinkedList is a circular linked list?

John Calsbeek
  • 35,947
  • 7
  • 94
  • 101
Joan Venge
  • 315,713
  • 212
  • 479
  • 689
  • @John, FYI I read the docs, but if you knew anything, you would know this is a valid question to ask, considering LinkedList implementations vary greatly. – Joan Venge Jun 22 '09 at 16:51
  • Ok, I'll withdraw the -1 until you specify what you mean by circular linked list, and why the MSDN documentation didn't make that clear to you. That way, we'll also get to tell Microsoft how to fix the documentation. – John Saunders Jun 22 '09 at 16:58
  • Fair enough. I guess I didn't really trust if MS used the term correctly. You know sometimes the claims for the BCL aren't valid. Minor but still wanted to be sure. – Joan Venge Jun 22 '09 at 17:17
  • 4
    @Dror: The use case that comes to mind is an I/O buffer. – Robert Harvey Feb 18 '11 at 18:46

5 Answers5

79

A quick solution to using it in a circular fashion, whenever you want to move the "next" piece in the list:

current = current.Next ?? current.List.First;

Where current is LinkedListNode<T>.

abatishchev
  • 98,240
  • 88
  • 296
  • 433
Ady Kemp
  • 903
  • 1
  • 7
  • 7
19

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.

Reed Copsey
  • 554,122
  • 78
  • 1,158
  • 1,373
  • FWIW, the doc statement that proves it is not circular can be found in [LinkedListNode.Next Property)](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.linkedlistnode-1.next?view=netframework-2.0): "A reference to the next node in the LinkedList, or **null** if the current node is the last element (**Last**) of the LinkedList." – ToolmakerSteve Nov 23 '18 at 13:31
9

While the public API of the LinkedList is not circular, internally it actually is. Consulting the reference source, you can see how it's implemented:

// This LinkedList is a doubly-Linked circular list.
internal LinkedListNode<T> head;

Of course, to hide the fact that it's circular, properties and methods that traverse the list make checks to prevent wrapping back to the head.

LinkedListNode:

public LinkedListNode<T> Next {
    get { return next == null || next == list.head? null: next;}
}

public LinkedListNode<T> Previous {
    get { return prev == null || this == list.head? null: prev;}
}

LinkedList.Enumerator:

public bool MoveNext() {
    if (version != list.version) {
        throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion));
    }

    if (node == null) {
        index = list.Count + 1;
        return false;
    }

    ++index;
    current = node.item;   
    node = node.next;  
    if (node == list.head) {
        node = null;
    }
    return true;
}
Arturo Torres Sánchez
  • 2,751
  • 4
  • 20
  • 33
6

If you need a circular data structure, have a look at the C5 generic collections library. They have any collection that's imaginably useful in there, including a circular queue (which might help you).

Jacob
  • 22,785
  • 8
  • 39
  • 55
4

No, its not. See MSDN

Lucas Jones
  • 19,767
  • 8
  • 75
  • 88