Python內(nèi)建類型list源碼學(xué)習(xí)

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

問(wèn)題：

深入認(rèn)識(shí)Python內(nèi)建類型這部分的內(nèi)容會(huì)從源碼角度為大家介紹Python中各種常用的內(nèi)建類型。

list是日常開(kāi)發(fā)中最常用的內(nèi)建類型之一，掌握好它的底層知識(shí)，無(wú)論是對(duì)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)的理解，還是對(duì)開(kāi)發(fā)效率的提升，應(yīng)該都是有一定幫助的

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

1常用方法

大家對(duì)于list應(yīng)該是比較熟悉的，我們先列舉一些常用的方法：

append：向尾部追加元素

l=[1,2,3]

l.append(4)

[1,2,3,4]

pop：彈出元素（默認(rèn)從尾部彈出元素，也可以通過(guò)index參數(shù)從指定位置彈出）

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)位置的下標(biāo)

l=[1,2,3,4]

l.index(1)

extend：用一個(gè)可迭代對(duì)象擴(kuò)展列表元素逐一追加到尾部

l=[1,2,3]

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

[1,2,3,1,3]

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

l=[1,2,3,1]

l.count(1)

l.count(2)

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

l=[1,2,3]

l.reverse()

[3,2,1]

clear：將列表清空

l=[1,2,3]

l.clear()

小結(jié)：

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

題外話：

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

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

不知不覺(jué)就寫了這么多，相比上次寫str相關(guān)的內(nèi)容還是要順暢多了（捂臉）。相關(guān)的小知識(shí)應(yīng)該是還有很多的，大家可以在學(xué)習(xí)的過(guò)程中多找一些問(wèn)題和資料來(lái)融會(huì)貫通，當(dāng)然我個(gè)人認(rèn)為如果能把底層的邏輯搞清楚，其他的應(yīng)該都不成問(wèn)題~

2list的內(nèi)部結(jié)構(gòu)：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：二維指針，指向動(dòng)態(tài)數(shù)組的指針，數(shù)組保存元素對(duì)象指針allocated：動(dòng)態(tài)數(shù)組總長(zhǎng)度，即列表當(dāng)前的容量ob_size：當(dāng)前元素個(gè)數(shù)，即列表當(dāng)前的長(zhǎng)度

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

3尾部操作和頭部操作

認(rèn)識(shí)了list的底層結(jié)構(gòu)之后，這里在強(qiáng)調(diào)一下尾部操作和頭部操作的一些問(wèn)題，鞏固一下數(shù)組相關(guān)的數(shù)據(jù)結(jié)構(gòu)知識(shí)，也順便引出一些動(dòng)態(tài)數(shù)組的相關(guān)內(nèi)容。

3.1尾部操作

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

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

個(gè)人想法：這里引出這個(gè)問(wèn)題是因?yàn)槲覀€(gè)人當(dāng)時(shí)在學(xué)習(xí)到這個(gè)知識(shí)點(diǎn)時(shí)，意識(shí)到了一個(gè)問(wèn)題：怎么擴(kuò)容。如果沒(méi)記錯(cuò)的話Java面試題中也會(huì)經(jīng)常聞到動(dòng)態(tài)擴(kuò)容。這里拋開(kāi)面試不談，我的想法主要是在怎么去避免頻繁擴(kuò)容，畢竟擴(kuò)容一次就需要拷貝所有的元素。這在日常開(kāi)發(fā)中應(yīng)該也是一個(gè)需要大家關(guān)注的問(wèn)題：像這種類似的消耗突增的操作，我們需要去避免，降低它的觸發(fā)頻率，但同時(shí)也不能忽視時(shí)空上的消耗。

3.2頭部操作

與尾部相比，由于在列表頭部增刪元素需要挪動(dòng)其他元素，性能差別就很大了（數(shù)組的基礎(chǔ)知識(shí)）

這里既然提到了頭部操作，我們來(lái)看一下Python中的隊(duì)列：

通過(guò)list實(shí)現(xiàn)棧是很好的，但是用來(lái)實(shí)現(xiàn)隊(duì)列是很不合理的：（LeetCode上的用棧實(shí)現(xiàn)隊(duì)列除外，hh）

q=[]

q.append(1)

q.append(2)

q.append(3)

#deque

q.pop(0)

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

