O(1) indexable deque of integers in Python

Question

what are my options there? I need to call a lot of appends (to the right end) and poplefts (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 O(1).

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).

I come from a Lisp background and was amazed to learn that in Python removing a head element from a list is an O(n) operation. A deque could be an answer except the documentation says access is O(n) in the middle. Is there anything else, pre-built?

Answer 1

You can get an amortized O(1) data structure by using two python lists, one holding the left half of the deque and the other holding the right half. The front half is stored reversed so the left end of the deque is at the back of the list. Something like this:

class mydeque(object):

  def __init__(self):
    self.left = []
    self.right = []

  def pushleft(self, v):
    self.left.append(v)

  def pushright(self, v):
    self.right.append(v)

  def popleft(self):
    if not self.left:
      self.__fill_left()
    return self.left.pop()

  def popright(self):
    if not self.right:
      self.__fill_right()
    return self.right.pop()

  def __len__(self):
    return len(self.left) + len(self.right)

  def __getitem__(self, i):
    if i >= len(self.left):
      return self.right[i-len(self.left)]
    else:
      return self.left[-(i+1)]

  def __fill_right(self):
    x = len(self.left)//2
    self.right.extend(self.left[0:x])
    self.right.reverse()
    del self.left[0:x]

  def __fill_left(self):
    x = len(self.right)//2
    self.left.extend(self.right[0:x])
    self.left.reverse()
    del self.right[0:x]

I'm not 100% sure if the interaction between this code and the amortized performance of python's lists actually result in O(1) for each operation, but my gut says so.