python - Python はリストに連結リストを使用しますか? 挿入が遅いのはなぜですか？

Question

Pythonを学んでいるだけです。公式チュートリアルを読む。私はこれに出くわしました：

リストの末尾からの追加とポップは高速ですが、リストの先頭からの挿入またはポップは低速です (他のすべての要素を 1 つシフトする必要があるため)。

Python のような成熟した言語にはあらゆる種類の最適化があると推測していましたが、なぜ Python は連結リストを使用して挿入を高速化しないのでしょうか?

Answer 1

Python はメモリ内で線形リスト レイアウトを使用するため、インデックス作成は高速です (O(1))。

Answer 2

Greg Hewgill がすでに指摘しているように、python リストは連続したメモリ ブロックを使用してインデックス作成を高速化します。dequeリンクされたリストのパフォーマンス特性が必要な場合は、を使用できます。しかし、あなたの最初の前提には欠陥があるようです。(標準の) リンク リストの途中へのインデックス付き挿入も低速です。

Answer 3

list配列リストとして実装されています。頻繁に挿入したい場合は、 a を使用できますdeque(ただし、途中までのトラバーサルはコストがかかることに注意してください)。

または、ヒープを使用できます。時間をかけてドキュメントを参照すれば、すべて揃っています。

Answer 4

Python が「リスト」と呼ぶものは、実際にはリンクされたリストではありません。それらは配列に似ています。Python 用語集のリスト エントリと、Pythonで配列を作成するにはどうすればよいですか?も参照してください。Python FAQ から。