一、特點(diǎn)

（1）相對(duì)于 tuple 來說，list 是動(dòng)態(tài)的（mutable），即：各個(gè)元素都是可變的。

（2）可以通過索引進(jìn)行查詢。

（3）list 中的元素可以是 python 中的任何對(duì)象。例如：list、tuple、dict、set、字符串和整數(shù)，并且可以任意混合。

（4）所有元素由一個(gè)中括號(hào)“[ ]”包裹。

二、相關(guān)操作

1、增

? ? ? ? a、append() ，在 list 尾部插入元素。

? ? ? ? b、insert()，在 list 的指定位置插入元素。

2、刪

? ? ? ? a、pop()，彈出 list 尾部元素并返回，與 append 對(duì)應(yīng)。

? ? ? ? b、remove()，刪除指定元素。

? ? ? ? c、del ，刪除指定的位置的元素。

3、改

? ? ? ? 直接用“=”修改指定元素即可。

4、查

? ? ? ? 類似于數(shù)組的索引。

栗子：

if __name__ == '__main__':testlist = ['one', 'two', 'six']# 增# append 在 list 末尾添加元素。testlist.append('three')# insert 在指定的位置插入元素。testlist.insert(1, 'four')# 刪# pop 刪除 list 尾部元素。t = testlist.pop()# remove 刪除 list 中的元素。testlist.remove('two')# del 刪除 list 中指定范圍的元素。del testlist[0:2]# 改testlist[0] = 'hello world!'

三、實(shí)現(xiàn)原理

1、底層的實(shí)現(xiàn)方式是 PyObject 類型的二維指針數(shù)組 。在 python 世界中，一切都是對(duì)象，無論是 int 、string 還是 list 等，這些都繼承于 PyObject ，所以 list 保存的是各個(gè) PyObject 的指針，傳指針相對(duì)于傳對(duì)象效率更高。

2、空 list 的大小是 40B，即：一個(gè)描述 list 的結(jié)構(gòu)體的大小。該結(jié)構(gòu)體如下所示：

typedef struct {PyObject_VAR_HEAD // 用來保存已使用的內(nèi)存槽的數(shù)量。PyObject **ob_item; // 用來保存對(duì)象的指針的指針數(shù)組。Py_ssize_t allocated; // 預(yù)先分配的內(nèi)存槽的總?cè)萘?#xff0c;即：ob_item 數(shù)組的容量。 } PyListObject;

3、當(dāng)一個(gè)空的 list 執(zhí)行 append 時(shí)，list 實(shí)際上會(huì)多分配一些內(nèi)存，這樣可以提高下次 append 的高效性，即：時(shí)間復(fù)雜度為 O(1)。分配內(nèi)存的算法如下：

new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

?總體效果是隨著對(duì)象的數(shù)量增多，單次分配的內(nèi)存槽逐漸變大。

4、append() 源碼實(shí)現(xiàn)

（1）過程簡述

• 判斷是否需要重新對(duì) list 的內(nèi)存槽數(shù)組（ob_item）進(jìn)行重新分配。若需要，則申請(qǐng)新的內(nèi)存槽數(shù)組、將舊內(nèi)存槽數(shù)組中的數(shù)據(jù)拷貝到新的內(nèi)存槽數(shù)組中，釋放舊的內(nèi)存槽數(shù)組。
• 將新對(duì)象的指針加入到 ob_item 的尾部。

（2）append() 函數(shù)實(shí)際上調(diào)用的是 app1() 函數(shù)。

/*** 向 list 的尾部添加對(duì)象。 */ static PyObject *list_append(PyListObject *self, PyObject *object) {if (app1(self, object) == 0)Py_RETURN_NONE;return NULL; }

（3）app1 函數(shù)的執(zhí)行過程如下：

static int app1(PyListObject *self, PyObject *v) {/*** 返回當(dāng)前 list 中對(duì)象的數(shù)量。*/Py_ssize_t n = PyList_GET_SIZE(self);assert(v != NULL);if (n == PY_SSIZE_T_MAX){PyErr_SetString(PyExc_OverflowError,"cannot add more objects to list");return -1;}/*** 重新調(diào)整 list 的內(nèi)存。* 創(chuàng)建新的內(nèi)存槽數(shù)組、釋放舊的內(nèi)存槽數(shù)組。*/if (list_resize(self, n + 1) < 0)return -1;/*** 對(duì)象 v 的引用計(jì)數(shù) + 1 。*/Py_INCREF(v);/*** 將對(duì)象指針插入到 list 的 ob_item 指針數(shù)據(jù)中。*/PyList_SET_ITEM(self, n, v);return 0; }

（4）精髓就在 list_resize() 函數(shù)中了，該函數(shù)完成了內(nèi)存的重新分配。

static int list_resize(PyListObject *self, Py_ssize_t newsize) {PyObject **items;size_t new_allocated, num_allocated_bytes;Py_ssize_t allocated = self->allocated;/* Bypass realloc() when a previous overallocation is large enoughto accommodate the newsize. If the newsize falls lower than halfthe allocated size, then proceed with the realloc() to shrink the list.*//*** （1）若 newsize < 已分配的內(nèi)存槽的數(shù)量的 1/2，則重新分配內(nèi)存槽數(shù)組（縮容）。* （2）若 newsize >= 已分配的內(nèi)存槽的數(shù)量的 1/2，且 newsize =< 已分配的內(nèi)存槽的數(shù)量，則無需調(diào)整。* （3）若 newsize > 已分配的內(nèi)存槽的數(shù)量，則重新分配內(nèi)存槽數(shù)組（擴(kuò)容）。* （注意，新的 list 和舊的 list 不在同一個(gè)內(nèi)存起始地址。）*/if (allocated >= newsize && newsize >= (allocated >> 1)){assert(self->ob_item != NULL || newsize == 0);Py_SIZE(self) = newsize;return 0;}/* This over-allocates proportional to the list size, making room* for additional growth. The over-allocation is mild, but is* enough to give linear-time amortized behavior over a long* sequence of appends() in the presence of a poorly-performing* system realloc().* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...* Note: new_allocated won't overflow because the largest possible value* is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.*//*** 內(nèi)存分配方案，獲取新的內(nèi)存槽的數(shù)量。*/new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)){PyErr_NoMemory();return -1;}if (newsize == 0)new_allocated = 0;/*** 新的內(nèi)存槽數(shù)組的字節(jié)總數(shù)。*/num_allocated_bytes = new_allocated * sizeof(PyObject *);/*** （1）創(chuàng)建新的內(nèi)存槽數(shù)組；* （2）將舊內(nèi)存槽數(shù)組中的數(shù)據(jù)拷貝到新的內(nèi)存槽數(shù)組中；* （3）釋放舊的內(nèi)存槽數(shù)組。* obmalloc.c PyMem_realloc() 函數(shù)。*/items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);if (items == NULL){PyErr_NoMemory();return -1;}/*** 將新的狀態(tài)更新到 list 對(duì)象中。*/self->ob_item = items;Py_SIZE(self) = newsize;self->allocated = new_allocated;return 0; }

