NOIP 普及组初赛 · NOIP 2011 普及组初赛试题 第 13 题

在含有 $n$ 个元素的双向链表中查询是否存在关键字为 $k$ 的元素，最快情况下运行的时间复杂度是（ ）。

这题考双向链表查找复杂度。别被‘双向’二字误导，它只是能两头遍历，依然只能一个个节点挨个找，最快也得看运气。

最容易错选 B O(log n)，那是二分查找的复杂度，前提是支持随机访问或有序且能跳半程；链表不支持随机访问，无法二分。也有人选 A O(1)，那是直接访问第 i 个位置的复杂度，不是按值查找。记住：链表按值查找永远是线性扫描，最快也是 O(n)。

双向链表查找的真相

考点与概念

这道题考查的是链表查找的时间复杂度。链表（无论是单向还是双向）的核心特征是不支持随机访问：你不能直接跳到第 i 个节点，只能从头（或从尾）一个接一个地往后挪。因此，如果要找关键字 k，只能从头到尾（或从尾到头）逐个比较节点的值，直到找到为止，或者遍历完所有节点都没找到。这种“挨个看”的过程就是线性扫描。