GESP 五级 · GESP 202403 C++ 五级 第 24 题

单链表和双链表都可以在常数时间内实现在链表头部插入或删除节点的操作。

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

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

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

1. 考纲定位：GESP 202403 C++ 五级，考查数据结构中链表的基本性质。命题人专门挑"头部操作"来卡住那些只背过"链表是线性的"却没细看过操作差异的考生——五级题往往就在这些基础细节上设伏。

2. 解题思维：单向链表头插只需 new_node->next=head; head=new_node; 头删 head=head->next; 双向链表头插再多加 new_node->prev=NULL; head->prev=new_node; 头删 head->prev=NULL; 关键观察是"头部指针直接指向新节点"，无需遍历任何节点，因此时间复杂度 O(1)。这一结论适用于所有链表头部操作，是链表区别于数组的核心优势。

3. 陷阱拆解：命题人专挖"头尾混淆"坑。若题目改成"尾操作"，单链表尾插尾删需 O(n) 遍历，答案变 B。考生易被"链表"二字带偏，忽略"头部"这一关键限定词，误以为所有链表操作都是 O(1)。最阴险的是没写"仅头部"，让粗心者默认链表整体都是常数操作。

4. 反命题思维：若改为"尾操作"，单链表尾插尾删需遍历至末尾，时间复杂度 O(n)，答案变 B。刷到链表题先问"考头还是尾"，别被"链表"自带的光环迷惑。