Python內建類型list源碼學習

第Python內建類型list源碼學習目錄問題：1常用方法小結：題外話：2list的內部結構：PyListObject3尾部操作和頭部操作3.1尾部操作3.2頭部操作4淺拷貝和深拷貝4.1淺拷貝4.2深拷貝4.3直接賦值4.4小結個人總結：TODO：5動態(tài)數組5.1容量調整5.2append()5.3insert()5.4pop()5.5remove()6一些問題

問題：

深入認識Python內建類型這部分的內容會從源碼角度為大家介紹Python中各種常用的內建類型。

list是日常開發(fā)中最常用的內建類型之一，掌握好它的底層知識，無論是對數據結構基礎知識的理解，還是對開發(fā)效率的提升，應該都是有一定幫助的

list對象支持哪些操作？時間復雜度、空間復雜度分別是多少？試分析append和insert這兩個典型方法的時間復雜度。頭部添加元素時性能較差，如何解決？

1常用方法

大家對于list應該是比較熟悉的，我們先列舉一些常用的方法：

append：向尾部追加元素

l=[1,2,3]

l.append(4)

[1,2,3,4]

pop：彈出元素（默認從尾部彈出元素，也可以通過index參數從指定位置彈出）

l=[1,2,3,4]

l.pop()

[1,2,3]

l=[1,2,3,4]

l.pop(0)#指定index

[2,3,4]

insert：在指定位置插入元素

l=[1,2,3]

l.insert(0,4)

[4,1,2,3]

index：查找指定元素第一次出現(xiàn)位置的下標

l=[1,2,3,4]

l.index(1)

extend：用一個可迭代對象擴展列表元素逐一追加到尾部

l=[1,2,3]

l.extend({1:2,3:4})

[1,2,3,1,3]

count：計算元素出現(xiàn)的次數

l=[1,2,3,1]

l.count(1)

l.count(2)

reverse：將列表反轉（注意這里是直接在原列表上進行操作，可以和切片區(qū)分下）

l=[1,2,3]

l.reverse()

[3,2,1]

clear：將列表清空

l=[1,2,3]

l.clear()

小結：

list的操作總體比較簡單，但是要注意的是：由于list底層是由數組實現(xiàn)的，對應的各類插入和刪除操作就會由于數組的特型而在復雜度上有所差別，例如：通過insert()在頭部插入元素時，需要挪動整個列表，此時時間復雜度為O(n)，而append()直接在尾部插入元素時，時間復雜度為O(1)。在使用時要注意時空復雜度問題（后續(xù)我會結合源碼詳細介紹）。

題外話：

list的操作有很多，后續(xù)我會對典型操作進行源碼分析，還有很多操作可能就需要大家自行去學習了解了，但是本質上都是大同小異的，掌握好數組以及Python對此在源碼處理上的一些技巧就能熟練掌握了。這里我結合自己的學習、工作、面試經歷，總結了一點問題和心得：

list為什么可以使用負數索引從源碼角度看是因為判斷了索引輸入為負數的情況，會做一個相應的處理：索引值+列表長度。例如：索引為-1，列表長度為3，最終的索引就是2，也就是最后一個元素的索引。對比一下Java中的數組，如果使用負數索引，會報錯索引越界，在網上查能否有相關方法實現(xiàn)負數索引：有人說用一個類來包裝，也有的說用一個字典去映射負數和正確的索引，也有的直接給出了無法做到的答案。相關的做法應該是有很多的，但同時也不要忽視了安全性等相關問題。這里提出這個點也是我自己覺得比較有趣的一個地方吧，索引值+列表長度其實是一個很簡單的做法，但總感覺又有那么一點一般人想不出來的巧妙，hh以pop()和insert()為例，這兩個方法有一個共同的參數：索引。對于pop()，如果索引值大于等于列表長度，則會報錯；而對于insert()，如果索引值大于等于列表長度則統(tǒng)一將元素插入到列表最后。從源碼角度看其實就是insert()對于索引參數做了一個判斷處理，當它大于列表長度時，會將索引值更改為列表長度，例如：index=5，而list=[1,2,3]，源碼處理時，會將index置為3。所以如果開發(fā)者樂意的話，應該可以對pop()也采用相同的操作，我個人認為這里應該是有其他的考慮的，例如安全性等問題，當然也有可能只是寫成了這樣而已，hhreverse()，reversed()，切片的區(qū)別。個人認為本質上這三者其實沒啥關系，大家如果容易弄混可能還是因為不夠熟練。重點問題可能在切片以及深拷貝、淺拷貝的問題上，后續(xù)我會詳細介紹相關內容。append()和extend()的區(qū)別。面試題好像會問這個，也是很基礎的知識了。如果換個角度問可能會更有趣些：l.append(3)和l.extend(3)的效果是不是一樣的？答：不一樣，后者會直接報錯，hh

