问题
单项选择题
若对一个链表最常用的操作是在末尾插入结点和删除尾结点,则采用仅设尾指针的单向循环链表(不含头结点)时,______。
A.插入和删除操作的时间复杂度都为O(1)
B.插入和删除操作的时间复杂度都为O(n)
C.插入操作的时间复杂度为O(1),删除操作的时间复杂度为O(n)
D.插入操作的时间复杂度为O(n),删除操作的时间复杂度为O(1)
答案
参考答案:C
解析:本题考查数据结构与算法基础知识。 设尾指针的单向循环链表(不含头结点)如下图所示: 设结点的指针域为next,新结点的指针为s,则在尾指针所指结点后插入结点的操作为: 也就是插入操作的时间复杂度为O(1)。 要删除尾指针所指结点,必须通过遍历操作找到尾结点的前驱结点,其操作序列 如下: 也就是说,删除操作的时间复杂度为O(n)。