title: O(1) indexable deque of integers in Python
body: <p>what are my options there? I need to call a lot of <code>append</code>s (to the right end) and <code>popleft</code>s (from the left end, naturally), but also to read from the middle of the storage, which will steadily grow, by the nature of the algorithm. I would like to have all these operations in <code>O(1)</code>.</p>
  
  <p>I could implement it in C easy enough on circularly-addressed array (what's the word?) which would grow automatically when it's full; but what about Python? Pointers to other languages are appreciated too (I realize the "collections" tag is more Java etc. oriented and would appreciate the comparison, but as a secondary goal).</p>
  
  <p>I come from a Lisp background and was amazed to learn that in Python removing a head element from a list is an <code>O(n)</code> operation. A <code>deque</code> could be an answer except the documentation says access is <code>O(n)</code> in the middle. Is there anything else, pre-built?</p>