Python Big O: the time complexities of different data structures in Python

The time complexity of common operations on Python's many data structures.

8 comments

Zero surprises. It's the same as in any other language.
- And thank god for that. Theoretical computer science is still good ;)
- I was a bit surprised that deque is implemented as a linked list and not, for example, a ring buffer. It would mean that index reads would be constant time (though insert and delete at an index would be linear time), the opposite of using a linked list.
  
  But a ring buffer is a FIFO data structure that can be implemented using linked lists. What ring buffer implementation did you have in mind?

You've viewed 8 comments.