なぜPythonにネイティブリンクリスト実装がないのですか？

Question

私はネイティブのPythonリストのパフォーマンスをリンクリストの実装（例えばthis）と比較する簡単な実験を試みました。

ネイティブのPythonリストは、（理論に基づいて）存在してはならない場合のネイティブリンクリストよりも常に高速です。上記テストに私が

from linkedlist import * 
import time 
a = LinkedList() 
b = [] 
for i in range(1000000): 
    b.append(i) 
    a.add_first(i) 
t0 = time.clock() 
a.remove(10) 
t1 = time.clock() 
b.remove(10) 
t2 = time.clock() 
print t1-t0 
print t2-t1 

結果は次のとおり

• ネイティブリンクリスト= 2.00000000001e-05

• Pythonリスト= 0.005576

• 非天然のリストにリンク= 3.90000000001e-05

なぜ、PythonにネイティブのLinked Listデータ構造がないのだろうと思っていました。 Pythonの場合、標準的なライブラリのいくつかの側面をスピードアップするために、標準リストの代わりに リンクリストを持つことがアルゴリズム的には有用であると私は思っています。

私の理解では、リストデータ構造は言語の重要なビルディングブロックであり、コードをよりメンテナンスしやすくし、その非常にデータ構造に集中するように簡単に最適化できるようにします。

その他の理由はありますか？

Answer 1

Pythonはネイティブの二重リンクリストであるcollections.dequeを持っています。

Answer 2

これは、ビルドリストがメソッドを追加するのではなく、大半の時間を要するからです。したがって、あなたが示したように線形時間演算ではない場合、（例えば：n^2演算）appendメソッドは、見たい結果につながる建物よりも重要です。