是否存在可以在 O(n) 中以插入顺序和数量级遍历的数据结构，最多 O(log(n)) 插入和删除？
换句话说，给定元素 5、1、4、3、2（按此顺序插入），它可以按O(n) 时间1,2,3,4,5或按5,1,4,3,2O(n) 时间遍历。
当然我可以使用一个数组并在遍历之前简单地对其进行排序，但这需要一个 O(n*log(n)) 预遍历步骤。另外，我可以使用多链表来实现 O(n) 遍历，但在这种情况下，插入和删除操作也会花费 O(n)，因为我不能保证最新的元素一定是最大的。
如果存在这样的数据结构，请给我一个正式的名称，以便我可以进一步研究它，或者如果它没有，一个简短的表面级描述将不胜感激。
谢谢
一种还允许次线性删除的解决方案是构建一个数据结构D，该结构使用链表D.L按插入顺序进行遍历，并使用排序树按D.T数量级进行遍历。但是如何链接它们以在亚线性时间内额外实现删除操作？诀窍是不应该D.T存储值，而只是对中相应链表元素的引用。D.L
插入：在时间 O(1) 中追加，并在时间 O(log(n)) 中D.L插入对附加元素的引用。D.T当然，任何比较D.T都是在参考值上进行的，而不是参考本身）
按插入顺序（或向后）遍历：简单地D.L在时间 O(n) 中线性遍历
按数量级（或向后）遍历：只需D.T通过 tree-walk 在时间 O(n) 中遍历
删除D.T：首先在 O(log n) 时间内找到并删除元素，这也为您提供了正确的元素引用D.L，因此可以D.L在 O(1) 时间内将其删除。
评论者是对的：您最好的选择是将对象存储两次：一次在链表中（插入顺序），一次在二叉树中（内在排序顺序）。
这并不像听起来那么糟糕，因为您不必复制对象，因此唯一的成本是列表/树脚手架，这将花费您存储的每个对象 4 个机器字。
你甚至不需要两个数据结构。只需使用二叉树，而不是插入对象，而是将其包装在一个对象中，该对象还包含指向前一个和下一个对象的指针。这在像 java 这样的主流语言中是相当简单的，您可以使用带有比较器的默认树实现来按属性对树进行排序。
只要您保留对第一个和最后一个元素的引用，您就可以使用对象的内部指针按顺序遍历它们。