我正在寻找一个保留其元素顺序的数据结构（该数据结构可能会在数据结构的整个生命周期中发生变化，因为客户端可能会移动元素）。
它应该允许快速搜索，在给定元素之前/之后插入，删除给定元素，查找第一个和最后一个元素以及从给定元素开始的双向迭代。
什么是好的实施？
这是我的第一次尝试：
从collections.abc.Iterable和collections.abc.MutableSet派生的类，其中包含链接列表和字典。字典的键是元素，值是链表中的节点。字典将处理给定元素的节点搜索。一旦找到一个元素，链表将处理插入之前，之后，删除和迭代。将通过添加或删除相关的键/值对来更新字典。显然，使用这种方法，元素必须是可哈希的且唯一的（否则，我们将需要另一层间接层，其中每个元素都由自动分配的数字标识符表示，并且仅将这些标识符存储为键）。
在我看来，这在渐近复杂度上绝对比list或collections.deque更好，但我可能是错的。 [编辑：错误，如@roliu所指出。与list或deque不同，我无法通过O(1)中的数字索引找到元素。到目前为止，它是O(N)，但我确信如有必要，可以通过某种方法将其设置为O(log N)。]
最佳答案
在Python中使用双向链接列表并不常见。但是，您自己提出的双链表和字典解决方案具有正确的复杂性：您要求的所有操作都是O（1）。
我认为标准库中没有更直接的实现。从理论上讲，树可能不错，但也有缺点，例如O（log n）或（准确地）它们从标准库中普遍缺失。
关于python - 如何实现保留顺序并快速插入/删除的数据结构？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19355986/