質問: プログラミング歴1年の新人です pythonにはリストと言うものが存在しますが、この中身はどういった物なのでしょうか 私の認識ではlistと言うと連結リスト等の事を表してると思ったのですが、多くの入門サイトにおいては他の言語における配列と同じ物だと書かれているものもあります しかし、もしpythonのリストの中身が一般的にリストと呼ばれている(と私が誤認しているだけかもしれないが)物だとしたら、配列と同じ物と呼んでしまうと明らかに語弊があるのではないかと思います pythonのリストの中身はどういった物なのか、ご存知の方いらっしゃったらお願いします
回答: Python の リファレンス・マニュアル (日本語版はこちら) を読む限りでは、マニュアルのレベルでは Python の「リスト」がどのような実装になっているべきかは書かれていないようです。(ただし Python FAQ には書かれていました。) そこでこの投稿では、Python 処理系の実際の実装においてリストがどのように実現されているかに注目して回答します。 Python の処理系はいくつかありますが、ここでは標準的な実装である CPython を取り上げます。 ### CPython における実装 CPython は、C 言語によって実装された Python 処理系で、最も一般的に使われている処理系です。普段 `python` コマンドを実行したときに立ち上がっているものと考えて頂いて差し支えありません。 この処理系の実装では、「リスト」はいわゆる連結リストのことではありません。多くのサイトに書かれている通り、C 言語の配列とほぼ同じものだと考えてよいでしょう。正確にいうと、可変長かつ heterogeneous な配列になっています。 以下、もっと詳しく解説してみます。 CPython の実装では、リスト型の値を表す `PyListObject` 構造体が Include/listobject.h で定義されています (Python version 3.7.1 alpha 1 時点)。 今回大事な部分だけ抜き出してコードから引用すると、以下の通りです。 ``` typedef struct { /* 中略 */ /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */ PyObject **ob_item; /* 中略 */ } PyListObject; // CPython のコードより引用したものを加工しました。 ``` つまり、 **CPython のリストは「"各要素が置いてあるアドレス"の配列」の形で実装されています。** このように実装されていると、リストの `n` 番目の要素 `list[n]` へのアクセスが O(1) 時間で可能になります。(連結リストだと O(n) 時間かかります。) この意味で、CPython のリストの **中身** は C 言語における配列とほぼ同じと言えるでしょう。 ただし Python のリストをプログラムから触るときには、可変長であったり、違う型のオブジェクトを同じリストに入れられたりする (heterogeneous) ので、この意味では C 言語における生の配列とは少し違って感じられるかもしれません。 たとえば以下は CPython 3.6.0 で試してみた例です。`id(x)` で `x` のアドレスが分かります。 ``` >>> str = 'abc' >>> mylist = [1, 2, 3, 'one', str, str] >>> id(mylist) 140278170168200 >>> for item in mylist: ... print(id(item)) ... 140278195378432 140278195378464 140278195378496 140278167680088 140278196758432 140278196758432 >>> ``` リストの各要素が実際に置かれているアドレスは連続しておらず、まただんだん増えていっているわけでもないことが分かると思います。