title: Is a Python list a singly or doubly linked list?
body: <p>I'm wondering what the order of complexity for a Python v2.7 list being built up using append() is?  Is a Python list doubly linked and thus it is constant complexity or is it singly linked and thus linear complexity?  If it is singly linked, how can I in linear time build up a list from an iteration that provides the values of the list in the order of from beginning to end?</p>
  
  <p>For example:</p>
  
  <pre><code>def holes_between(intervals):
    # Compute the holes between the intervals, for example:
    #     given the table: ([ 8,  9] [14, 18] [19, 20] [23, 32] [34, 49])
    #   compute the holes: ([10, 13] [21, 22] [33, 33])
    prec = intervals[0][1] + 1 # Bootstrap the iteration
    holes = []
    for low, high in intervals[1:]:
      if prec &lt;= low - 1:
        holes.append((prec, low - 1))
      prec = high + 1
    return holes
  </code></pre>