7

I was going through this answer on Stack Overflow. I came to know about existence of OrderedSet in Python. I would like to know how it is implemented internally. Is it similar to hash table implementation of sets?

Also, what is the time complexity of some of the common operations like insert, delete, find, etc.?

Anatolii
  • 14,139
  • 4
  • 35
  • 65
likecs
  • 353
  • 2
  • 13
  • Did you read the [linked documentation](http://orderedset.readthedocs.io/en/latest/)? OrderedSet isn't part of the standard library. – jonrsharpe Feb 27 '18 at 08:06
  • Thanks for the link @jonrsharpe. The [link](http://code.activestate.com/recipes/576694/) to the implementation was useful – likecs Feb 27 '18 at 08:43
  • @likecs then maybe you could answer your own question. – Anatolii Dec 19 '19 at 21:42

1 Answers1

4

From the documentation available here

Implementation based on a doubly linked link and an internal dictionary. This design gives OrderedSet the same big-Oh running times as regular sets including O(1) adds, removes, and lookups as well as O(n) iteration.

There is also a discussion on the topic, see Does Python have an ordered set?

teoML
  • 784
  • 4
  • 13