GESP 八级 · GESP 202406 C++ 八级 第 23 题

使用单链表和使用双向链表，查找元素的时间复杂度相同。

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

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

【考点】链表结构｜时间复杂度分析｜线性遍历

1. 🎯 考纲定位

本题考查《GESP 大纲》八级"数据结构与算法"模块中链表基础内容。命题人卡住的是考生对"链表查找本质"的认知——绝大多数人误以为双向链表因有前后指针就更快，却忽略了查找仍需从头或尾线性遍历的核心事实。