不知不覺就寫了這么多，相比上次寫str相關的內容還是要順暢多了（捂臉）。相關的小知識應該是還有很多的，大家可以在學習的過程中多找一些問題和資料來融會貫通，當然我個人認為如果能把底層的邏輯搞清楚，其他的應該都不成問題~

2list的內部結構：PyListObject

源碼如下：

typedefstruct{

PyObject_VAR_HEAD

/*Vectorofpointerstolistelements.list[0]isob_item[0],etc.*/

PyObject**ob_item;

/*ob_itemcontainsspacefor'allocated'elements.Thenumber

*currentlyinuseisob_size.

*Invariants:

*0=ob_size=allocated

*len(list)==ob_size

*ob_item==NULLimpliesob_size==allocated==0

*list.sort()temporarilysetsallocatedto-1todetectmutations.

*ItemsmustnormallynotbeNULL,exceptduringconstructionwhen

*thelistisnotyetvisibleoutsidethefunctionthatbuildsit.

Py_ssize_tallocated;

}PyListObject;

源碼分析：

ob_item：二維指針，指向動態(tài)數組的指針，數組保存元素對象指針allocated：動態(tài)數組總長度，即列表當前的容量ob_size：當前元素個數，即列表當前的長度

這里出現(xiàn)了一些新的概念：動態(tài)數組，容量。后續(xù)我會對此進行介紹，這里大家對照示意圖應該就能有比較初步的認識了：

3尾部操作和頭部操作

認識了list的底層結構之后，這里在強調一下尾部操作和頭部操作的一些問題，鞏固一下數組相關的數據結構知識，也順便引出一些動態(tài)數組的相關內容。

3.1尾部操作

假設列表對象l內部數組長度為5，當前保存了2個元素，分別是1，2。當我們調用append()方法向尾部追加元素時，由于內部數組還未用滿，只需將新元素保存于下一個可用位置，并更新ob_size字段。因此，絕大多數情況下，append()方法的性能都足夠好，時間復雜度為O(1)。

若list對象內部數組已滿，則再添加元素時就需要進行擴容。append()等方法在操作時都會對內部數組進行檢查，如需擴容，則會重新分配一個長度更大的數組并替換舊數組。因此，當使用append()方法遇到擴容時，會將列表元素從舊數組拷貝到新數組，此時時間復雜度為O(n)。

個人想法：這里引出這個問題是因為我個人當時在學習到這個知識點時，意識到了一個問題：怎么擴容。如果沒記錯的話Java面試題中也會經常聞到動態(tài)擴容。這里拋開面試不談，我的想法主要是在怎么去避免頻繁擴容，畢竟擴容一次就需要拷貝所有的元素。這在日常開發(fā)中應該也是一個需要大家關注的問題：像這種類似的消耗突增的操作，我們需要去避免，降低它的觸發(fā)頻率，但同時也不能忽視時空上的消耗。

3.2頭部操作

與尾部相比，由于在列表頭部增刪元素需要挪動其他元素，性能差別就很大了（數組的基礎知識）

這里既然提到了頭部操作，我們來看一下Python中的隊列：

通過list實現(xiàn)棧是很好的，但是用來實現(xiàn)隊列是很不合理的：（LeetCode上的用棧實現(xiàn)隊列除外，hh）

q=[]

q.append(1)

q.append(2)

q.append(3)

#deque

q.pop(0)

這樣的隊列實現(xiàn)，在出隊操作時會移動所有隊列元素（除pop掉的元素以外），性能很差

如果需要頻繁進行頭部操作，可以使用標準庫中的deque，這是一種雙端隊列結構：

fromcollectionsimportdeque

q=deque()

#enqueue

q.append(job)

#deque

q.popleft()

4淺拷貝和深拷貝

淺拷貝和深拷貝應該是容器相關的一個比較重要的知識點了，無論是Python還是Java中都會涉及，面試中應該也比較常見。（其實可以單獨寫一篇博客來介紹這部分內容，這里就先放在了list中來介紹，后續(xù)會考慮重新總結歸納出一篇博客）

4.1淺拷貝

調用list對象的copy方法，可以將列表拷貝一份，生成一個新的列表，但是不會拷貝列表中的元素。結合源碼來說就是：會拷貝一下底層數組中指向具體元素對象的指針，但是元素對象不會被拷貝。

下面通過對淺拷貝后的列表進行修改來實際體會一下：

示例1：

l1=[1,[1,2,3]]

[1,[1,2,3]]

#淺拷貝

l2=l1.copy()

[1,[1,2,3]]

#修改新列表中的可變元素

l2[1][0]=6

[1,[6,2,3]]

[1,[6,2,3]]

示例2：

l1=[1,[1,2,3]]

[1,[1,2,3]]

#淺拷貝

l2=l1.copy()

[1,[1,2,3]]

#修改新列表中的不可變元素

l2[0]=2

[2,[1,2,3]]

[1,[1,2,3]]

示例3：

l1=[1,[1,2,3]]

[1,[1,2,3]]

#淺拷貝

l2=l1.copy()

[1,[1,2,3]]

#這里要注意并沒有修改可變元素[1,2,3]，而是將l2[1]處的指針修改了，指向了一個新對象[3,4]

l2[1]=[3,4]

[2,[3,4]]

[1,[1,2,3]]

list對象的底層數組保存的是元素對象的指針，copy()方法復制底層數組時，拷貝的也是元素對象的指針，而不會拷貝具體的元素對象。因此，新舊列表對象的數組中的指針指向的還是相同的對象。圖示如下：

4.2深拷貝

通過copy模塊中的deepcopy()函數可以進行深拷貝，deepcopy()函數會遞歸復制所有容器對象，確保新舊列表不會包含同一個容器對象（這里要注意元組是比較特殊的，稍微會說明）

下面通過對深拷貝后的列表進行修改來實際體會一下：

fromcopyimportdeepcopy

l1=[1,[1,2,3]]

[1,[1,2,3]]

#深拷貝

l2=deepcopy(l1)

[1,[1,2,3]]

l2[1][0]=5

[1,[5,2,3]]

[1,[1,2,3]]

l2[0]=2

[2,[5,2,3]]

[1,[1,2,3]]

圖示如下：

4.3直接賦值

除了深拷貝、淺拷貝外，最常見的操作就是直接賦值，即對象的引用（別名），這里就不涉及到復制操作了。

4.4小結

直接賦值：b=a

淺拷貝：b=a.copy()

深拷貝：b=copy.deepcopy(a)

個人總結：

弄清楚list底層數組中存儲的是指向對應元素的指針，以及深拷貝時的遞歸，我覺得就能對相關的知識點有一個比較清晰的認識了。但是對于Python中的元組需要特殊考慮，它是一個不可變的容器，當元組中含有可變數據類型的容器和不含時，深拷貝的情況是有區(qū)別的。

本質上元組是不會去創(chuàng)建新對象的，因為它不可變（這里我沒有找到百分百的證據，主要是根據經驗和查到的資料，大家可以去看一下源碼），但是當元組中還有可變數據類型的容器，就又會由于深拷貝遞歸去拷貝相應的對象而導致重新創(chuàng)建一個新的元組對象。

這里可能比較繞，大家可以自行去打印看一下結果。但是我個人覺得核心就是弄清楚list底層數組中存儲的是指向對應元素的指針，以及深拷貝時的遞歸。

TODO：

后續(xù)我會重新寫一篇博客來專門將深淺拷貝的源碼列出來，來看看為什么對于元組就會特殊處理。

要是我們的列表元素是自定義的數據類型又是如何處理的。深拷貝遞歸復制時判斷的條件到底是如何寫的。

5動態(tài)數組

這一部分的內容也是這篇博客最主要的重點：分析list底層數組的特性。前面我們已經介紹了list的常用操作、底層結構，以及以list為例簡單介紹了深淺拷貝。這一小節(jié)會結合源碼詳細介紹list底層動態(tài)數組的特性，我個人覺得這一設計也傳達了我們在業(yè)務開發(fā)上的一個比較常用和關鍵的思想。

5.1容量調整

前面已經提到，當我們調用append()、pop()、insert()等方法時，列表長度會發(fā)生變化。當列表長度超過底層數組容量時，便需要對底層數組進行擴容；當列表長度低于底層數組容量并且達到某個值時，便需要對底層數組進行縮容。

append()等方法是依賴list_resize()函數來調整列表長度的。源碼如下：

staticint

list_resize(PyListObject*self,Py_ssize_tnewsize)

PyObject**items;

size_tnew_allocated,num_allocated_bytes;

Py_ssize_tallocated=self-allocated;

/*Bypassrealloc()whenapreviousoverallocationislargeenough

toaccommodatethenewsize.Ifthenewsizefallslowerthanhalf

theallocatedsize,thenproceedwiththerealloc()toshrinkthelist.

if(allocated=newsizenewsize=(allocated1)){

assert(self-ob_item!=NULL||newsize==0);

Py_SIZE(self)=newsize;

return0;

/*Thisover-allocatesproportionaltothelistsize,makingroom

*foradditionalgrowth.Theover-allocationismild,butis

*enoughtogivelinear-timeamortizedbehavioroveralong

*sequenceofappends()inthepresenceofapoorly-performing

*systemrealloc().

*Thegrowthpatternis:0,4,8,16,25,35,46,58,72,88,...

*Note:new_allocatedwon'toverflowbecausethelargestpossiblevalue

*isPY_SSIZE_T_MAX*(9/8)+6whichalwaysfitsinasize_t.

new_allocated=(size_t)newsize+(newsize3)+(newsize93:6);

if(new_allocated(size_t)PY_SSIZE_T_MAX/sizeof(PyObject*)){

PyErr_NoMemory();

return-1;

if(newsize==0)

new_allocated=0;

num_allocated_bytes=new_allocated*sizeof(PyObject*);

items=(PyObject**)PyMem_Realloc(self-ob_item,num_allocated_bytes);

if(items==NULL){

PyErr_NoMemory();

return-1;

self-ob_item=items;

Py_SIZE(self)=newsize;

self-allocated=new_allocated;

return0;

源碼分析：

重要參數：

items指針：用于保存新數組new_allocated：用于保存新數組容量num_allocated_bytes：用于保存新數組內存大小，單位為字節(jié)allocated：用于保存舊數組容量

重要步驟：

第12行：檢查新長度與底層數組容量的大小關系。如果新長度不超過現(xiàn)有數組容量，并且大于等于現(xiàn)有容量的一半，則不會更新數組容量，只修改ob_size即可。從這里我們可以得知list對象的擴縮容條件：

擴容條件：新長度大于底層數組容量縮容條件：新長度小于底層數組容量的一半

第27行：新容量=新長度+1/8*新長度+3或6（取決于新長度是否小于9）

第28~31行：如果新容量超過了允許的最大值，則返回錯誤

第33~34行：如果新長度為0，則新容量也為0，此時底層數組為空

第36~40行：調用PyMem_Realloc()函數重新分配底層數組

第41~44行：依次設置新底層數組、新長度、新容量

注：

在擴容時先增加1/8，再增加3或6，是為了有效限制擴容頻率，避免list對象長度較小時會頻繁擴容（我個人在工作中沒有遇到需要考慮類似問題的需求，都是在寫業(yè)務代碼（捂臉），但是我認為這種思想還是值得學習的）

PyMem_Realloc()函數是Python內部實現(xiàn)的內存管理函數之一，功能和C的庫函數realloc()類似。主要步驟如下：

PyAPI_FUNC(void*)PyMem_Realloc(void*ptr,size_tnew_size);

新申請一塊大小為new_size的內存區(qū)域將數據從舊內存區(qū)域ptr拷貝到新內存區(qū)域釋放舊內存區(qū)域ptr返回新內存區(qū)域

圖示如下：

5.2append()

append()方法在Python內部由C函數list_append()實現(xiàn)，而list_append()進一步調用app1()函數完成元素追加

app1()函數源碼如下：

staticint

app1(PyListObject*self,PyObject*v)

Py_ssize_tn=PyList_GET_SIZE(self);

assert(v!=NULL);

if(n==PY_SSIZE_T_MAX){

PyErr_SetString(PyExc_OverflowError,

"cannotaddmoreobjectstolist");

return-1;

if(list_resize(self,n+1)0)

return-1;

Py_INCREF(v);

PyList_SET_ITEM(self,n,v);

return0;

源碼分析：

第4行：調用PyList_GET_SIZE()獲取列表當前長度，即ob_size

第7~11行：如果列表當前長度達到了最大值PY_SSIZE_T_MAX，則報錯

第13~14行：調用list_resize()，必要時進行擴容

第16行：增加元素對象引用計數（這里是列表引用了該元素對象）

第17行：調用PyList_SET_ITEM()將元素對象指針保存在列表的最后一個位置

5.3insert()

insert()方法在Python內部由C函數list_insert_impl()實現(xiàn)，而list_insert_impl()進一步調用ins1()函數完成元素插入

ins1()函數源碼如下：

staticint

ins1(PyListObject*self,Py_ssize_twhere,PyObject*v)

Py_ssize_ti,n=Py_SIZE(self);

PyObject**items;

if(v==NULL){

PyErr_BadInternalCall();

return-1;

if(n==PY_SSIZE_T_MAX){

PyErr_SetString(PyExc_OverflowError,

"cannotaddmoreobjectstolist");

return-1;

if(list_resize(self,n+1)0)

return-1;

if(where0){

where+=n;

if(where0)

where=0;

if(wheren)

where=n;

items=self-ob_item;

for(i=n;--i=where;)

items[i+1]=items[i];

Py_INCREF(v);

items[where]=v;

return0;

源碼分析：

第19~25行：檢查插入位置下標，如果下標為負數，則加上n將其轉化為非負數。如果轉化后的where值仍然小于0，則代表越界，但是這里會直接將where設置為0（即插入到列表頭部），而沒有報錯。若下標為正數，也會判斷是否越界，越界時則插入到列表尾部，同樣不會報錯。

第26~28行：將插入位置以后的元素逐一往后移動一個位置。（這里的for循環(huán)是從后往前迭代的）

5.4pop()

pop()方法將指定下標的元素從列表中彈出，下標默認為-1，即默認彈出最后一個元素

pop()方法在Python內部由list_pop_impl()函數實現(xiàn)。源碼如下：

staticPyObject*

list_pop_impl(PyListObject*self,Py_ssize_tindex)

/*[clinicendgeneratedcode:output=6bd69dcb3f17eca8input=b83675976f329e6f]*/

PyObject*v;

intstatus;

if(Py_SIZE(self)==0){

/*Special-casemostcommonfailurecause*/

PyErr_SetString(PyExc_IndexError,"popfromemptylist");

returnNULL;

if(index0)

index+=Py_SIZE(self);

if(index0||index=Py_SIZE(self)){

PyErr_SetString(PyExc_IndexError,"popindexoutofrange");

returnNULL;

v=self-ob_item[index];

if(index==Py_SIZE(self)-1){

status=list_resize(self,Py_SIZE(self)-1);

if(status=0)

returnv;/*andvnowownsthereferencethelisthad*/

else

returnNULL;

Py_INCREF(v);

status=list_ass_slice(self,index,index+1,(PyObject*)NULL);

if(status0){

Py_DECREF(v);

returnNULL;

returnv;

源碼分析：

第12~13行：如果給定下標為負數，則加上列表長度，轉化為普通下標

第14~16行：檢查下標是否合法，如果越界則報錯

第19~25行：如果待彈出元素為列表的尾部元素，則調用list_resize()直接處理（比較巧妙，hh）

第26~31行：其他情況下調用list_ass_slice()刪除元素，調用前需要通過Py_INCREF增加元素的引用計數，因為在list_ass_slice()函數內部會釋放被刪除元素

5.5remove()

remove()方法將給定元素從列表中刪除，與pop()不同，remove()直接刪除給定元素，而不是通過下標進行索引

remove()方法在Python內部由C函數list_remove()實現(xiàn)。源碼如下：

staticPyObject*

list_remove(PyListObject*self,PyObject*value)

/*[clinicendgeneratedcode:output=f087e1951a5e30d1input=2dc2ba5bb2fb1f82]*/

Py_ssize_ti;

for