本文将介绍列表在CPython中的实现，因为毕竟CPython是最常用的Python实现。Python中的列表非常强大，了解它们在幕后如何工作将会很有趣。下面是一个python脚本，它将一些整数添加到列表中，然后打印列表。>>>l=[]>>>l.append(1)>>>l.append(2)>>>l.append(3)>>>l[1,2,3]>>>foreinl:...printe...123可以查到，list是一个迭代器。List对象的C语言结构Cpython中的list实现类似于下面的C结构。ob_item是指向列表对象的指针数组。allocated是申请内存的槽数。typedefstruct{PyObject_VAR_HEADPyObject**ob_item;Py_ssize_tallocated;}PyListObject;列表初始化查看当您初始化一个空列表时会发生什么，例如：l=[]。arguments:sizeofthelist=0returns:listobject=[]PyListNew:nbytes=size*sizeofglobalPythonobject=0allocatenewlistobjectallocatelistofpointers(ob_item)ofsizenbytes=0clearob_itemsetlist'sallocatedvarto0=0slotsreturnlistobject区分列表大小和分配的槽大小很重要。列表的大小与len(l)的大小相同。分配槽大小是指内存中已经分配的槽空间的数量。通常分配槽的大小大于列表的大小，这是为了避免每次向列表添加元素时调用内存分配函数。下面将详细介绍。Append操作向列表添加一个整数：l.append(1)时会发生什么？底层C函数app1()被调用。arguments:listobject,newelementreturns:0ifOK,-1ifnotapp1:n=sizeoflistcalllist_resize()toresizethelisttosizen+1=0+1=1list[n]=list[0]=newelementreturn0下面是list_resize()函数。它将申请更多内存以避免频繁调用list_resize()函数。列表的增长模式为：0,4,8,16,25,35,46,58,72,88...arguments:listobject,newsizereturns:0ifOK,-1ifnotlist_resize:new_allocated=(newsize>>3)+(newsize<9?3:6)=3new_allocated+=newsize=3+1=4resizeob_item(listofpointers)tosizenew_allocatedreturn0现在为list元素分配4个slot空间，第一个空间为整数1。下图显示l[0]指向我们新添加的整数对象。虚线框表示已分配但未使用的插槽空间。将元素附加到列表的平均复杂度为O(1)。继续添加新元素：l.append(2)。调用list_resize函数，参数为n+1=2，但是由于已经申请了4个slot空间，所以不需要申请内存空间。添加两个整数也是如此：l.append(3)、l.append(4)。下图显示了我们现在的位置。Insert操作在列表的偏移量1处插入一个新元素，整数5：l.insert(1,5)，内部调用ins1()函数。arguments:listobject,where,newelementreturns:0ifOK,-1ifnotins1:resizelisttosizen+1=5->4moreslotswillbeallocatedstartingatthelastelementuptotheoffsetwhere,rightshifteeachelementsetnewelementatoffsetwherereturn0虚线框仍然表示已分配但未使用的槽空间。现在分配了8个槽位，但是列表的大小只有5个。列表插入操作的平均复杂度是O(n)。Pop操作取出列表的最后一个元素，即l.pop()，调用listpop()函数。list_resize函数将在listpop()函数中调用。如果取出元素后列表的大小小于分配的槽空间的一半，则列表的大小将减少。arguments:listobjectreturns:elementpoppedlistpop:iflistempty:returnnullresizelistwithsize5-1=4.4isnotlessthan8/2sonoshrinkagesetlistobjectsizeto4returnlastelementlistpop操作的平均复杂度是O(1)。可以看出，pop操作之后，slot空间4仍然指向原来的整型对象，但最重要的是现在list的大小已经变成了4，继续pop一个元素。在list_resize()函数中，size–1=4–1=3已经小于分配slotsize的一半，所以分配slot空间减少为6，现在listsize为3。可以看到那个slot空格3和4仍然指向原来的整数，但是列表的大小现在变成了3。删除操作Python的列表对象有一个方法可以删除指定的元素：l.remove(5)。底层调用listremove()函数。arguments:listobject,elementtomovereturnsnoneifOK,nullifnotlistremove:loopthrougheachlistelement:ifcorrectelement:slicelistbetweenelement'slotandelement'sslot+1returnnoreturnnull为了对列表进行切片和删除元素，调用了list_ass_slice()函数，它的实现方法还是蛮有意思的。当我们删除列表位置1的元素5时，低偏移量为1，高偏移量为2。arguments:listobject,lowoffset,highoffsetreturns:0ifOKlist_ass_slice:copyinteger5torecyclelisttodereferenceitshiftelementsfromslot2toslot1resizelistto5slotsreturn0列表移除操作的复杂度为O(n)。
