本文将介绍列表在 CPython中的实现，因为毕竟Cpython 又是 Python 最为常用的实现。
Python 中的列表非常强大，看看它的内部实现机制是怎么样的，一定非常有趣。
下面是一段 Python 脚本，在列表中添加几个整数，然后打印列表。
Python
1
2
3
4
5
6
7
8
9
10
11
12
>>>l=[]
>>>l.append(1)
>>>l.append(2)
>>>l.append(3)
>>>l
[1,2,3]
>>>foreinl:
... PRinte
...
1
2
3
可以发现，列表是一个迭代器。
列表对象的 C 语言结构体Cpython 中的列表实现类似于下面的 C 结构体。ob_item 是指向列表对象的指针数组。allocated 是申请内存的槽的个数。
Python
1
2
3
4
5
typedefstruct{
PyObject_VAR_HEAD
PyObject**ob_item;
Py_ssize_tallocated;
}PyListObject;
列表初始化看看初始化一个空列表的时候发生了什么，例如：l = []。
Python
1
2
3
4
5
6
7
8
9
arguments:sizeofthelist=0
returns:listobject=[]
PyListNew:
nbytes=size*sizeofglobalPythonobject=0
allocatenewlistobject
allocatelistofpointers(ob_item)ofsizenbytes=0
clearob_item
setlist'sallocatedvarto0=0slots
returnlistobject
要分清列表大小和分配的槽大小，这很重要。列表的大小和 len(l) 的大小相同。分配槽的大小是指已经在内存中分配了的槽空间数。通常分配的槽的大小要大于列表大小，这是为了避免每次列表添加元素的时候都调用分配内存的函数。下面会具体介绍。
Append 操作向列表添加一个整数：l.append(1) 时发生了什么？调用了底层的 C 函数 app1()。
Python
1
2
3
4
5
6
7
arguments:listobject,newelement
returns:0ifOK,-1ifnot
app1:
n=sizeoflist
calllist_resize()toresizethelisttosizen+1=0+1=1
list[n]=list[0]=newelement
return0
下面是 list_resize() 函数。它会多申请一些内存，避免频繁调用 list_resize() 函数。列表的增长模式为：0，4，8，16，25，35，46，58，72，88……
Python
1
2
3
4
5
6
7
arguments:listobject,newsize
returns:0ifOK,-1ifnot
list_resize:
new_allocated=(newsize>>3)+(newsize<9?3:6)=3
new_allocated+=newsize=3+1=4
resizeob_item(listofpointers)tosizenew_allocated
return0
现在分配了 4 个用来装列表元素的槽空间，并且第一个空间中为整数 1。如下图显示 l[0] 指向我们新添加的整数对象。虚线的方框表示已经分配但没有使用的槽空间。
列表追加元素操作的平均复杂度为 O(1)。
继续添加新的元素：l.append(2)。调用 list_resize 函数，参数为 n+1 = 2， 但是因为已经申请了 4 个槽空间，所以不需要再申请内存空间。再添加两个整数的情况也是一样的：l.append(3)，l.append(4)。下图显示了我们现在的情况。
Insert 操作在列表偏移量 1 的位置插入新元素，整数 5：l.insert(1,5)，内部调用ins1() 函数。
Python
1
2
3
4
5
6
7
arguments:listobject,where,newelement
returns:0ifOK,-1ifnot
ins1:
resizelisttosizen+1=5->4moreslotswillbeallocated
startingatthelastelementuptotheoffsetwhere,rightshifteachelement
setnewelementatoffsetwhere
return0
虚线的方框依旧表示已经分配但没有使用的槽空间。现在分配了 8 个槽空间，但是列表的大小却只是 5。
列表插入操作的平均复杂度为 O(n)。
Pop 操作取出列表最后一个元素 即l.pop()，调用了 listpop() 函数。在 listpop() 函数中会调用 list_resize 函数，如果取出元素后列表的大小小于分配的槽空间数的一半，将会缩减列表的大小。
Python
1
2
3
4
5
6
7
8
arguments:listobject
returns:elementpopped
listpop:
iflistempty:
returnnull
resizelistwithsize5-1=4.4isnotlessthan8/2sonoshrinkage
setlistobjectsizeto4
returnlastelement
列表 pop 操作的平均复杂度为 O(1)。
可以看到 pop 操作后槽空间 4 依然指向原先的整数对象，但是最为关键的是现在列表的大小已经变为 4。
继续 pop 一个元素。在 list_resize() 函数中，size – 1 = 4 – 1 = 3 已经小于所分配的槽空间大小的一半，所以缩减分配的槽空间为 6，同时现在列表的大小为 3。
可以看到槽空间 3 和 4 依然指向原先的整数，但是现在列表的大小已经变为 3。
Remove 操作Python 的列表对象有个方法，删除指定的元素： l.remove(5)。底层调用 listremove() 函数。
Python
1
2
3
4
5
6
7
8
arguments:listobject,elementtoremove
returnsnoneifOK,nullifnot
listremove:
loopthrougheachlistelement:
ifcorrectelement:
slicelistbetweenelement's slot and element'sslot+1
returnnone
returnnull
为了做列表的切片并且删除元素，调用了 list_ass_slice() 函数，它的实现方法比较有趣。我们在删除列表位置 1 的元素 5 的时候，低位的偏移量为 1 同时高位的偏移量为 2.
Python
1
2
3
4
5
6
7
arguments:listobject,lowoffset,highoffset
returns:0ifOK
list_ass_slice:
copyinteger5torecyclelisttodereferenceit
shiftelementsfromslot2toslot1
resizelistto5slots
return0
列表 remove 操作的复杂度为 O(n)。
全能程序员交流QQ群290551701，群内程序员都是来自，百度、阿里、京东、小米、去哪儿、饿了吗、蓝港等高级程序员 ，拥有丰富的经验。加入我们，直线沟通技术大牛，最佳的学习环境，了解业内的一手的资讯。如果你想结实大牛，那 就加入进来，让大牛带你超神！