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

Question

我想了解使用append()方法构建Python v2.7列表的复杂度顺序是什么？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

- WilliamKF

---

这实际上不是链表，而是动态数组的形式。你从哪里得到它是链表的想法呢？ - user395760

@delnan 有点像。与某些其他语言不同，它不是静态的，否则append根本无法工作。它更接近于Java的ArrayLists以及其他语言中的类似结构。请参见动态数组。编辑：抱歉，我一开始没有看到“动态”。你是对的，当然。 - Stjepan Bakrac

@StjepanBakrac 这就是为什么我在发布后立即将其编辑为“动态数组”;-) - user395760

我认为人们会觉得Python的列表是链接的，因为在Scheme、Lisp、Haskell、ML、Go、F#、OCaml、Clojure、Scala和许多其他语言中都是这样。在这方面，Python不遵循最小惊讶原则，并违反了关于顺序统计（即大O符号）的链表的基本假设。这使得Python更难教授，因为列表和元组不是正交数据结构。 - Jeff

Answer 1

Python中list.append()的时间复杂度为O(1)。请参阅Python Wiki上的时间复杂度列表。

在内部，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列表成为动态数组。

- Martijn Pieters

---

你分享的时间复杂度列表链接非常有帮助。谢谢。 - Sriram