5、insert() 源碼實(shí)現(xiàn)

（1）過程簡述

• 判斷是否需要重新對(duì) list 的內(nèi)存槽數(shù)組（ob_item）進(jìn)行重新分配。若需要，則申請(qǐng)新的內(nèi)存槽數(shù)組、將舊內(nèi)存槽數(shù)組中的數(shù)據(jù)拷貝到新的內(nèi)存槽數(shù)組中，釋放舊的內(nèi)存槽數(shù)組。
• 將 where 之后的元素全部向后挪一位。
• 將 new item 放到 where 的位置上。

（2）append() 函數(shù)實(shí)際上調(diào)用的是 ins1() 函數(shù)。

int PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem) {if (!PyList_Check(op)){PyErr_BadInternalCall();return -1;}return ins1((PyListObject *)op, where, newitem); }

（3）ins1() 源碼

static int ins1(PyListObject *self, Py_ssize_t where, PyObject *v) {/*** 返回當(dāng)前已用的內(nèi)存槽的數(shù)量，即：list 中已有的元素的數(shù)量。*/Py_ssize_t i, n = Py_SIZE(self);PyObject **items;if (v == NULL){PyErr_BadInternalCall();return -1;}if (n == PY_SSIZE_T_MAX){PyErr_SetString(PyExc_OverflowError,"cannot add more objects to list");return -1;}/*** 調(diào)整內(nèi)存槽數(shù)組。*/if (list_resize(self, n + 1) < 0)return -1;if (where < 0){where += n;if (where < 0)where = 0;}if (where > n)where = n;items = self->ob_item;/*** 將 where 之后的數(shù)據(jù)向后挪一位。*/for (i = n; --i >= where;)items[i + 1] = items[i];Py_INCREF(v);items[where] = v;return 0; }

四、拓展

下面是兩種創(chuàng)建空 list 的方法，哪一個(gè)效率更高呢？

empty_list = [] empty_list = list()

答案是前者效率更高，因?yàn)榍罢呤莾?nèi)置的C函數(shù)，可以直接調(diào)用；后者是 python 的函數(shù)調(diào)用，會(huì)創(chuàng)建 stack 和參數(shù)檢查，比較浪費(fèi)時(shí)間。

?

（SAW：Game Over！）

總結(jié)

以上是生活随笔為你收集整理的python 3.8.2 / 内置的数据结构 / list （类似于 STL 中的 vector）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。