大门| 2017大门模拟II |问题21

哪种数据结构最适合实现具有以下三个特征的值集合？ i） 项目将按FIFO顺序从集合中检索和移除。 ii）收藏中的物品数量没有先验限制。 iii）相对于内存地址所需的存储空间而言，项目的大小较大。 （A） 带有头指针和尾指针的单链表 （B） 只有头指针的双链表 （C） 二叉树 （D） 哈希表 答复: （A） 说明： 如果我们按照FIFO顺序访问元素，单链接列表中的头指针和尾指针将使插入和删除的时间复杂度达到O（1）。

在双链接列表中，由于只给出了头指针，所以对于插入，我们必须遍历完整的链接列表，所以插入将是O（n），因此不合适。

在二叉树中，我们只有一个指向根的指针。二叉树中的插入和删除将被删除 O（logn）所以不合适。

在哈希表中，无法以FIFO顺序访问数据。 这个问题的小测验