如果需要頻繁進(jìn)行頭部操作，可以使用標(biāo)準(zhǔn)庫(kù)中的deque，這是一種雙端隊(duì)列結(jié)構(gòu)：

fromcollectionsimportdeque

q=deque()

#enqueue

q.append(job)

#deque

q.popleft()

4淺拷貝和深拷貝

淺拷貝和深拷貝應(yīng)該是容器相關(guān)的一個(gè)比較重要的知識(shí)點(diǎn)了，無(wú)論是Python還是Java中都會(huì)涉及，面試中應(yīng)該也比較常見(jiàn)。（其實(shí)可以單獨(dú)寫一篇博客來(lái)介紹這部分內(nèi)容，這里就先放在了list中來(lái)介紹，后續(xù)會(huì)考慮重新總結(jié)歸納出一篇博客）

4.1淺拷貝

調(diào)用list對(duì)象的copy方法，可以將列表拷貝一份，生成一個(gè)新的列表，但是不會(huì)拷貝列表中的元素。結(jié)合源碼來(lái)說(shuō)就是：會(huì)拷貝一下底層數(shù)組中指向具體元素對(duì)象的指針，但是元素對(duì)象不會(huì)被拷貝。

下面通過(guò)對(duì)淺拷貝后的列表進(jìn)行修改來(lái)實(shí)際體會(huì)一下：

示例1：

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

[1,[1,2,3]]

#淺拷貝

l2=l1.copy()

[1,[1,2,3]]

#修改新列表中的可變?cè)?/p>

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]]

#修改新列表中的不可變?cè)?/p>

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]]

#這里要注意并沒(méi)有修改可變?cè)豙1,2,3]，而是將l2[1]處的指針修改了，指向了一個(gè)新對(duì)象[3,4]

l2[1]=[3,4]

[2,[3,4]]

[1,[1,2,3]]

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

4.2深拷貝

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

下面通過(guò)對(duì)深拷貝后的列表進(jìn)行修改來(lái)實(shí)際體會(huì)一下：

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直接賦值

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

4.4小結(jié)

直接賦值：b=a

淺拷貝：b=a.copy()

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

個(gè)人總結(jié)：

弄清楚list底層數(shù)組中存儲(chǔ)的是指向?qū)?yīng)元素的指針，以及深拷貝時(shí)的遞歸，我覺(jué)得就能對(duì)相關(guān)的知識(shí)點(diǎn)有一個(gè)比較清晰的認(rèn)識(shí)了。但是對(duì)于Python中的元組需要特殊考慮，它是一個(gè)不可變的容器，當(dāng)元組中含有可變數(shù)據(jù)類型的容器和不含時(shí)，深拷貝的情況是有區(qū)別的。

本質(zhì)上元組是不會(huì)去創(chuàng)建新對(duì)象的，因?yàn)樗豢勺儯ㄟ@里我沒(méi)有找到百分百的證據(jù)，主要是根據(jù)經(jīng)驗(yàn)和查到的資料，大家可以去看一下源碼），但是當(dāng)元組中還有可變數(shù)據(jù)類型的容器，就又會(huì)由于深拷貝遞歸去拷貝相應(yīng)的對(duì)象而導(dǎo)致重新創(chuàng)建一個(gè)新的元組對(duì)象。

這里可能比較繞，大家可以自行去打印看一下結(jié)果。但是我個(gè)人覺(jué)得核心就是弄清楚list底層數(shù)組中存儲(chǔ)的是指向?qū)?yīng)元素的指針，以及深拷貝時(shí)的遞歸。

TODO：

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

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

5動(dòng)態(tài)數(shù)組

這一部分的內(nèi)容也是這篇博客最主要的重點(diǎn)：分析list底層數(shù)組的特性。前面我們已經(jīng)介紹了list的常用操作、底層結(jié)構(gòu)，以及以list為例簡(jiǎn)單介紹了深淺拷貝。這一小節(jié)會(huì)結(jié)合源碼詳細(xì)介紹list底層動(dòng)態(tài)數(shù)組的特性，我個(gè)人覺(jué)得這一設(shè)計(jì)也傳達(dá)了我們?cè)跇I(yè)務(wù)開(kāi)發(fā)上的一個(gè)比較常用和關(guān)鍵的思想。

5.1容量調(diào)整

