GESP 六级 · GESP 202309 C++ 六级 第 14 题

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

这道题考链表遍历的时间复杂度。找节点必须从头开始一个个看，平均要走一半，最坏走全部，都是和N成比例，所以是O(N)。

容易把数组的O(1)随机访问套用到链表上，或者看到"平均"就以为会降一档变成对数级。其实平均情况只是把N换成N/2，在O记法里常数直接被吞了，还是O(N)。

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

1. 考纲定位

GESP 六级/七级必考内容，也是数据结构最基础的区分度测试。命题人专门用这道题卡住"只会背数组复杂度、不懂数据结构本质差异"的考生——数组能 O(1) 随机访问，链表不能，这是数据结构最核心的特征之一。