若某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点,要使操作时间最少,应选择的存储结构是( )

若某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点,要使操作时间最少,应选择的存储结构是( )


A、

无头结点的单向链表


B、

带头结点的单向链表


C、

带头结点的双循环链表


D、

带头结点的单循环链表


【正确答案】:C
【题目解析】:

双向循环链表:是一种对称结构,既可以直接访问前驱结点又可以直接访问后继结点,找前驱结点和后继结点的时间复杂度均为O(1)。双向循环链表适合应用在需要经常查找结点的前驱和后继的场合。即在最后一个结点之后插入一个新结点或删除最后一个结点用双向循环链表比较合适。选C。

单链表:允许从一个结点直接访问它的后继结点,所以,找直接后继结点的时间复杂度是O(1)。但找其前驱不方便。


Top