Why are Python lists implemented as dynamic arrays instead of ring buffers?

Question

A list in Python is now implemented as dynamic array of pointers, so it's not suitable for insertion and deletion at the front end. However, ring buffer also supports O(1) indexing. It can also expand and shrink like a dynamic array to support O(1) amortized insertion and deletion at both end. Why didn't CPython choose this implementation, or what's the main disadvantage of it?

Answer 1

With a ring buffer, you'd need some index transformation on every access, unless the start position happens to be at index 0. But even then, you'd have to check for the start position to be 0.

O(1) just means that the operation has fixed cost, but it doesn't tell you whether that fixed cost is high or low. With a dynamic array, the cost of accessing an element by index is as low as it can get: check the range, then access the item.

The Python FAQ on the topic doesn't discuss alternative implementation techniques, but it does mention accessing elements by index as an optimization target: https://docs.python.org/3/faq/design.html#how-are-lists-implemented-in-cpython