我想存储少量具有恒定大小（ac char）的项目（少于 255 个）并能够执行以下操作：
将值附加到任意位置并让其他项目保留其先前的顺序。
删除一个项目并让其他项目保留它们的顺序（如上）。
查找项目的下一个和上一个。
我尝试过使用数组并通过将所有项目向前移动来创建一个函数来添加一个值。删除也会发生同样的事情，但效率太低了。当然，我不介意必须使用库，只要它随时可用且免费。
问问题
92 次
2 回答
5
- 数组 - 访问：O(1)，插入：O(n)
- 双链表 - 访问 O(n)，上一个/下一个：O(1)，插入(*)：O(1)
- 存储子节点数量的 RB 树：所有操作的 O(log n)。
(*)：您需要先遍历列表才能到达位置 (O(n))。
注意：不，数组并不混乱，实现起来非常简单。正如您所看到的，根据使用情况，它可能非常有效。
根据元素的数量，以及您对数组实现的评论，您应该坚持使用数组。
于 2012-04-21T09:06:25.523 回答
0
您可以为此使用双链表。但是，如果您想保持数组行为（例如，通过索引快速访问元素（O(1)对于 LL，它是） ，这将不起作用）O(n)
于 2012-04-21T09:03:44.180 回答