题29

题29

题目

一个链表最常用的操作是在最后一个元素后插入一个元素和删除第一个元素, 则选用 （ ）最节省时间.
A. 不带头结点的单循环链表
B. 双链表
C. 单链表
D. 不带头结点且有尾指针的单循环链表

分析

对于 ,在最后一个元素之后插入元素的情况与普通单链表相同,时间复杂度为 ;
而删除第一个元素时, 为保持单循环链表的性质 (尾结点指向第一个结点), 要先遍历整个链表找到尾结点,再做删除操作,时间复杂度为 。
对于 ,双链表的情况与单链表的相同, 一个是 ,一个是 。
对于 ,在最后一个元素之后插入一个元素,要遍历整个链表才能找到插入位置,时间复杂度为 ;
删除第一个元素的时间复杂度为 。
对于 ,与 的分析对比,有尾结点的指针,省去了遍历链表的过程,因此时间复杂度均为 。

解

D