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

问题描述 投票:0回答:1

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

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

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

c# list data-structures reverse
1个回答
2
投票

具有直接索引访问和长度(数组,列表,字符串,文件流)的任何数据结构都可以表示在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)用于反向花费不会改变整体复杂度。

© www.soinside.com 2019 - 2024. All rights reserved.