问题
单项选择题
在链表结构中,采用______可以用最少的空间代价和最高的时间效率实现队列结构。
A.仅设置尾指针的单向循环链表
B.仅设置头指针的单向循环链表
C.仅设置尾指针的双向链表
D.仅设置头指针的双向链表
答案
参考答案:A
解析:
[分析]: 循环链表和单链表相比,不同之处在于链表中表尾结点中的“指针域”并不是指向Null,而是指向链表的头结点,这样只要知道表中任何一个结点的地址,就能够遍历表中其他任一结点。因此循环链表每个结点所需的空间和单链表是一样的,和双向链表相比空间代价要小得多。
队列只需要在头(通过尾结点可访问)、尾结点(通过尾指针可以获得)进行操作。但如果设置了头指针,那么寻找队尾需要遍历整个队列;而如果设置了尾指针,而可以很快找到头结点,因此设置尾指针的时间效率更高。