问题
单项选择题
如果对含有n(n＞1)个元素的线性表的运算只有4种：删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后—个元素的后面插入新元素，则最好使用( )。
A．只有尾结点指针没有头结点指针的循环单链表
B．只有尾结点指针没有头结点指针的非循环单链表
C．只有头结点指针没有尾结点指针的循环单链表
D．既有头结点指针也有尾结点指针的循环单链表
答案
参考答案：C
解析：对于A的链表，删除最后一个结点p时，需要找到p的前一个结点，其时间复杂度为O(n)；对于B的链表，删除第一个结点的p时，需找到头结点，这里没给出头结点指针，故无法实现这种操作。对于C的链表，这4种操作的时间复杂度都为O(1)，对于D的链表，删除最后一个结点p时，需要找到p的前一个结点，其时间复杂度为O(n)。