首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >Python列表的底层数据结构是什么?

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

Stack Overflow用户
提问于 2009-05-27 06:22:56
回答 3查看 17.4K关注 0票数 81

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

EN

回答 3

Stack Overflow用户

发布于 2009-05-27 06:29:29

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;
票数 30
EN

Stack Overflow用户

发布于 2009-05-27 06:35:04

Jython implementation中,它是一个ArrayList<PyObject>

票数 13
EN

Stack Overflow用户

发布于 2020-07-19 02:02:34

尽管这可能很明显,但值得一提的是,Python列表是Dynamic数组(与Static数组相对)。这是在求职面试问题/学术界中出现的一个重要区别。

因为数组是动态的,所以Python在声明时保留一定数量的内存,例如:

somelist = []

因为已经预留了额外的内存,所以执行somelist.append()只会写入下一个保留的内存槽,因此大部分时间都是O(1)。对于静态数组,通常数组已满(即如果有4个字节,则数组大小为4),并且追加将始终为O(n),因为它们需要保留一组全新的内存(现在可能为5个字节)并复制内容。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/914233

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档