深入Python列表的内部实现

本文将介绍列表在 CPython中的实现，因为毕竟Cpython 又是 Python 最为常用的实现。

Python 中的列表非常强大，看看它的内部实现机制是怎么样的，一定非常有趣。

下面是一段 Python 脚本，在列表中添加几个整数，然后打印列表。

1. >>> l = [] 
2.  
3. >>> l.append(1) 
4.  
5. >>> l.append(2) 
6.  
7. >>> l.append(3) 
8.  
9. >>> l 
10.  
11. [1, 2, 3] 
12.  
13. >>> for e in l: 
14.  
15. ...   print e 
16.  
17. ... 
18.  
19. 1 
20.  
21. 2 
22.  
23. 3  

可以发现，列表是一个迭代器。

列表对象的 C 语言结构体

Cpython 中的列表实现类似于下面的 C 结构体。ob_item 是指向列表对象的指针数组。allocated 是申请内存的槽的个数。

1. typedef struct { 
2.  
3.     PyObject_VAR_HEAD 
4.  
5.     PyObject **ob_item; 
6.  
7.     Py_ssize_t allocated; 
8.  
9. } PyListObject;  

列表初始化

看看初始化一个空列表的时候发生了什么，例如：l = []。

1. arguments: size of the list = 0 
2.  
3. returns: list object = [] 
4.  
5. PyListNew: 
6.  
7.     nbytes = size * size of global Python object = 0 
8.  
9.     allocate new list object 
10.  
11.     allocate list of pointers (ob_item) of size nbytes = 0 
12.  
13.     clear ob_item 
14.  
15.     set list's allocated var to 0 = 0 slots 
16.  
17.     return list object  

要分清列表大小和分配的槽大小，这很重要。列表的大小和 len(l) 的大小相同。分配槽的大小是指已经在内存中分配了的槽空间数。通常分配的槽的大小要大于列表大小，这是为了避免每次列表添加元素的时候都调用分配内存的函数。下面会具体介绍。

Append 操作

向列表添加一个整数：l.append(1) 时发生了什么?调用了底层的 C 函数 app1()。

1. arguments: list object, new element 
2.  
3. returns: 0 if OK, -1 if not 
4.  
5. app1: 
6.  
7.     n = size of list 
8.  
9.     call list_resize() to resize the list to size n+1 = 0 + 1 = 1 
10.  
11.     list[n] = list[0] = new element 
12.  
13.     return 0  

下面是 list_resize() 函数。它会多申请一些内存，避免频繁调用 list_resize() 函数。列表的增长模式为：0，4，8，16，25，35，46，58，72，88……

1. arguments: list object, new size 
2.  
3. returns: 0 if OK, -1 if not 
4.  
5. list_resize: 
6.  
7.     new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) = 3 
8.  
9.     new_allocated += newsize = 3 + 1 = 4 
10.  
11.     resize ob_item (list of pointers) to size new_allocated 
12.  
13.     return 0  

现在分配了 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() 函数。

1. arguments: list object, where, new element 
2.  
3. returns: 0 if OK, -1 if not 
4.  
5. ins1: 
6.  
7.     resize list to size n+1 = 5 -> 4 more slots will be allocated 
8.  
9.     starting at the last element up to the offset where, right shift each element 
10.  
11.     set new element at offset where 
12.  
13.     return 0  

虚线的方框依旧表示已经分配但没有使用的槽空间。现在分配了 8 个槽空间，但是列表的大小却只是 5。

列表插入操作的平均复杂度为 O(n)。

Pop 操作

取出列表最后一个元素 即l.pop()，调用了 listpop() 函数。在 listpop() 函数中会调用 list_resize 函数，如果取出元素后列表的大小小于分配的槽空间数的一半，将会缩减列表的大小。

1. arguments: list object 
2.  
3. returns: element popped 
4.  
5. listpop: 
6.  
7.     if list empty: 
8.  
9.         return null 
10.  
11.     resize list with size 5 - 1 = 4. 4 is not less than 8/2 so no shrinkage 
12.  
13.     set list object size to 4 
14.  
15.     return last element  

列表 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() 函数。

1. arguments: list object, element to remove 
2.  
3. returns none if OK, null if not 
4.  
5. listremove: 
6.  
7.     loop through each list element: 
8.  
9.         if correct element: 
10.  
11.             slice list between element's slot and element's slot + 1 
12.  
13.             return none 
14.  
15.     return null  

为了做列表的切片并且删除元素，调用了 list_ass_slice() 函数，它的实现方法比较有趣。我们在删除列表位置 1 的元素 5 的时候，低位的偏移量为 1 同时高位的偏移量为 2.

1. arguments: list object, low offset, high offset 
2.  
3. returns: 0 if OK 
4.  
5. list_ass_slice: 
6.  
7.     copy integer 5 to recycle list to dereference it 
8.  
9.     shift elements from slot 2 to slot 1 
10.  
11.     resize list to 5 slots 
12.  
13.     return 0  

列表 remove 操作的复杂度为 O(n)。

作者：佚名

来源：51CTO