Python 列表的數(shù)據(jù)結(jié)構(gòu)是怎么樣的？

列表實(shí)際上采用的就是數(shù)據(jù)結(jié)構(gòu)中的順序表，而且是一種采用分離式技術(shù)實(shí)現(xiàn)的動(dòng)態(tài)順序表

但這是不是Python的列表？

我的結(jié)論是順序表是列表的一種實(shí)現(xiàn)方式。

書(shū)上說(shuō)的是：列表實(shí)現(xiàn)可以是數(shù)組和鏈表。

順序表是怎么回事？順序表一般是數(shù)組。

列表是一個(gè)線性的集合，它允許用戶在任何位置插入、刪除、訪問(wèn)和替換元素。

列表實(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ù)中常見(jiàn)的鏈表混淆。事實(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ì)過(guò)高。

利用 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)說(shuō)，tuple會(huì)有一個(gè)對(duì)象池，所以小的、重復(fù)的使用tuple還有益處的。

為什么要有tuple，還有很多的合理性。

實(shí)際情況中的確也有不少大小固定的列表結(jié)構(gòu)，例如二維地理坐標(biāo)等；

另外tuple也給元素天然地賦予了只讀屬性。

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

補(bǔ)充：python list, tuple, dictionary, set的底層細(xì)節(jié)

list, tuple, dictionary, set是python中4中常見(jiàn)的集合類型。在筆者之前的學(xué)習(xí)中，只是簡(jiǎn)單了學(xué)習(xí)它們4者的使用，現(xiàn)記錄一下更深底層的知識(shí)。

列表和元組

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

實(shí)現(xiàn)細(xì)節(jié)

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

從細(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ù)過(guò)分配，所以并不是每次操作都需要改變數(shù)組的大小。但是，也因?yàn)檫@個(gè)原因添加或取出元素的平攤復(fù)雜度較低。

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

利用 list.insert方法在任意位置插入一個(gè)元素——復(fù)雜度O(N)

利用 list.delete或del刪除一個(gè)元素——復(fù)雜度O(N)

操作 復(fù)雜度 復(fù)制 O(N) 添加元素(在尾部添加) O(1) 插入元素(在指定位置插入) O(N) 獲取元素 O(1) 修改元素 O(1) 刪除元素 O(N) 遍歷 O(N) 獲取長(zhǎng)度為k的切片 O(k) 刪除切片 O(N) 列表擴(kuò)展 O(k) 測(cè)試是否在列表中 O(N) min()/max() O(n) 獲取列表長(zhǎng)度 O(1) 列表推導(dǎo)

要習(xí)慣用列表推導(dǎo)，因?yàn)檫@更加高效和簡(jiǎn)短，涉及的語(yǔ)法元素少。在大型的程序中，這意味著更少的錯(cuò)誤，代碼也更容易閱讀。

>>>[i for i in range(10) if i % 2 == 0] [0, 2, 4, 6, 8]其它習(xí)語(yǔ)

1.使用enumerate.在循環(huán)使用序列時(shí)，這個(gè)內(nèi)置函數(shù)可以方便的獲取其索引：

for i, element in enumerate([’one’, ’two’, ’three’]): print(i, element)

result：

0 one1 two2 three

2.如果需要一個(gè)一個(gè)合并多個(gè)列表中的元素，可以使用zip()。對(duì)兩個(gè)大小相等的可迭代對(duì)象進(jìn)行均勻遍歷時(shí)，這是一個(gè)非常常用的模式：

for item in zip([1, 2, 3], [4, 5, 6]): print(item)

(1, 4)(2, 5)(3, 6)

3.序列解包

#帶星號(hào)的表達(dá)式可以獲取序列的剩余部分>>>first, second, *reset = 0, 1, 2, 3>>>first0>>>second1>>>reset[2, 3]字典

字典是python中最通用的數(shù)據(jù)結(jié)構(gòu)之一。dict可以將一組唯一的鍵映射到相應(yīng)的值。

我們也可以用前面列表推導(dǎo)的方式來(lái)創(chuàng)建一個(gè)字典。

squares = {number: number**2 for number in range(10)}print(squares)

result：

{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}

在遍歷字典元素時(shí)，有一點(diǎn)需要特別注意。字典里的keys(), values()和items()3個(gè)方法的返回值不再是列表，而是視圖對(duì)象（view objects）。

keys(): 返回dict_keys對(duì)象，可以查看字典所有鍵

values():返回dict_values對(duì)象，可以查看字典的所有值

items():返回dict_items對(duì)象，可以查看字典所有的{key, value}二元元組。

視圖對(duì)象可以動(dòng)態(tài)查看字典的內(nèi)容，因此每次字典發(fā)生變化的時(shí)候，視圖都會(huì)相應(yīng)的改變，見(jiàn)下面這個(gè)例子：

words = {’foo’: ’bar’, ’fizz’: ’bazz’}items= words.items()words[’spam’] = ’eggs’print(items)

result：

dict_items([(’foo’, ’bar’), (’fizz’, ’bazz’), (’spam’, ’eggs’)])

視圖無(wú)需冗余的將所有值都保存在內(nèi)存中，像列表那樣。但你仍然可以獲取其長(zhǎng)度（使用len）,也可以測(cè)試元素是否包含在其中（使用in子句）。當(dāng)然，視圖是迭代的。

實(shí)現(xiàn)細(xì)節(jié)

CPython使用偽隨機(jī)探測(cè)(pseudo-random probing)的散列表(hash table)作為字典的底層數(shù)據(jù)結(jié)構(gòu)。由于這個(gè)實(shí)現(xiàn)細(xì)節(jié)，只有可哈希的對(duì)象才能作為字典的鍵。

