CodeMonkey@programming.devtoPython@programming.dev•Python Big O: the time complexities of different data structures in Python
3·
11 days agoI 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.
I am used to seeing ring buffers implemented using an array. They are FIFO if you write to the maximum offset and read from the minimum offset but they are double ended if you have a method to read from the maximum offset and write to the minimum offset.