blocks|key|1546656|text|CPython：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1546657|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;|code-block|syntax|javascript|1546658|从下面的代码行可以看到，该列表被声明为指向PyObjects的指针数组。|offset|length|style|CODE|1546659|PyObject+**ob_item;|1546660|entityMap^0|0|0|L|9|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|S|8|@$I|T|J|U|K|L]]|9|@]|A|$]]|$1|M|3|N|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

CPython:

<pre><code>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 &lt;= ob_size &lt;= 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;
</code></pre>

As can be seen on the following line, the list is declared as an array of pointers to <code>PyObjects</code>.

<pre><code>PyObject **ob_item;
</code></pre>

blocks|key|1331370|text|在Jython+implementation中，它是一个ArrayList<PyObject>。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1331371|entityMap|0|LINK|mutability|MUTABLE|url|http://fisheye3.atlassian.com/browse/jython/trunk/jython/src/org/python/core/PyList.java?r1=6244&r2=6257&u=-1&ignore=&k=^0|S|J|1|L|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@$9|O|A|P|B|C]]|D|@$9|Q|A|R|1|S]]|E|$]]|$1|F|3|-4|5|6|7|T|8|@]|D|@]|E|$]]]|G|$H|$5|I|J|K|E|$L|M]]]]

In the <a href="http://fisheye3.atlassian.com/browse/jython/trunk/jython/src/org/python/core/PyList.java?r1=6244&amp;r2=6257&amp;u=-1&amp;ignore=&amp;k=" rel="noreferrer">Jython implementation</a>, it's an <code>ArrayList&lt;PyObject&gt;</code>.

blocks|key|1546790|text|尽管这可能很明显，但值得一提的是，Python列表是Dynamic数组(与Static数组相对)。这是在求职面试问题/学术界中出现的一个重要区别。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1546791|因为数组是动态的，所以Python在声明时保留一定数量的内存，例如：|1546792|somelist+=+[]|code-block|syntax|javascript|1546793|因为已经预留了额外的内存，所以执行somelist.append()只会写入下一个保留的内存槽，因此大部分时间都是O(1)。对于静态数组，通常数组已满(即如果有4个字节，则数组大小为4)，并且追加将始终为O(n)，因为它们需要保留一组全新的内存(现在可能为5个字节)并复制内容。|1546794|entityMap^0|Q|7|11|6|0|0|0|H|H|1L|4|2U|4|0^^$0|@$1|2|3|4|5|6|7|Q|8|@$9|R|A|S|B|C]|$9|T|A|U|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|V|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|W|8|@]|D|@]|E|$K|L]]|$1|M|3|N|5|6|7|X|8|@$9|Y|A|Z|B|C]|$9|10|A|11|B|C]|$9|12|A|13|B|C]]|D|@]|E|$]]|$1|O|3|-4|5|6|7|14|8|@]|D|@]|E|$]]]|P|$]]

Although it may be obvious, worth stating that Python lists are <code>Dynamic</code> arrays (as opposed to <code>Static</code> arrays). This is an important distinction that comes up in job interview questions/academia.
Because the array is dynamic, Python reserves an amount of memory upon declaration, eg:
<pre><code>somelist = []
</code></pre>
Because extra memory already is set aside, performing <code>somelist.append()</code> simply writes to the next reserved memory slot(s) and hence is <code>O(1)</code> most of the time. For a static array, typically the array is full (ie. if have 4 bytes, then array size is 4) and appends would always be <code>O(n)</code> because they require reserving an entirely new set of memory (maybe 5 bytes now) and copying contents over.

What is the typical underlying data structure used to implement Python's built-in list data type?

What is the underlying data structure for Python lists?

数据结构

Python

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

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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