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

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?

我想知道使用append（）构建Python v2.7列表的复杂性顺序是什么？ Python列表是双重链接的，因此它是恒定的复杂性，还是单独链接，因此是线性复杂性？如果它是单链接的，我如何在线性时间内从迭代中建立一个列表，该列表按照从开始到结束的顺序提供列表的值？

For example:

例如：

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

1 个解决方案

#1

The time complexity for python list.append() is O(1). See the Time Complexity list on the Python Wiki.

python list.append（）的时间复杂度为O（1）。请参阅Python Wiki上的Time Complexity列表。

Internally, python lists are vectors of pointers:

在内部，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;

The ob_item vector is resized as needed with overallocation to give an amortized O(1) cost for appends:

根据需要调整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);

This makes Python lists dynamic arrays.

这使得Python列出了动态数组。

#1