28

在 C# 中创建循环链表的最佳方法是什么。我应该从 LinkedList< T> 集合中派生它吗?我正计划使用此链接列表创建一个简单的地址簿来存储我的联系人(这将是一个糟糕的地址簿,但我不在乎,因为我将是唯一使用它的人)。我主要只是想创建关键链接列表,以便我可以在其他项目中再次使用它。

如果您认为链接列表不是正确的方法,请告诉我哪种方法会更好。

4

10 回答 10

85

由于这些答案中的大多数实际上并没有真正解决问题的实质,而仅仅是意图,因此也许这会有所帮助:

据我所知,链接列表和循环链接列表之间的唯一区别是迭代器在到达列表末尾或开头时的行为。支持循环链接列表行为的一种非常简单的方法是为 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;
    }
}

现在您可以只调用 myNode.NextOrFirst() 而不是 myNode.Next,您将拥有循环链表的所有行为。您仍然可以在列表中的所有节点之前和之后进行恒定时间删除和插入等。如果我缺少循环链表的其他关键位,请告诉我。

于 2010-04-19T19:29:42.870 回答
5

从 BCL LinkedList 类派生可能不是一个好主意。该类被设计为一个非循环列表。试图让它循环只会给你带来问题。

你自己写可能会好得多。

于 2009-04-04T01:23:06.593 回答
4

我不认为循环链表是联系人列表的正确数据结构。一个简单的 List<> 或 Collection<> 就足够了。

于 2009-04-04T01:22:04.737 回答
4

您是否有使用循环链表(即作业)的特定要求?如果没有,我建议使用简单List<T>类来存储您的联系人。

于 2009-04-04T01:23:31.007 回答
3

循环链接列表通常使用数组实现,这使得它们非常快,并且本质上不需要动态调整大小。您只需要快速检查读取和写入索引,看看它们是否从末端脱落,如果是,请将其重置为零(或一,等等)。

但是,它们通常用于输入缓冲区之类的东西,其中数据一旦读取就没有实际价值。联系人列表具有持久的价值,一旦列表填满,新联系人将覆盖旧联系人,这可能没问题,除非你覆盖你的祖母,她会给你留下一大笔现金。


我不认为链表是循环缓冲区的最有效方法(原始问题)。

循环缓冲区的目的是提高速度,而在循环缓冲区的上下文中,数组根本无法超越速度。即使您保留指向上次访问的链表项的指针,数组仍然会更有效。列表具有循环缓冲区不需要的动态调整大小功能(开销)。话虽如此,我认为循环缓冲区可能不是您提到的应用程序(联系人列表)的正确结构。

于 2009-04-04T02:52:04.677 回答
3
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() { }
}
于 2012-02-26T19:18:13.817 回答
2

基于模数的解决方案。

如果循环缓冲区被实现为原始数组(或任何其他类型的集合)

T[] array;

并且我们存储到int current_index当前项的索引中,我们可以循环上下缓冲区如下:

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

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

相同的方法可用于任何 XAML 绑定集合。

于 2016-05-19T08:38:46.900 回答
1

这个基于 CList 的循环列表怎么样。

于 2009-04-04T01:24:31.863 回答
0

我认为这个问题最正确的数据结构是循环双向链表。使用此数据结构,您可以通过联系人列表自由上下

于 2011-11-13T01:34:43.503 回答
0
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;
    }
}

如果您想走得更远,请制作 aCircularList并按住相同的枚举器以跳过Skip()示例中的旋转时的 。

于 2012-03-31T04:09:22.090 回答