从一元链表中获取第10项的最有效方法

Question

从列表末尾获取第10项的最有效方法是什么

我是这样想的：

List[List.Count() - 10];

Answer 1

如果你使用的是来自System.Collections.Generic的List<T>，那么你实际上并没有使用单链表。它由一个数组支持，您可以简单地通过索引访问它，正如您已经建议的那样：

list[list.Count - 10];

这将是O(1)运算。在这样做之前，你可能应该检查list是否至少有10个元素，这样你就不会得到异常。

但是，如果您有自己的单链表结构，则必须迭代整个列表才能从列表的末尾获得第N项。您可以使用相同的方法，但这将强制在集合上进行两次往返-第一次获取元素的总数，第二次获取最后第N个元素。

如果你存储了你最后一次看到的N项目，例如在一个队列中，你可以只用一次迭代就能实现。这将是O(n)操作。