在哪里可以使用(双向链表)位置列表ADT?当开发人员想要 O(n)
内存和 O(1)
(非摊销行为)到列表中的任意位置时?我想看一个使用位置列表的例子。使用位置列表比使用基于数组的序列有什么优势?
最佳答案
如果您的程序经常需要向数据集合中添加新元素或从中删除元素,那么列表可能是比数组更好的选择。
删除数组中第N个元素需要对第N个元素之后的所有元素进行复制操作,原则上:
Arr[N] = Arr[N+1]
Arr[N+1] = Arr[N+2]
...
插入新元素时需要类似的副本,即为新元素腾出空间。
如果您的程序频繁添加/删除元素,许多复制操作可能会影响性能。
作为这些操作的一部分,现有元素的位置会发生变化,即在位置 50 处删除/添加元素后,位置 1000 处的元素将位于位置 999 或 1001。
如果您的程序的某些部分搜索了特定元素并保存了它的位置(例如位置 1000),这可能会成为问题。元素删除/添加操作后,保存的位置不再有效。
(双向链接)列表“解决”了所描述的 3 个问题。使用列表,您可以添加/删除元素,而无需将现有元素复制到新位置。因此,特定元素的位置(例如指向元素的指针)在添加/删除操作后仍然有效。
总结一下:如果您的程序(经常)添加或删除随机定位的元素,并且如果您的程序要求位置信息不受添加/删除操作的影响,那么列表可能是比数组更好的选择。
关于data-structures - 位置列表 ADT 的需求在哪里?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63010959/