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 <rep...@bugs.python.org> <https://bugs.python.org/issue31265> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
