[单选题]在实现队列的链表结构中, 其时间复杂度最优的是( )

A

仅设置头指针的单循环链表

B

仅设置尾指针的单循环链表

C

仅设置头指针的双向链表

D

仅设置尾指针的双向链表

正确答案:B
题目解析

如果只设头指针:则出列容易,头指针往后移一个就行;入列则要遍历整个队列,确定队尾后再插入,所以出列是O(1),入列是O(n) 。

如果只设尾指针:则入列时直接插入,出列只须后移一个结点即可找到队头结点,都是常数级的时间耗费,即都是O(1)

在单链表中,如果让最后一个结点的指针域指向第一个结点可以构成循环链表。

故如果从时间和空间两方面考虑,单循环链表优于双向链表。故综合考虑选B。

扫描二维码
免费搜题、免费刷题、免费查看解析