data-structures - 我的应用程序的最佳链接列表或 BST 是什么

Question

我的任务是开发一个电子电话簿，我必须在其中存储公司员工的姓名和电话号码。您可用的数据结构是链表和二叉搜索树 (BST)，我必须为我的项目选择最受支持的数据结构。此外，在选择任何数据结构时，还必须考虑插入、删除和搜索操作，因为公司可以雇佣一些新员工，搜索一个员工的电话号码，一些老员工也可以离开这个公司。讨论您认为哪种数据结构更适合上述场景。还要讨论为什么您更喜欢这种数据结构而不是其他的原因？

Answer 1

BST会更好。因为...

1. 在 BST 中搜索电话簿中最常用的功能比在链表中更快。

2. 在平均情况下，插入需要 O(log n) 时间。在链表的情况下，如果要插入一个新节点，找到正确的位置需要 O(n) 时间，这再次比 BST 慢。

3. 删除：最坏的情况是它需要的时间与树的高度成正比。但是在链表的情况下需要恒定的订购时间。（这是链表更好的唯一情况。）

因此，平均链表更好。

PS：我假设您想以排序方式存储电话簿。