36727


プログラミング歴1年の新人です  
pythonにはリストと言うものが存在しますが、この中身はどういった物なのでしょうか  
私の認識ではlistと言うと連結リスト等の事を表してると思ったのですが、多くの入門サイトにおいては他の言語における配列と同じ物だと書かれているものもあります  
しかし、もしpythonのリストの中身が一般的にリストと呼ばれている（と私が誤認しているだけかもしれないが）物だとしたら、配列と同じ物と呼んでしまうと明らかに語弊があるのではないかと思います  
pythonのリストの中身はどういった物なのか、ご存知の方いらっしゃったらお願いします


CC BY-SA 3.0
2017-07-27T05:25:05.673
36710
2017-08-06T22:20:34.547
2017-08-06T22:20:34.547
19110
24599
question
python
pythonのリストの中身はどういった物？


(プログラマからの観点)Pythonのリストの構造は、リニア リストですから、配列とほぼ同義です。

(内部構造)Pythonはリスト、配列、タプルなど様々な構造を持っていますので、その内部表現ではリンク(ポインター)が活用されているだろうと推測します。連結リストも使われているのではないでしょうか。


CC BY-SA 3.0
2017-07-27T07:26:39.730
36716
2017-07-27T07:26:39.730
217
36710
answer


[本家の Fred Foo さんの回答](https://stackoverflow.com/a/3958322/3090068)によれば、CPython
の実装には「ポインタの配列」が使われている様子です。

[code]

    typedef struct {
        PyObject_HEAD
        Py_ssize_t ob_size;
    
        /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
        PyObject **ob_item;
    
        /* ob_item contains space for 'allocated' elements.  The number
         * currently in use is ob_size.
         * Invariants:
         *     0 <= ob_size <= allocated
         *     len(list) == ob_size
         *     ob_item == NULL implies ob_size == allocated == 0
         */
        Py_ssize_t allocated;
    } PyListObject;
    
[/code]

なので、配列と同じようなものと考えても問題ありません。  
(他の言語でいうと、 C++ ならば vector, Java ならば ArrayList でしょうか。)


CC BY-SA 3.0
2017-07-27T08:41:33.933
36718
2017-07-27T08:41:33.933
754
36710
answer


[TimeComplexity - Python
Wiki](https://wiki.python.org/moin/TimeComplexity)によればCPythonのリストは配列で実装されています。さらに重要なのは`Get
Item`, `Set
Item`がC等の配列と同じくO(1)で行える=ランダムアクセスができるという点です。この特徴を以って「他の言語における配列と同じ物」と言っているのだと思います。


CC BY-SA 3.0
2017-07-27T09:54:06.630
36721
2017-07-27T09:54:06.630
13199
36710
answer


Python の [リファレンス・マニュアル](https://docs.python.org/3/reference/)
([日本語版はこちら](https://docs.python.jp/3/reference/index.html))
を読む限りでは、マニュアルのレベルでは Python の「リスト」がどのような実装になっているべきかは書かれていないようです。(ただし [Python
FAQ](https://docs.python.org/3/faq/design.html#how-are-lists-implemented)
には書かれていました。)

そこでこの投稿では、Python 処理系の実際の実装においてリストがどのように実現されているかに注目して回答します。  
Python の処理系はいくつかありますが、ここでは標準的な実装である CPython を取り上げます。

### CPython における実装

[CPython](https://github.com/python/cpython) は、C 言語によって実装された Python
処理系で、最も一般的に使われている処理系です。普段 `python` コマンドを実行したときに立ち上がっているものと考えて頂いて差し支えありません。  
この処理系の実装では、「リスト」はいわゆる[連結リスト](https://ja.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E3%83%AA%E3%82%B9%E3%83%88)のことではありません。多くのサイトに書かれている通り、C
言語の[配列](https://ja.wikipedia.org/wiki/%E9%85%8D%E5%88%97)とほぼ同じものだと考えてよいでしょう。正確にいうと、可変長かつ
heterogeneous な配列になっています。

以下、もっと詳しく解説してみます。  
CPython の実装では、リスト型の値を表す `PyListObject` 構造体が
[Include/listobject.h](https://github.com/python/cpython/blob/master/Include/listobject.h)
で定義されています (Python version 3.7.1 alpha 1 時点)。  
今回大事な部分だけ抜き出してコードから引用すると、以下の通りです。

[code]

    typedef struct {
        /* 中略 */
        /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
        PyObject **ob_item;
        /* 中略 */
    } PyListObject;
    // CPython のコードより引用したものを加工しました。
    
[/code]

つまり、 **CPython のリストは「"各要素が置いてあるアドレス"の配列」の形で実装されています。**  
このように実装されていると、リストの `n` 番目の要素 `list[n]` へのアクセスが O(1) 時間で可能になります。（連結リストだと O(n)
時間かかります。)  
この意味で、CPython のリストの **中身** は C 言語における配列とほぼ同じと言えるでしょう。

ただし Python
のリストをプログラムから触るときには、[可変長](https://ja.wikipedia.org/wiki/%E9%85%8D%E5%88%97#.E5.8B.95.E7.9A.84.E9.85.8D.E5.88.97)であったり、違う型のオブジェクトを同じリストに入れられたりする
(heterogeneous) ので、この意味では C 言語における生の配列とは少し違って感じられるかもしれません。

たとえば以下は CPython 3.6.0 で試してみた例です。`id(x)` で `x` のアドレスが分かります。

[code]

    >>> 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
    >>> 
    
[/code]

リストの各要素が実際に置かれているアドレスは連続しておらず、まただんだん増えていっているわけでもないことが分かると思います。


CC BY-SA 3.0
2017-07-27T12:07:21.397
36727
2017-07-27T12:29:43.647
2017-07-27T12:29:43.647
19110
19110
36710
answer