您可以使用什么数据结构动态存储元素并有效地访问它们？

Question

您可以使用什么数据结构动态存储元素并有效地访问它们？这是一个面试问题.我应该回答std::list(我的意思是在C++中)？或其他人？

作为后续问题,在最坏的情况下,在链表中查找任何元素的复杂性是多少？

感谢您的所有意见.

Answer 1

这个问题很模糊.我们拥有多个数据结构的全部原因是它们都比其他数据结构更高效或更低效地支持不同的访问模式.例如:

• 如果所有访问都是从列表的开头开始,则链表是一个很好的选择.
• 如果访问是随机的并且插入/删除结束,则动态数组是一个不错的选择.
• 如果访问始终是FIFO,则堆栈是一个不错的选择.
• 如果访问始终是LIFO,则队列是一个不错的选择.
• 如果访问总是在最后,那么deque是一个不错的选择.
• 如果访问始终是最小元素,则优先级队列是一个不错的选择.
• 如果访问是完全随机的并且不需要排序,则哈希表是好的.
• 如果访问是完全随机的并且需要排序,则平衡二叉搜索树是好的.
• 如果存储的元素是字符串或其他数字,则特里是好的.
• 如果元素是空间中的点并且您想要支持范围查询或最近邻搜索,则kd树是好的.
• 如果您想知道元素如何相互连接,那么union-find结构就很好.
• 如果值是整数,访问是随机的,并且您希望它们按顺序排列,则van Emde Boas树很好.
• 如果要将元素存储为几何结构并且想要访问特定面附近的点和边(或反之亦然),则quadedge是好的.
• 等等

这个问题有很多好的答案取决于你想要对数据做什么.这个列表只是对那些数据结构的一小部分抽样,根据具体情况,所有数据结构都可能是正确答案.根据具体情况,它们也可能都是错误的答案.请记住 - 在选择数据结构时,请确保您知道您要解决的问题!

至于你的第二个问题:在最坏的情况下,在链表中找到一个元素需要花费O(n)的时间.当您搜索的元素不在链表中或者它接近结尾时,就会发生这种情况.在这种情况下,您需要一次扫描整个链表一个元素,然后才能断定相关元素是否包含在列表中.

希望这可以帮助!

Answer 2

第一个问题我会说哈希表.使用哈希表来放置和获取元素在平均情况下是O(1).链接列表在O(n)中存储的情况更糟,在O(n)中存在更糟的访问情况.数组在O(1)中存储O(1)和更糟的访问情况的情况更糟.链接列表可以非常快速地增长,其中数组需要分配新的和更大的数组,并复制现有的元素以实现动态增长的功能.

对于问题2,在链表中查找元素的复杂性是O(n),因为在更糟的情况下必须迭代列表中的所有元素(考虑元素不在列表中的情况).