python中list的实现_python list实现

python是如何实现list的

首先，我们需要知道的是，python中一切皆对象。也就是说我们的字符串是一个对象，我们的list也是一个对象，而他们也是由元类来创建。

>>> a = []
>>> a.__class__
<class 'list'>
>>> a.__class__.__class__
<class 'type'>
1
2
3
4
5

要知道什么是元类，可以进行百度，这里就不再赘述了。

再说说内存，我们知道，存储的最小单位为字节，一个字节又是由8位组成，内存就是由无数个字节按照顺序排列起来的。在Python中，所有的值都与内存打交道，例如正常的int类型或者在str类型，并且在32位机子中，一个int类型的值在内存中是由4个字节存储的，即如果你存的是1，那么在内存中，它的位即00000000 00000000 00000000 00000001，并且我们知道，字符串是由一个或多个字符组成的，一个字符在内存中是由一位存储的。

要知道，python中的list可以存放任意类型的数据，比如一个整数，比如一个新的字符串和列表等。我们知道的一个顺序表它的存放方式是一个一块连续的内存空间，并且每块内存空间都必须是相同的大小的内存单元，但是回去看我们的python，每一个下标存放的值并不一定是相同类型的值，但我们还是可以通过下表去进行查找，并且时间复杂度仍然是O（1）。这是为什么？

因为，除了最基本的顺序表，还有另一种分离式结构的顺序表，这种表他将每个值单独存放，而将存放值的地址在放在了顺序表中（类似于链表的操作）。这样一来，不管你存储的值是多大的类型的，只要你的内存空间能放下，他就会存在一个id，而这个id就被记录在了顺序表相应的内存块中。

接下来就是要知道，如何处理这个内存。都知道内存宝贵那python是如何来实现的呢？

在Python的官方实现中，list实现采用如下的策略：建立空表（或很小的表）时，系统自动分配一块能容纳8个元素的存储区；在执行插入操作时，如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大（目前阈值为50000），则改变策略，采用加一倍的方式，引入这种改变策略的方式，是为了避免出现过多的空闲存储位置。