一、python中的列表原理

列表是一個(gè)線性的集合，它允許用戶在任何位置插入、刪除、訪問和替換元素。
列表實(shí)現(xiàn)是基于數(shù)組或基于鏈表結(jié)構(gòu)的。當(dāng)使用列表迭代器的時(shí)候，雙鏈表結(jié)構(gòu)比單鏈表結(jié)構(gòu)更快。
有序的列表是元素總是按照升序或者降序排列的元素。

實(shí)現(xiàn)細(xì)節(jié)
python中的列表的英文名是list，因此很容易和其它語(yǔ)言(C++, Java等)標(biāo)準(zhǔn)庫(kù)中常見的鏈表混淆。事實(shí)上CPython的列表根本不是列表（可能換成英文理解起來(lái)容易些：python中的list不是list）。在CPython中，列表被實(shí)現(xiàn)為長(zhǎng)度可變的數(shù)組。

可參考《Python高級(jí)編程（第2版）》

從細(xì)節(jié)上看，Python中的列表是由對(duì)其它對(duì)象的引用組成的連續(xù)數(shù)組。指向這個(gè)數(shù)組的指針及其長(zhǎng)度被保存在一個(gè)列表頭結(jié)構(gòu)中。這意味著，每次添加或刪除一個(gè)元素時(shí)，由引用組成的數(shù)組需要該標(biāo)大小（重新分配）。幸運(yùn)的是，Python在創(chuàng)建這些數(shù)組時(shí)采用了指數(shù)分配，所以并不是每次操作都需要改變數(shù)組的大小。但是，也因?yàn)檫@個(gè)原因添加或取出元素的平攤復(fù)雜度較低。

不幸的是，在普通鏈表上“代價(jià)很小”的其它一些操作在Python中計(jì)算復(fù)雜度相對(duì)過高。

利用 list.insert(i,item) 方法在任意位置插入一個(gè)元素——復(fù)雜度O(N)
利用 list.pop(i) 或 list.remove(value) 刪除一個(gè)元素——復(fù)雜度O(N)

列表的算法效率
可以采用時(shí)間復(fù)雜度來(lái)衡量：

index() O(1)
append O(1)
pop() O(1)
pop(i) O(n)
insert(i,item) O(n)
del operator O(n)
iteration O(n)
contains(in) O(n)
get slice[x:y] O(k)
del slice O(n)
set slice O(n+k)
reverse O(n)
concatenate O(k)
sort O(nlogn)
multiply O(nk)

O括號(hào)里面的值越大代表效率越低

列表和元組
列表和元組的區(qū)別是顯然的：
列表是動(dòng)態(tài)的，其大小可以該標(biāo) (重新分配)；
而元組是不可變的，一旦創(chuàng)建就不能修改。

list和tuple在c實(shí)現(xiàn)上是很相似的，對(duì)于元素?cái)?shù)量大的時(shí)候，
都是一個(gè)數(shù)組指針，指針指向相應(yīng)的對(duì)象，找不到tuple比list快的理由。
但對(duì)于小對(duì)象來(lái)說，tuple會(huì)有一個(gè)對(duì)象池，所以小的、重復(fù)的使用tuple還有益處的。

為什么要有tuple，還有很多的合理性。
實(shí)際情況中的確也有不少大小固定的列表結(jié)構(gòu)，例如二維地理坐標(biāo)等；
另外tuple也給元素天然地賦予了只讀屬性。

認(rèn)為tuple比list快的人大概是把python的tuple和list類比成C++中的數(shù)組和列表了。

延伸閱讀：

二、列表元素添加

我們都知道，在上學(xué)的時(shí)候會(huì)有臨時(shí)加課的情況，有的時(shí)候是在中間的時(shí)候加課有的是在放學(xué)后加課。

放學(xué)后加課，在python的世界里，就相當(dāng)于在列表的末尾加一個(gè)元素，我們可以用列表的自帶方法append()方法來(lái)實(shí)現(xiàn)，格式是append(新元素名)，比如在下面的課表中加上音樂課

list=[‘語(yǔ)文’， ‘?dāng)?shù)學(xué)’， ‘英語(yǔ)’， ‘體育’， ‘政治’， ‘地理’， ‘美術(shù)’]

list.append(‘音樂’)

print(list)

#輸出：[‘語(yǔ)文’, ‘?dāng)?shù)學(xué)’, ‘英語(yǔ)’, ‘體育’, ‘政治’, ‘地理’, ‘美術(shù)’, ‘音樂’]

但是如果是在中間加課呢？我們可以用列表的insert()方法，格式為列表名.insert(索引，新元素)比如在第四節(jié)課后面加一節(jié)自習(xí)課

list=[‘語(yǔ)文’, ‘?dāng)?shù)學(xué)’,’英語(yǔ)’, ‘體育’, ‘政治’, ‘地理’, ‘美術(shù)’]

list.insert(4,’自習(xí)課’)

print(list)

#輸出：[‘語(yǔ)文’, ‘?dāng)?shù)學(xué)’, ‘英語(yǔ)’, ‘體育’, ‘自習(xí)課’, ‘政治’, ‘地理’, ‘美術(shù)’]