C＃中允许在O（1）中反转的数据结构

Question

我有一些要迭代的列表，有时从头到尾，有时从头到尾。此列表从未修改过，我将对其进行多次遍历。当我要从头到尾进行迭代时，我想避免在O（n）中反转列表的操作。

是否有某种允许的数据结构？

我以为C＃中的（双重）LinkedList实现允许这种行为很简单（通过保留列表开头的内部引用），但是我不认为这种实现方式。如果我写错了，可以提供链接吗？

Answer 1

具有直接索引访问和长度（数组，列表，字符串，文件流）的任何数据结构都可以表示在O（1）时间内完成“反向”（请注意，它本身就是反向的，显然，迭代所有项仍为O（ n）。

Possible to iterate backwards through a foreach?中有几个带有“收益率回报”的示例，suggested by Jon Skeet是最灵活的方式（性能可能比向后for差一点：]

public static IEnumerable<T> FastReverse<T>(this IList<T> items)
{
    for (int i = items.Count-1; i >= 0; i--)
    {
        yield return items[i];
    }
}

作为Patrick Roberts commented，您还可以使用其他看起来像数组的数据结构-即具有顺序int键和已知高/低边界的字典将起作用（这大致就是JavaScript数组的工作方式。

请注意，从理论的角度来看，如果您仍然需要遍历所有元素，那么将O（n）用于反向花费不会改变整体复杂度。