# Re-implement ordered dict

**URL:** <https://discuss.python.org/t/re-implement-ordered-dict/18199>\
**Category:** Ideas\
**Created:** [August 14, 2022, 6:35am UTC](https://discuss.python.org/t/re-implement-ordered-dict/18199 "2022-08-14T06:35:31Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![matthiasgoergens](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/matthiasgoergens/32/8338_2.png) [@matthiasgoergens](https://discuss.python.org/u/matthiasgoergens)\
**Post date:** [August 14, 2022, 6:35am UTC](https://discuss.python.org/t/re-implement-ordered-dict/18199/1 "2022-08-14T06:35:31Z")

</div>

Currently, ordered dicts are implemented with the help of a linked list. A while ago, ordinary dicts became ordered.

I would like to give re-implementing ordered dicts without linked lists a try.

However, I want to avoid duplicating work. Could you please point me to some existing efforts, if any? I tried to search myself, but didn’t find much. Thanks!

P.S. The main algorithmic difficulty I see is supporting ordered-dict’s move-to-front functionality. The rest seems pretty straightforward, if a bit tedious. What’s your take?

---

<div class="post-metadata">

**Author:** ![storchaka](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/storchaka/32/217_2.png) [@storchaka](https://discuss.python.org/u/storchaka)\
**Post date:** [August 14, 2022, 7:14am UTC](https://discuss.python.org/t/re-implement-ordered-dict/18199/2 "2022-08-14T07:14:37Z")

</div>

See [Remove doubly-linked list from C OrderedDict · Issue #75448 · python/cpython · GitHub](https://github.com/python/cpython/issues/75448).

In short: you cannot make `move_to_end()` in O(1) time. You can make it in O(1) amortized time, but not in O(1) guaranteed time.

---

<div class="post-metadata">

**Author:** ![matthiasgoergens](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/matthiasgoergens/32/8338_2.png) [@matthiasgoergens](https://discuss.python.org/u/matthiasgoergens)\
**Post date:** [August 14, 2022, 3:03pm UTC](https://discuss.python.org/t/re-implement-ordered-dict/18199/3 "2022-08-14T15:03:03Z")

</div>

Thanks, again!

I see that this issue was from quite a while ago, before the dicts being ordered was well established.

I don’t really understand the problem they are bringing up with amortised vs worst case performance: almost everything about dicts only makes amortised claims. Or worse, collision handling only makes claims for the ‘average’ case of input.

Btw, if you want to see it, I can `make move_to_end` take worst case O(1) time (without linked lists). With a similar technique that also could be used to make inserts take O(1) worst case time. Basically, ‘lazy’ rebuilding, instead of compacing everything at once.

But I am not sure the extra implementation complexity would be worth it.

---

<div class="post-metadata">

**Author:** ![KubaSO](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/kubaso/32/9044_2.png) [@KubaSO](https://discuss.python.org/u/KubaSO)\
**Post date:** [September 20, 2022, 11:16pm UTC](https://discuss.python.org/t/re-implement-ordered-dict/18199/4 "2022-09-20T23:16:13Z")

</div>

This is an idea similar to incremental garbage collection driven in small steps by allocations. It also thrashes less cache per dictionary operation. If it can be implemented cleanly then I’d look forward to this (as a user).
