My initial proposal would have been to add a data structure to allow something like deque, but allowing cheaper random accesses. However I realized it was a use case more suitable for an external lib. Thinking about how I would implement such a new data structure, I imagined several possibilities, one of them would be to couple a deque with a dict or a list. However, sharing data between a deque and another data structure is hard because, while you can easily hook on the element going in (since you put them in yourself), there is no efficient way to get back an element on its way out. On lists or dicts, if you remove an element, you can pop() it and you get back the removed element. On deque, if you set a maxlen of 5 and add a 6th element, if you want to get the element that has been removed, you need to check if the maxlen has been reached, and if yes, get a reference to the first element, then add the new one. It's inconvenient and of course slower than it needs to be given that deque are quite fast. So my more modest and realistic proposal would be to add a callback on deque signature: collections.deque(iterable, maxlen, pop_callback) pop_callback would accept any callable, and call it everytime an element is removed from the deque, allowing third party libraries to then do whatever they need with it.