GESP 六级 · GESP 202412 C++ 六级 第 5 题

$N$ 个节点的双向循环链，在其中查找某个节点的平均时间复杂度是（ ）。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】链表遍历｜平均时间复杂度｜线性查找

GESP 六级“数据结构·链表”模块，命题人卡住的是“链表即数组”的直觉误区，考查对链表访问本质的理解。

双向循环链表没有排序，查找任意节点必须从头或尾单向遍历。平均情况下期望步数 = N/2 = O(N)。双向只是能反向遍历，不改变时间阶数。

A 项 O(1) 混淆了数组随机访问；C 项 O(log N) 误把二分查找套到链表上——二分需要 O(1) 随机访问；D 项 O(N³) 纯属吓唬人。最阴险的是“平均”二字，不少同学只记“最坏情况 O(N)”，忽略了平均也是同一量级。

若链表已排序且支持 O(1) 随机访问（如跳表），平均可降至 O(log N)；若换成哈希表，平均直接 O(1)。刷题前先问自己：题目在考验什么数据结构特性？