Python列表是单向链表还是双向链表？

Question

我想知道在Python v2.7中，使用append()方法构建一个列表的复杂度是什么样的？Python的列表是双向链表，所以它的复杂度是常数级别，还是单向链表，所以它的复杂度是线性级别？如果是单向链表的话，我该如何在时间复杂度为线性的情况下，从一个提供列表值的迭代中，按顺序从头到尾构建一个列表呢？

例如：

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 <= low - 1:
      holes.append((prec, low - 1))
    prec = high + 1
  return holes

Answer 1

在Python中，使用list.append()这个方法添加元素的时间复杂度是O(1)。你可以在Python维基百科上查看时间复杂度的相关信息。

从内部结构来看，Python的列表其实是指针的集合：

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

当需要增加元素时，ob_item这个指针集合会进行调整，并且会预留一些空间，这样在添加元素时平均下来每次的时间复杂度都是O(1)：

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

这就使得Python的列表成为了动态数组。