Is OrderedDict a tree?

Question

OrderedDict is a collection that preserves order of items (in which they were inserted). I do not think this can be achieved with hashtables (which regular dict uses I think) so are balanced trees used to implement it?

I assume there are many depends like Python 2/3 and CPython/IPython/others.

I found many questions about regular dict being a hashtable but nothing on OrderedDict. — ArekBulski, Dec 28 '15 at 15:56
It can be achieved with a hashtable in combination with an ordered list, such as a linked list. — khelwood, Dec 28 '15 at 15:56
Not quite a duplicate *question*, but the accepted *answer* (from one of the core developers, no less) explains a bit about how it's implemented in CPython. — jonrsharpe, Dec 28 '15 at 15:58
@jonrsharpe not just any core developer but the dude who wrote Timsort! — John Red, Mar 16 '22 at 02:07

score 26 · Accepted Answer · edited Dec 10 '21 at 19:54

26

You can read the implementation in CPython's source code: Lib/collections/__init__.py as OrderedDict is implemented in Python.

It uses a doubly linked list to maintain the order of the elements in the dictionary.

edited Dec 10 '21 at 19:54

Boris Verkhovskiy

14,854
11
100
103

answered Dec 28 '15 at 15:56

Simeon Visser

118,920
18
185
180

Is OrderedDict a tree?

1 Answers1