GESP 五级 · GESP 202406 C++ 五级 第 3 题

小杨采用如下双链表结构保存他喜欢的歌曲列表：

struct dl_node {
    string song;
    dl_node* next;
    dl_node* prev;
};

小杨想在头指针为 head 的双链表中查找他喜欢的某首歌曲，采用如下查询函数，该操作的时间复杂度为（ ）。

dl_node* search(dl_node* head, string my_song) {
    dl_node* temp = head;
    while (temp != nullptr) {
        if (temp->song == my_song)
            return temp;
        temp = temp->next;
    }
    return nullptr;
}

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

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

【考点】链表遍历（线性查找）｜时间复杂度分析

1. 🎯 考纲定位

五级数据结构模块，考察链表基本操作与复杂度分析。命题人卡住的是学生"看到双链表就慌"——其实 prev 指针在本题完全无用，但考生总被结构定义干扰，忘记只看代码实际遍历路径。