data-structures - 位置列表 ADT 的需求在哪里？

Question

在哪里可以使用(双向链表)位置列表ADT？当开发人员想要 O(n) 内存和 O(1)(非摊销行为)到列表中的任意位置时？我想看一个使用位置列表的例子。使用位置列表比使用基于数组的序列有什么优势？

Answer 1

如果您的程序经常需要向数据集合中添加新元素或从中删除元素，那么列表可能是比数组更好的选择。

删除数组中第N个元素需要对第N个元素之后的所有元素进行复制操作，原则上:

Arr[N] = Arr[N+1]
Arr[N+1] = Arr[N+2]
...

插入新元素时需要类似的副本，即为新元素腾出空间。

如果您的程序频繁添加/删除元素，许多复制操作可能会影响性能。

作为这些操作的一部分，现有元素的位置会发生变化，即在位置 50 处删除/添加元素后，位置 1000 处的元素将位于位置 999 或 1001。

如果您的程序的某些部分搜索了特定元素并保存了它的位置(例如位置 1000)，这可能会成为问题。元素删除/添加操作后，保存的位置不再有效。

(双向链接)列表“解决”了所描述的 3 个问题。使用列表，您可以添加/删除元素，而无需将现有元素复制到新位置。因此，特定元素的位置(例如指向元素的指针)在添加/删除操作后仍然有效。

总结一下:如果您的程序(经常)添加或删除随机定位的元素，并且如果您的程序要求位置信息不受添加/删除操作的影响，那么列表可能是比数组更好的选择。