Python列表的底层数据结构是什么?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (54)

用于实现Python内置列表数据类型的典型底层数据结构是什么?

提问于
用户回答回答于

列表对象被实现为数组。它们针对快速固定长度操作进行了优化,并为pop(0)和insert(0,v)操作带来了改变底层数据表示大小和位置的O(n)内存移动成本。

用户回答回答于

CPython的:

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;

从下面一行可以看出,列表被声明为一个指向数组的指针PyObjects

PyObject **ob_item;

扫码关注云+社区

领取腾讯云代金券