c#/ .net xx是否具有双向链表的实现(可以向后迭代)？

Question

我一直在寻找c#中双向链表的标准实现(所以我有一个链表可以向后迭代)并且找不到.我觉得这么简单的东西必须有一个我只是缺少的实现.

如果确实存在,那么它存在哪个版本的c#/ .net？

反向迭代通常似乎是不打算在c#中完成的.我的思想在c ++/stl模式下是不是太过分了,或者这是c#中非常缺乏的东西？

我知道LinkedList但是没有找到一种方法来向后迭代它假设它是单独链接的.

如果LinkedList是双向链接的,那么如何向后迭代它(有效地)？

Answer 1

以下代码将有效地迭代遍历LinkedList:

        LinkedList<string> list = new LinkedList<string>
            (new[] {"cat", "dog", "frog", "antelope", "gazelle"});
        LinkedListNode<string> item = list.Last;
        do
        {
            Console.WriteLine(item.Value);
            item = item.Previous;
        }
        while (item != null);
        Console.ReadKey();

这里的关键是LinkedList只包含对列表的First和Last LinkedListNode实例的引用.每个LinkedListNode实例都包含对列表中下一个和上一个项的引用(或列表每端的null)以及Value属性.这意味着从第一个或最后一个LinkedListNode迭代很容易,但随机访问需要从列表中的第一个或最后一个迭代.

如果需要沿途插入,请使用LinkedList.AddBefore或AddAfter插入新的LinkedListNode.

Answer 2

除了这里给出的答案,您还可以编写一个扩展方法,LinkedList<T>以便更轻松地重用:

public static IEnumerable<T> Backwards(this LinkedList<T> list)
{
    LinkedListNode<T> node= list.Last;
    while (node != null)
    {
        yield return node.Value;
        node = node.Previous;
    }
}

用于:

foreach (string x in list.Backwards())
{
    // ...
}