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 25 · Accepted Answer · edited Dec 10 '21 at 19:54

25

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

10,733
7
77
79

answered Dec 28 '15 at 15:56

Simeon Visser

113,587
18
171
175

Is OrderedDict a tree?

1 Answers1