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

Question

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

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

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

Answer 1

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

有可能通过foreach向后迭代的示例。乔恩·斯凯特（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）所评论的，您还可以使用其他看起来像数组的数据结构-即具有顺序int键和已知高/低边界的字典将起作用（这大致就是JavaScript数组的工作方式）。

确实LinkedList，仅在需要正向和反向迭代时，双链表（在C＃中）是首选的数据结构...但是转换数组/列表（已经为您提供了表示反向迭代的O（1）方式）是不值得的它。根据其他要求，可以选择完全切换到链表。

请注意，从理论的角度来看，如果无论如何您都需要遍历所有元素，那么将O（n）花在反向上并不会改变整体复杂度。