title: Difference between queue implementations in Python
body: <p>One of the <a href="http://interactivepython.org/courselib/static/pythonds/BasicDS/ProgrammingExercises.html" rel="nofollow noreferrer">exercises</a> (namely, #6) asks us to compare performance of queue implementations (with head in the beinning / at the end of a list). That sounds like there could be some difference, so I tried to figure it out. Here's my code</p>
  
  <pre><code>import timeit
  
  class QueueStart(object):
      '''Queue implementation with head in the beginning of a list'''    
      def __init__(self):
          self.items = []
  
      def enqueue(self, i):
          self.items.append(i)
  
      def dequeue(self):
          return self.items.pop(0)
  
      def isEmpty(self):
          return len(self.items) == 0
  
      def size(self):
          return len(self.items)
  
  class QueueEnd(object):
      '''Queue implementation with head at the end of a list'''     
      def __init__(self):
          self.items = []
  
      def enqueue(self, item):
          self.items.insert(0, item)
  
      def dequeue(self):
          return self.items.pop()
  
      def isEmpty(self):
          return len(self.items) == 0
  
      def size(self):
          return len(self.items)
  
  # store results for further plotting
  start_add_list = [] # QueueStart.enqueue(item) runtimes for inputs of different sizes
  start_pop_list = [] # the same for QueueStart.dequeue(item)
  end_add_list = [] # the same for QueueEnd.enqueue(item) 
  end_pop_list = [] # the same for QueueEnd.dequeue(item) 
  
  for i in range(100000, 500000, 10000):
      qs = QueueStart()
      qs.items = list(range(i))
      qe = QueueEnd()
      qe.items = list(range(i))
      start_add = timeit.Timer('qs.enqueue(1)', 'from __main__ import qs')
      start_pop = timeit.Timer('qs.dequeue()', 'from __main__ import qs')
      end_add = timeit.Timer('qe.enqueue(1)', 'from __main__ import qe')
      end_pop = timeit.Timer('qe.dequeue()', 'from __main__ import qe')
  
      start_add_list.append(start_add.timeit(number=1000))
      start_pop_list.append(start_pop.timeit(number=1000))
      end_add_list.append(end_add.timeit(number=1000))
      end_pop_list.append(end_pop.timeit(number=1000))
  </code></pre>
  
  <p>And here are plots that reflect results of my experiment
  <a href="https://i.stack.imgur.com/mDY7Q.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/mDY7Q.png" alt="enter image description here"></a>
  <a href="https://i.stack.imgur.com/My1f7.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/My1f7.png" alt="enter image description here"></a></p>
  
  <p>It's known that <code>insert</code> and <code>pop(index)</code> are O(n). The interesting thing, though, is that from the graphs we see that <code>insert(0, item)</code> takes twice as long as <code>pop(0)</code>. That observation made me wonder, why this is the case. On the surface, two methods look very similar, but, apparently, under the hood there's something interesting going on. So, the question is: could you help me figure it out? </p>