[issue31265] Remove doubly-linked list from C OrderedDict

[INADA Naoki]

INADA Naoki added the comment:

>  I'm unclear about whether you understand and acknowledge why the doubly-linked list was chosen and what kind of workloads it supports (we didn't choose it because it was either convenient or fun, we chose it because it was an algorithmically correct way of supporting arbitrary deletion, move-to-front, move-to-back, pop-first, and pop-last operations all of which have legitimate use cases).

Arbitrary deletion: New and current implementation has same complexity, because current implementation relying on dict deletion.  Only difference is current implementation need to remove item from link list, not only dict.

move-to-front, move-to-back: Current implementation is worst case O(1) and new implementation is amortized O(1), like insertion.

pop-first, pop-last: Current implementation is worst case O(1).  New implementation is typical case (when dict is dense) O(1).  When mixed with arbitrary deletion operation (dict is sparse), it's become amortized O(1).

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue31265>
_______________________________________