Python中所有不可變的內(nèi)置類型都是可哈希的。可變類型（如列表，字典和集合）就是不可哈希的，因此不能作為字典的鍵。

字典的三個(gè)基本操作（添加元素，獲取元素和刪除元素）的平均事件復(fù)雜度為O(1)，但是他們的平攤最壞情況復(fù)雜度要高得多，為O(N).

操作 平均復(fù)雜度 平攤最壞情況復(fù)雜度 獲取元素 O(1) O(n) 修改元素 O(1) O(n) 刪除元素 O(1) O(n) 復(fù)制 O(n) O(n) 遍歷 O(n) O(n)

還有一點(diǎn)很重要，在復(fù)制和遍歷字典的操作中，最壞的復(fù)雜度中的n是字典曾經(jīng)達(dá)到的最大元素?cái)?shù)目，而不是當(dāng)前的元素?cái)?shù)目。換句話說(shuō)，如果一個(gè)字典曾經(jīng)元素個(gè)數(shù)很多，后來(lái)又大大減小了，那么遍歷這個(gè)字典可能會(huì)花費(fèi)相當(dāng)長(zhǎng)的事件。

因此在某些情況下，如果需要頻繁的遍歷某個(gè)詞典，那么最好創(chuàng)建一個(gè)新的字典對(duì)象，而不是僅在舊字典中刪除元素。

字典的缺點(diǎn)和替代方案

使用字典的常見(jiàn)陷阱就是，它并不會(huì)按照鍵的添加順序來(lái)保存元素的順序。在某些情況下，字典的鍵是連續(xù)的，對(duì)應(yīng)的散列值也是連續(xù)值（例如整數(shù)），那么由于字典的內(nèi)部實(shí)現(xiàn)，元素的實(shí)現(xiàn)可能和添加的順序相同：

keys = {num: None for num in range(5)}.keys()print(keys)

result：

dict_keys([0, 1, 2, 3, 4])

但是，如果散列方法不同的其它數(shù)據(jù)類型，那么字典就不會(huì)保存元素順序。

age = {str(i): i for i in range(100)}keys = age.keys()print(keys)

result：

dict_keys([’0’, ’1’, ’2’, ’3’, ’4’, ’5’, ’6’, ’7’, ’8’, ’9’, ’10’, ’11’, ’12’, ’13’, ’14’, ’15’, ’16’, ’17’, ’18’, ’19’, ’20’, ’21’, ’22’, ’23’, ’24’, ’25’, ’26’, ’27’, ’28’, ’29’, ’30’, ’31’, ’32’, ’33’, ’34’, ’35’, ’36’, ’37’, ’38’, ’39’, ’40’, ’41’, ’42’, ’43’, ’44’, ’45’, ’46’, ’47’, ’48’, ’49’, ’50’, ’51’, ’52’, ’53’, ’54’, ’55’, ’56’, ’57’, ’58’, ’59’, ’60’, ’61’, ’62’, ’63’, ’64’, ’65’, ’66’, ’67’, ’68’, ’69’, ’70’, ’71’, ’72’, ’73’, ’74’, ’75’, ’76’, ’77’, ’78’, ’79’, ’80’, ’81’, ’82’, ’83’, ’84’, ’85’, ’86’, ’87’, ’88’, ’89’, ’90’, ’91’, ’92’, ’93’, ’94’, ’95’, ’96’, ’97’, ’98’, ’99’])

理論上，鍵的順序不應(yīng)該是這樣的，應(yīng)該是亂序。。。具體為什么這樣，等以后明白了再補(bǔ)充

如果我們需要保存添加順序怎么辦？python 標(biāo)準(zhǔn)庫(kù)的collections模塊提供了名為OrderedDicr的有序字典。

集合

集合是一種魯棒性很好的數(shù)據(jù)結(jié)構(gòu)，當(dāng)元素順序的重要性不如元素的唯一性和測(cè)試元素是否包含在集合中的效率時(shí)，大部分情況下這種數(shù)據(jù)結(jié)構(gòu)極其有用。

python的內(nèi)置集合類型有兩種：

set(): 一種可變的、無(wú)序的、有限的集合，其元素是唯一的、不可變的（可哈希的）對(duì)象。

frozenset(): 一種不可變的、可哈希的、無(wú)序的集合，其元素是唯一的，不可變的哈希對(duì)象。

set([set([1, 2, 3]), set([2, 3, 4])])

result:

Traceback (most recent call last): File '/pycharm_project/LearnPython/Part1/demo.py', line 1, in <module> set([set([1, 2, 3]), set([2, 3, 4])])TypeError: unhashable type: ’set’

set([frozenset([1, 2, 3]), frozenset([2, 3, 4])])

result:不會(huì)報(bào)錯(cuò)

set里的元素必須是唯一的，不可變的。但是set是可變的，所以set作為set的元素會(huì)報(bào)錯(cuò)。

實(shí)現(xiàn)細(xì)節(jié)

CPython中集合和字典非常相似。事實(shí)上，集合被實(shí)現(xiàn)為帶有空值的字典，只有鍵才是實(shí)際的集合元素。此外，集合還利用這種沒(méi)有值的映射做了其它的優(yōu)化。

由于這一點(diǎn)，可以快速的向集合中添加元素、刪除元素、檢查元素是否存在。平均時(shí)間復(fù)雜度為O(1),最壞的事件復(fù)雜度是O(n)。

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持好吧啦網(wǎng)。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教。