ベストアンサー
名前が示すとおり、Pythonリストは実際には配列であり、私を悩ませることは決してありません（私は「誤解を招くような名前は好きではありません。具体的には、指数関数的な過剰割り当てを伴う動的配列であるため、次のようなコードは線形の複雑さを持つことができます。
lst = []
for i in xrange(0, 100000):
lst.append(i)
興味深いことに、 CPythonは、1.125 * new\_size + 6（または配列が9要素よりも小さい場合は+ 3）を割り当てるため、非常に保守的です。その1.125定数はかなり珍しいものであり、前述したように、非常に保守的であるため、追加呼び出しはそれほど一般的ではありません。動的配列の実装は通常2や1.5のような定数を使用します（gcc / clangのstd :: vectorの実装を確認したところ、2を使用しています。Microsoftコンパイラの実装は1.5を使用していることを覚えているようです。 ）。 +3と+6の定数がどこから来たのかはわかりませんが、これを書いた人は誰でも、+ 3が小さな配列に最適なポリシーであり、+ 6がかなり小さな配列に最適であることがわかったと思います（たとえば、100未満）であり、大きな配列ではまったく問題ではないので、そのままにしておくのはなぜですか。
JythonやIronPythonなどの代替実装では、基盤となるネイティブの動的配列クラスを使用しているようです。言語（それぞれJavaとC＃）が提供するため、同じパフォーマンス特性を備えています（正確な基礎となるクラスは、JythonのArrayListとIronPythonのC＃Listのようです）。
コメントで誰かがそれがどのように可能であるかを尋ねました。異種タイプの要素の配列を持つため（[1、 “hello”]はPythonで有効なリストです）。その質問に対する答えは、配列にはオブジェクト自体ではなくポインタが技術的に格納されているため、配列に特定のサイズの要素のみを含めることができます。基礎となる実装のいたるところにポインターがあることは、動的型付け言語の一般的な機能であり、実際、それを装おうとする言語にはポインターがありません。
回答
Adrien Lucas Ecoffetが言ったように、Pythonリストは可変長配列に他なりません。cpythonのソースコードを掘り下げてマクロを展開すると、基本構造は次のように定義されます。
typedef struct {
PyObject\_VAR\_HEAD
PyObject **ob\_item;
Py\_ssize\_t allocated;
} PyListObject;
ここでコメントを削除しました。元のコメントを参照してくださいここにコードを記述します。 6c2e2de5ab8e Include / listobject.h
PyObject\_VAR\_HEADには、参照カウントと型識別子が含まれています。つまり、ベクトル/配列です。それは過剰に割り当てます。このような配列がいっぱいになったときにサイズを変更するためのコードは、 listobject.c にあります。これは、list\_resizeを何度も呼び出さないように、メモリを過剰に割り当てます。成長パターンリストの内容は次のとおりです：0、4、8、16、25、35、46、58、72、88、…
arguments: list object, new size
returns: 0 if OK, -1 if not
list\_resize:
new\_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6)
new\_allocated += newsize
resize ob\_item (list of pointers) to size new\_allocated
return 0
追加、挿入、削除、拡張など、リストPythonリスト実装のすべてのリストされたメソッドを確認するには、この優れたブログ投稿を参照してください。