GESP 六级 · GESP 202503 C++ 六级 第 25 题

栈和队列均可以用双向链表实现，插入和删除操作的时间复杂度为 $O(1)$。

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

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

【考点】数据结构实现｜链表操作｜时间复杂度分析

🎯 考纲定位 GESP六级《数据结构与算法》核心模块。命题人专门卡住那些只背"栈用数组实现""队列用链表实现"这种刻板印象的考生——六级不再考"能用什么实现"，而是考"不同实现方式下的操作复杂度"。

🧠 解题思维 链表插入/删除的本质是"只改指针，不动数据"。栈的push/pop对应链表头插/头删，队列的enqueue/dequeue对应头插+头删或尾插+头删，双向链表两端都能O(1)操作。因此只要题目说是"可以用链表实现"，插入删除就是O(1)。

🪤 陷阱拆解 A选项把"时间复杂度为O(1)"直接说成"正确"，看似绝对，实则精准——命题人利用考生容易把"链表操作一定是O(n)"的直觉当成铁律。错误选项通常会把"链表操作时间复杂度"偷换为"链表查找时间复杂度"，或者把"双向链表"暗示成"更复杂结构"。只要抓住"指针操作O(1)"这一条，就能避开所有陷阱。

🔄 反命题思维 如果改成"插入和删除操作的时间复杂度为O(log n)"，答案立刻翻转；若强调"双向链表只能O(1)插入删除，不能O(1)查找"，则考点变成"链表查找O(n)"。刷到类似题先问自己：命题人想考我链表指针操作的本质，还是想考我混淆"操作"与"查找"？