在 C# 中创建循环链表？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/716256/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Creating a circularly linked list in C#?
提问by Kredns
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.
在 C# 中创建循环链表的最佳方法是什么。我应该从 LinkedList< T> 集合派生它吗？我打算使用这个链接列表创建一个简单的地址簿来存储我的联系人（这将是一个糟糕的地址簿，但我不在乎，因为我将是唯一使用它的人）。我主要只是想创建关键链接列表，以便我可以在其他项目中再次使用它。
If you don't think the Linked List is the right way to go let me know which way would be better.
如果您认为链接列表不是正确的方法，请告诉我哪种方法更好。
采纳答案by Clueless
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:
据我所知，链表和循环链表之间的唯一区别是迭代器到达列表末尾或开头时的行为。支持循环链表行为的一个非常简单的方法是为 LinkedListNode 编写一个扩展方法，该方法返回列表中的下一个节点，如果不存在这样的节点，则返回第一个节点，同样用于检索前一个节点或最后一个节点如果不存在这样的节点，则为一个。下面的代码应该可以做到这一点，虽然我还没有测试过：
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.
现在您只需调用 myNode.NextOrFirst() 而不是 myNode.Next ，您将拥有循环链表的所有行为。您仍然可以进行恒定时间删除并在列表中的所有节点之前和之后插入等等。如果我遗漏了循环链表的其他一些关键位，请告诉我。
回答by Mitch Wheat
I don't think a circular linked list is the right data structure for a contacts list. A simple List<> or Collection<> should suffice.
我不认为循环链表是联系人列表的正确数据结构。一个简单的 List<> 或 Collection<> 就足够了。
回答by JaredPar
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.
从 BCL LinkedList 类派生可能是一个坏主意。该类被设计为一个非循环列表。试图让它循环只会给你带来问题。
You're probably much better off writing your own.
你可能最好自己写。
回答by Samuel
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.
你有使用循环链表（即作业）的具体要求吗？如果没有，我建议使用简单的List<T>类来存储您的联系人。
回答by John Ellinwood
How about this CList based circular list.
这个基于 CList 的循环列表怎么样。
回答by RAL
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.
循环缓冲区的目的是提高速度，而在循环缓冲区的上下文中，数组的速度是无法超越的。即使您保留一个指向上次访问的链表项的指针，数组仍然会更有效率。列表具有循环缓冲区不需要的动态调整大小功能（开销）。话虽如此，我认为循环缓冲区可能不是您提到的应用程序（联系人列表）的正确结构。
回答by omar
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
我认为这个问题最正确的数据结构是循环双向链表。有了这个数据结构，你可以自由地上下浏览联系人列表
回答by Andrii Nemchenko
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() { }
}
回答by Davi Fiamenghi
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 CircularListand hold the same enumerator to skip the Skip()when rotating like in your sample.
如果你想更进一步，制作一个CircularList并保持相同的枚举器Skip()在旋转时跳过你的样本。
回答by voccoeisuoi
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_indexthe index of the current item, we can cycle up and down the buffer as follows:
并且我们存储到int current_index当前项的索引中，我们可以按如下方式上下循环缓冲区：
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.
相同的方法可用于任何 XAML 绑定集合。
