题24

题24

题目

设对 个元素的线性表的运算只有 4 种：
删除第一个元素；
删除最后一个元素;
在第一个元素之前插入新元素;
在最后一个元素之后插入新元素,
则最好使用 ( ).
A. 只有尾结点指针没有头结点指针的循环单链表
B. 只有尾结点指针没有头结点指针的非循环双链表
C. 只有头结点指针没有尾结点指针的循环双链表
D. 既有头结点指针又有尾结点指针的循环单链表

分析

对于 ,删除尾结点 *p 时,需要找到 *p 的前一个结点,时间复杂度为 O(n) 。
对于 ,删除首结点 *p 时,需要找到 *p 结点,这里没有直接给出头结点指针,而通过尾结点的 prior 指针找到 *p 结点的时间复杂度为 O(n) 。
对于 ,删除尾结点 *p 时,需要找到 *p 的前一个结点,时间复杂度为 O(n) 。
对于 ,执行这四种算法的时间复杂度均为 O(1) 。

解

C