GESP 七级 · GESP 202409 C++ 七级 第 24 题

使用单链表实现队列时，链表头结点作为队首比链表头结点作为队尾更便于操作。

链表分为单向/双向/循环链表，插入删除O(1)，但查找O(n)。注意指针操作的顺序，防止断链。

链表操作要特别注意指针修改的顺序。例如在节点前插入时，先新节点→next = 当前→next，再当前→next = 新节点。顺序颠倒会导致断链。

【考点】链表操作｜队列实现｜时间复杂度

🎯 考纲定位 GESP 七级《数据结构与算法》链表专题，命题人专门卡住学生"单向链表只能向前遍历"这一硬性约束。七级以前学生容易把链表当成双向链表用，忽略节点指针方向，导致在队列场景下误判操作效率。

🧠 解题思维 队列本质是 FIFO 结构：入队加到尾部，出队从头部删除。单向链表只有 next 指针，只能从头往后走。若头结点作队尾，入队需遍历整表找尾节点 O(n)；若头结点作队首，出队直接删头节点 O(1)，入队仍需 O(n)——但题目比较的是"作为队首比作为队尾更便于操作"，因为两种操作总次数必然相等，关键在于出队频率高时优先保证 O(1)，所以头作队首更优。

🪤 陷阱拆解 错误选项 B 诱使考生认为"入队更频繁，所以头作队尾省事"，却完全忽略单向链表无法从尾结点快速定位下一个位置的致命缺陷。命题人借"便于操作"四个字模糊时间复杂度对比，若只背结论不分析指针方向，必然掉进这个坑。

🔄 反命题思维 若题目改成"双向链表"，答案就反了——头作队尾时出入队都能 O(1)。刷到类似题先问自己：链表是单向还是双向？队列还是栈？指针允许往哪走？这三点定生死。

, created by