Pythonでプログラムを書くとき、ほぼ必須となるデータ構造であるリスト (list) の仕組みを紹介します。僕自身Pythonをよく使うのですが、これまで実装を意識してこなかったので、内部の仕組みについてまとめてみました。Pythonのリストは要素の追加 (list.append) /削除 (list.pop) により、サイズが動的に変更されますが、これらはO(1)で高速に行う (list.popは末尾要素のみ) ことができます。この記事ではその理由について解説していきます。 Pythonのリストのような特徴を持ったデータ構造は動的配列 (dynamic array) と呼ばれます。通常の配列は静的配列 (static array)として区別されます。 この記事では、動的配列の概要、要素の追加/削除について、MITの講義 (Table Doubling, Karp-Rabin) を元に以
![Pythonユーザーなら知っておきたいのリストの仕組み – Yasufumi Taniguchi – Medium](https://cdn-ak-scissors.b.st-hatena.com/image/square/cb65a9f2dba0cbb2ba48469f45cc70cc9fbf49b5/height=288;version=1;width=512/https%3A%2F%2Fmiro.medium.com%2Fv2%2Fresize%3Afit%3A785%2F1%2AGqoRU084fvULAGZwsU-G-Q.png)