一个线性表采用链式存储结构,头结点为head,以下哪个操作的时间复杂度与链表长度无关?
答案解析
核心考点说明:本题考察链表的基本操作的时间复杂度。解题思路分析:链表头部插入和删除操作,直接修改头指针和节点的指针域即可,时间复杂度为O(1),其他操作需要遍历链表。选项分析:A. 错误,查找最后一个节点需要遍历整个链表,时间复杂度为O(n); B. 正确,在链表头部插入节点只需要修改头指针,时间复杂度为O(1); C. 错误,删除指定节点需要遍历链表找到其前驱节点,最坏情况时间复杂度为O(n); D. 错误,查找指定值需要遍历链表,时间复杂度为O(n)。易错点提醒:链表的插入和删除操作如果只针对头部或给出结点指针,时间复杂度为O(1),否则需要遍历查找,复杂度为O(n)。
正确答案:B