c# - C# 中允许在 O(1) 中反转的数据结构

Question

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

是否有某种数据结构允许这样做？

我认为 C# 中的(双重)LinkedList 实现允许这种行为(通过保留列表开头的内部引用)会很简单，但我认为它没有实现方式。如果我错了，你能提供一个链接吗？

Answer 1

任何具有直接索引访问和长度的数据结构(数组、列表、字符串、文件流)都允许表示在 O(1) 时间内完成“反向”(注意它本身是反向的，显然迭代所有项目仍然是 O (n).

Possible to iterate backwards through a foreach?中有几个例子与“ yield 返回”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 数组的工作方式)。

确实，双链表(C# 中的 LinkedList)是仅需要正向和反向迭代时选择的数据结构...但是转换数组/列表(已经给你 O( 1)表示反向迭代的方式)不值得。根据其他要求，完全切换到链表可能是一种选择。

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