python的list是數組的結構還是鏈表的結構？

01-28

之前看網上教程：「在大數據下（比如根據學生姓名查找對應分數），list的查找元素的速度要遠遠慢於dict（dict是用key來找對應的value），因為要建立兩個list，一個放姓名，一個放分數；在查找時，要先將輸入的名字與第一個list的元素進行逐一對比，然後得到相應位置，再到第二個list里找到對應分數，所以數據越大，速度越慢。而dict只需要一個「名字」-「成績」的對照表，直接根據名字查找成績，無論這個表有多大，查找速度都不會變慢」
我覺著按照這個描述，如果list結構是和c++里的數組一樣，根據首地址+偏移地址來查找的話，那無論多大的數據，兩者應該是差不多的速度呀，都要先根據輸入的名字，先逐一對照名字。而如果list是鏈表結構的話，那的確在這種情況下，dict比list要快，因為用list實現的話，要遍歷兩遍。
難不成是我對dict的本質還是沒有認識清楚？

假設有

names = [張三, 『李四』, .....中間一堆...., 趙五, ...另外一堆...]

scores = [77, 88, .....中間一堆..., 99, ...另外一堆...]

names和scores裡面的元素是一一對應的，那麼，如何查找趙五的分數呢？因為我們並不知道趙五是names裡面的第幾個元素，所以必須要遍歷。

別人說的是這個：

for index, name in enumerate(names): if name == 趙五: print(scores[index])

只要你找出index了，取出來當然是很快的。這個取的過程就是你說的「首地址+偏移地址」，即scores[index].

但是怎麼知道index呢？這個過程慢。

你的理解是針對scores[index]的：

scores是數組所以scores[index]快，如果scores是鏈表的話要還要挨個遍歷所以scores[index]慢。。。

從這點來說你的理解是對的，鏈表找第幾個確實比數組找第幾個慢得多。因為鏈表要挨個遍歷，數組直接取偏移地址就好了。

但是這個跟別人說的事情不是一回事:

別人說的是找這個偏移地址慢 (for index, name in enumerate(names):)

你說的是找到這個偏移地址之後取值慢 ( scores[index] )

你可以試一下deque，那個就是鏈表。自己手動實現一下，用timeit之類的測一下。

比在這問問題強。

那麼為什麼dict快呢，簡單的來說，dict並不是逐一比較名字，它本身在存儲的時候就帶了查詢的結構，所以查起來快. 具體實現的話，看看hash table是咋回事就行了。

1、In CPython, lists are arrays of pointers

可以看源代碼

https://svn.python.org/projects/python/trunk/Objects/listobject.c

2、字典是

Dictionary object implementation using a hash table

https://svn.python.org/projects/python/trunk/Objects/dictobject.c

3、Python中數據結構的時間複雜度請看

TimeComplexity - Python Wiki

是的，題主對dict的本質還不太清楚。

list 是用數組實現的，dict 使用hash表實現的。

這個你就不必懷疑了。

如你所說，用兩個list（數組）存名字和成績。

查找時需要逐一比較名字，複雜度是o（n）

但哈希表的查找效率是o（1）。

字典是不需要遍歷的, 因為每次查找都是先計算hash值, 然後訪問的.

list 實現方式是 arraylist，即數組，

沒人會用鏈表實現存儲很多元素的數據結構的，O(n)時間訪問完全不可容忍
除非確定這個鏈表一定不太大（比如鏈表經常被用來解決Hash表衝突）
數組的插入是慢點，不過現在內存操作很快的，無所謂了。

python 中list對象的存儲結構採用的是線性表，因此其查詢複雜度為O(n),而dict對象的存儲結構採用的是散列表(hash表)，其在最優情況下查詢複雜度為O(1)。