A deque is a data structure that exists outside of Python and the only 
guarantee is that adding an element at the top or the front is O(1). Giving 
more guarantee would force trade-offs and impose them to other implementations. 
If you want fast deletion, you should use another data structure.

Also, removing an element from a doubly-linked list is not a O(1) operation, 
it's O(n). It's O(1) once you have a pointer to the element but you have to 
iterate over the list to get it and that would take O(n) operations, so making 
deque a doubly-linked list would not be faster anyway.

I think the data structure that you are looking for would be a skipped-list, or 
alternatively (but the implementation is more involved) a red-black tree.
_______________________________________________
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at 
https://mail.python.org/archives/list/python-ideas@python.org/message/JXI3KKZZBD4ORTBKMZVMC7XNUNIK7DYB/
Code of Conduct: http://python.org/psf/codeofconduct/

Reply via email to