如何以倒序方式遍历C# LinkedList

Question

我该如何使用C#的LinkedList来实现与下面这段C++代码等效的功能？

std::list<MyClass*>::reverse_iterator itr(it); 
for(; itr != MyList.rend(); ++itr)

- softwarematter

Answer 1

作为一次性事件，可以这样做：

var el = list.Last;
while (el != null) {
    // use el.Value
    el = el.Previous;
}

如果您经常这样做，可以使用类似的迭代器块来产生所有值：

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

那么：

foreach(var val in list.Reverse()) {
    // use val
}

- Marc Gravell

---

我认为值得注意的是，LinkedList<T> 是 IEnumerable<T>，因此如果您使用 Linq，它会使用 IEnumerable<T>.Reverse()。对于非常短的列表，这可能已经足够了。对于较长的列表，这个答案中的方法将更加高效。 - Matthew Strawbridge

@UnionP 你在进行基准测试时使用了BenchmarkDotNet吗？能否分享一下结果？ - undefined

我之前没有测试过，但刚刚测试了一下，结果更糟糕，92ns（使用扩展方法）对比11ns（使用for循环）。你可以使用这个LINQPad脚本来复现测试结果：http://share.linqpad.net/j2ojvo.linq - undefined

@UnionP 感谢你分享你的基准测试结果。我之前没有意识到C#的迭代器会有可测量的开销。 - undefined

Marc Gravell，你可以把Reverse改成ReverseIteration或者其他什么名字，这样就能避免误用LINQ的Reverse操作符了。有趣的是，你的操作符和LINQ的操作符在性能上没有太大的区别。唯一能观察到的区别就是LINQ的Reverse分配了更多的内存。 - undefined

Answer 2

一个对Marc的while循环的调整是使用for循环，我觉得这样更简洁一些。

for (var el = list.Last; el != null; el = el.Previous)
{
    // use el.Value
}

- UnionP