前面已經(jīng)提到，當(dāng)我們調(diào)用append()、pop()、insert()等方法時(shí)，列表長(zhǎng)度會(huì)發(fā)生變化。當(dāng)列表長(zhǎng)度超過(guò)底層數(shù)組容量時(shí)，便需要對(duì)底層數(shù)組進(jìn)行擴(kuò)容；當(dāng)列表長(zhǎng)度低于底層數(shù)組容量并且達(dá)到某個(gè)值時(shí)，便需要對(duì)底層數(shù)組進(jìn)行縮容。

append()等方法是依賴list_resize()函數(shù)來(lái)調(diào)整列表長(zhǎng)度的。源碼如下：

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;

源碼分析：

重要參數(shù)：

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

重要步驟：

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

擴(kuò)容條件：新長(zhǎng)度大于底層數(shù)組容量縮容條件：新長(zhǎng)度小于底層數(shù)組容量的一半

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

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

第33~34行：如果新長(zhǎng)度為0，則新容量也為0，此時(shí)底層數(shù)組為空

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

第41~44行：依次設(shè)置新底層數(shù)組、新長(zhǎng)度、新容量

注：

在擴(kuò)容時(shí)先增加1/8，再增加3或6，是為了有效限制擴(kuò)容頻率，避免list對(duì)象長(zhǎng)度較小時(shí)會(huì)頻繁擴(kuò)容（我個(gè)人在工作中沒(méi)有遇到需要考慮類似問(wèn)題的需求，都是在寫業(yè)務(wù)代碼（捂臉），但是我認(rèn)為這種思想還是值得學(xué)習(xí)的）

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

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

新申請(qǐng)一塊大小為new_size的內(nèi)存區(qū)域?qū)?shù)據(jù)從舊內(nèi)存區(qū)域ptr拷貝到新內(nèi)存區(qū)域釋放舊內(nèi)存區(qū)域ptr返回新內(nèi)存區(qū)域

圖示如下：

5.2append()

append()方法在Python內(nèi)部由C函數(shù)list_append()實(shí)現(xiàn)，而list_append()進(jìn)一步調(diào)用app1()函數(shù)完成元素追加

app1()函數(shù)源碼如下：

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行：調(diào)用PyList_GET_SIZE()獲取列表當(dāng)前長(zhǎng)度，即ob_size

第7~11行：如果列表當(dāng)前長(zhǎng)度達(dá)到了最大值PY_SSIZE_T_MAX，則報(bào)錯(cuò)

第13~14行：調(diào)用list_resize()，必要時(shí)進(jìn)行擴(kuò)容

第16行：增加元素對(duì)象引用計(jì)數(shù)（這里是列表引用了該元素對(duì)象）

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

5.3insert()

insert()方法在Python內(nèi)部由C函數(shù)list_insert_impl()實(shí)現(xiàn)，而list_insert_impl()進(jìn)一步調(diào)用ins1()函數(shù)完成元素插入

ins1()函數(shù)源碼如下：

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行：檢查插入位置下標(biāo)，如果下標(biāo)為負(fù)數(shù)，則加上n將其轉(zhuǎn)化為非負(fù)數(shù)。如果轉(zhuǎn)化后的where值仍然小于0，則代表越界，但是這里會(huì)直接將where設(shè)置為0（即插入到列表頭部），而沒(méi)有報(bào)錯(cuò)。若下標(biāo)為正數(shù)，也會(huì)判斷是否越界，越界時(shí)則插入到列表尾部，同樣不會(huì)報(bào)錯(cuò)。

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

5.4pop()

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

pop()方法在Python內(nèi)部由list_pop_impl()函數(shù)實(shí)現(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行：如果給定下標(biāo)為負(fù)數(shù)，則加上列表長(zhǎng)度，轉(zhuǎn)化為普通下標(biāo)

第14~16行：檢查下標(biāo)是否合法，如果越界則報(bào)錯(cuò)

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

第26~31行：其他情況下調(diào)用list_ass_slice()刪除元素，調(diào)用前需要通過(guò)Py_INCREF增加元素的引用計(jì)數(shù)，因?yàn)樵趌ist_ass_slice()函數(shù)內(nèi)部會(huì)釋放被刪除元素

5.5remove()

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

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

staticPyObject*

list_remove(PyListObject*self,PyObject*value)

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

Py_ssize_ti;

for