我有一些我想要遍历的列表,有时从头到尾,有时从头到尾。此列表从未修改过,我将多次迭代它。当我想从头到尾迭代时,我想避免在 O(n) 中反转列表的操作。
是否有某种数据结构允许这样做?
我认为 C# 中的(双重)LinkedList 实现允许这种行为(通过保留列表开头的内部引用)会很简单,但我认为它没有实现方式。如果我错了,你能提供一个链接吗?
最佳答案
任何具有直接索引访问和长度的数据结构(数组、列表、字符串、文件流)都允许表示在 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) 不会改变整体复杂性。
关于c# - C# 中允许在 O(1) 中反转的数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58550791/