Q

Python是否使用鏈表作爲列表？爲什麼插入緩慢？

python

2012-09-05 23 views 10 likes

10

剛剛學習Python。閱讀官方教程。我跑過這樣的：Python是否使用鏈表作爲列表？爲什麼插入緩慢？

雖然從列表的末尾附加和持久性有機污染物的速度快，執行插入或彈出從列表的開始是緩慢的（因爲所有其他元素都必須通過一個移位）。

我會猜想像Python這樣的成熟語言會有各種各樣的優化，那麼爲什麼Python [似乎]不使用鏈接列表，以便插入可以很快？

2012-09-05 loneboat

+2

你可以實現一個非常平凡和使用它，如果你想太多，但它會減慢訪問...... –

+0

每個數據結構都有其權衡。 Python選擇了一個不適合插入的選項。 –

+0

查看[這個問題]的答案（http：// stackoverflow。com/questions/7477181/array-based-vs-list-based-stacks-and-queues）來檢查權衡。 –

A

回答

18

Python在內存中使用線性列表佈局，因此索引很快（O（1））。

2012-09-05 03:22:01

8

正如Greg Hewgill已經指出的那樣，python列表使用連續的內存塊來快速建立索引。如果您需要鏈接列表的性能特徵，則可以使用deque。但是你的初始前提對我來說似乎有缺陷。索引插入到（標準）鏈表的中間也很慢。

2012-09-05 03:26:52 senderle

+0

我應該澄清我的前提。想要說的是，「......這樣插入開始就很快。」 – loneboat

2

list作爲一個數組列表來實現。如果你想經常插入，你可以使用deque（但是注意到中間的遍歷是昂貴的）。

或者，您可以使用堆。如果您花時間查看文檔，這一切都在那裏。

2012-09-05 03:27:19 Marcin

3

Python被稱爲「列表」的東西實際上並不是鏈表;他們更像陣列。請參閱Python FAQ中的list entry from the Python glossary和How do you make an array in Python?。

2012-09-05 03:29:02 jamesdlin

1

Python列表是使用對其他對象的可調整大小的引用數組實現的。與O（n）查找相比，這提供了O（1）查找的鏈接列表實現。

見How are lists implemented?

至於你提到的這個實施，使得插入到一個Python列表緩慢的開始或中間，因爲數組插入點右側中的每個元素必須要移動一個元素。此外，有時該陣列將不得不調整以容納更多元素。對於插入到鏈表中，您仍然需要O（n）時間來查找要插入的位置，但實際插入本身將爲O（1），因爲您只需立即更改節點中的引用插入點之前和之後（假設爲雙向鏈表）。

因此，決定讓Python列表使用動態數組而不是鏈接列表與語言實現的「成熟度」無關。只是在不同的數據結構之間進行權衡，Python的設計者決定動態數組是整體上最好的選擇。他們可能認爲索引列表比將數據插入索引更常見，因此在這種情況下使動態數組成爲更好的選擇。

請參閱下表中的各種數據結構，性能特點的比較動態數組維基百科文章：

https://en.wikipedia.org/wiki/Dynamic_array#Performance

2015-07-03 17:40:16

相關問題