weixin_41175251
菜菜小杨
2020-07-12 17:21
采纳率: 100%
浏览 127

一个数据结构的选择题 !!!

某线性表只在头尾两端进行插入和删除,则____是最佳的存储方式。

A. 仅含有头指针,带头结点循环双链表
B. 仅含有尾指针,带头结点的单循环链表

答案是B ,我选的A
我感觉在进行删除操作时需要找到尾结点的前驱结点,如果是B的话就要遍历整个链表才行
,而A的话则只需要从头结点后移两步就找到了尾结点的前驱,这样效率不是更高么?
是我理解错了么?

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

4条回答 默认 最新

  • caozhy
    已采纳

    ab效率一样,但是a存储更大,所以选b。

    点赞 评论
  • qq_42734954
    低级用户 2020-07-12 23:25

    A无疑可以快速找到头尾位置,B如果是仅含头指针就需要O(n)找尾,但B有尾,头即是尾的下一个,AB效率因此一样,A是双链,内存大。所以选B.

    点赞 1 评论
  • qq_39812061
    qq_39812061 2020-07-12 19:12

    尾指针表示的单循环链表存储时,很容易找到线性表的首、尾元素。

    点赞 评论
  • qiu_shaofeng
    qiu_shaofeng 2020-07-12 20:33

    B删除尾节点还是需要遍历链表,插入尾节点是O(1)

    点赞 评论

相关推荐