Creating a cyclically linked list in C #?

Question

What would be the best way to create a cyclically linked list in C #. Should I get it from the LinkedList <T> collection? I plan to create a simple address book using this Linked List to store my contacts (this will be the suck-y address book, but I don't care, I will be the only one who can use it). I basically just want to create a list related to criticism so that I can use it again in other projects.

If you don’t think a linked list is the right way, let me know which one is better.

Answer 1

Since most of these answers do not actually address the essence of the question, just intention, perhaps this will help:

As far as I can tell, the only difference between the Linked List and the Circular Linked List is the behavior of iterators when they reach the end or the beginning of the list. A very simple way to maintain the behavior of the Circular Linked List is to write an extension method for LinkedListNode that returns the next node in the list or the first if such a node does not exist, and similarly to get the previous node or the last if such a node does not exist. The following code should execute this, although I have not 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 the circular linked list. You can still permanently delete the time and insert before and after all the nodes in the list, etc. If you have another key bit of a circular linked list, I don't know, let me know.

Answer 2

There will probably be a bad conclusion from the BCL LinkedList class. This class is for a non-circular list. Trying to make it circular will cause only problems.

You are probably much better off writing your own.

Answer 3

I do not think that a circular linked list is the correct data structure for a contact list. A simple list <> or Collection <> should be sufficient.

Answer 4

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

Answer 5

Looping lists are often implemented using arrays, which make them very fast and, by their nature, do not require dynamic resizing. You just need a quick check of the read and write indices to see if they have fallen from the end, and if so, then reset it is zero (or one, regardless).

However, they are commonly used for things like input buffers, where the data does not have real value after reading. Contact lists are of lasting importance, and new contacts will overwrite old contacts after filling out the list, which may be good if you do not rewrite your grandmother, who will leave you a lot of cash in her will.

---

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

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

Answer 6

 class CircularArray<T> : IEnumerator<T> { private readonly T[] array; private int index = -1; public T Current { get; private set; } public CircularArray(T[] array) { Current = default(T); this.array = array; } object IEnumerator.Current { get { return Current; } } public bool MoveNext() { if (++index >= array.Length) index = 0; Current = array[index]; return true; } public void Reset() { index = -1; } public void Dispose() { } } 

Answer 7

Module based solution.

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

 T[] array; 

and we store the index of the current element in int current_index , we can cyclically move 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.

Answer 8

How about this CLIST based circular list .

Answer 9

I think the most correct data structure for this problem is a circular double list. Using this data structure, you can freely navigate your contact list.

Answer 10

 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 to go further, make a CircularList and hold the same enumerator to skip Skip() while rotating, as in your example.