4.5 まとめ¶
1. 要点の振り返り¶
- 配列と連結リストは 2 種類の基本的なデータ構造であり、それぞれコンピュータメモリにおけるデータの 2 つの格納方式、すなわち連続領域への格納と分散領域への格納を表す。両者の特徴は相互補完的である。
- 配列はランダムアクセスをサポートし、使用メモリも少ない。一方で、要素の挿入と削除の効率は低く、初期化後に長さを変更できない。
- 連結リストは参照（ポインタ）を変更することでノードの挿入と削除を効率的に行え、長さも柔軟に調整できる。一方で、ノードへのアクセス効率は低く、メモリ使用量も多い。一般的な連結リストには単方向連結リスト、循環連結リスト、双方向連結リストがある。
- リストは、追加・削除・検索・更新をサポートする順序付き要素集合であり、通常は動的配列に基づいて実装される。配列の利点を保ちながら、長さを柔軟に調整できる。
- リストの登場により配列の実用性は大幅に高まったが、一部のメモリ領域が無駄になる可能性がある。
- プログラムの実行時、データは主にメモリに格納される。配列はより高いメモリ空間効率を提供でき、連結リストはメモリ利用の面でより柔軟である。
- キャッシュは、キャッシュライン、プリフェッチ機構、空間局所性と時間局所性といったデータ読み込み機構を通じて CPU に高速なデータアクセスを提供し、プログラムの実行効率を大きく向上させる。
- 配列はキャッシュヒット率が高いため、通常は連結リストよりも高効率である。データ構造を選択する際は、具体的な要件や場面に応じて適切に選ぶべきである。
2. Q & A¶
Q：配列をスタックに格納する場合とヒープに格納する場合では、時間効率と空間効率に影響がありますか？
スタック上とヒープ上の配列はいずれも連続したメモリ領域に格納されるため、データ操作の効率は基本的に同じである。ただし、スタックとヒープにはそれぞれ特徴があり、以下の違いが生じる。
- 確保と解放の効率：スタックは比較的小さなメモリ領域で、確保はコンパイラによって自動的に行われる。一方、ヒープメモリは相対的に大きく、コード内で動的に確保できる反面、断片化しやすい。そのため、ヒープ上での確保と解放は通常スタック上より遅い。
- サイズ制限：スタックメモリは比較的小さく、ヒープのサイズは一般に利用可能メモリに制限される。そのため、ヒープは大きな配列の格納により適している。
- 柔軟性：スタック上の配列サイズはコンパイル時に確定している必要があるが、ヒープ上の配列サイズは実行時に動的に決定できる。
Q：なぜ配列では同じ型の要素が求められるのに、連結リストでは同じ型であることが強調されないのですか？
連結リストはノードで構成され、ノード同士は参照（ポインタ）で接続されている。各ノードには int、double、string、object など、異なる型のデータを格納できる。
これに対して、配列要素は同じ型でなければならない。そうでなければ、オフセットを計算して対応する要素位置を取得できないからである。たとえば、配列に int と long の 2 種類が同時に含まれていて、各要素がそれぞれ 4 バイトと 8 バイトを占める場合、配列内に 2 種類の「要素長」が存在するため、次の式ではオフセットを計算できない。
Q：ノード P を削除した後、P.next を None に設定する必要はありますか？
P.next を変更しなくてもよい。この連結リストの観点では、先頭ノードから末尾ノードまでたどっても、もはや P に出会うことはない。つまり、ノード P はすでに連結リストから削除されており、この時点で P がどこを指していても、この連結リストには影響しない。
データ構造とアルゴリズム（問題を解くとき）の観点では、切り離さなくても問題はなく、プログラムのロジックが正しいことを保証すればよい。標準ライブラリの観点では、切り離したほうがより安全で、ロジックも明確である。切り離さない場合、削除されたノードが適切に回収されなかったとすると、後続ノードのメモリ回収に影響する可能性がある。
Q：連結リストでの挿入と削除の時間計算量は \(O(1)\) です。しかし、追加や削除の前には要素を探すのに \(O(n)\) の時間が必要です。では、なぜ時間計算量は \(O(n)\) ではないのですか？
要素を先に探してから削除するのであれば、時間計算量が \(O(n)\) であるのは確かである。しかし、連結リストの \(O(1)\) での追加・削除という利点は、ほかの用途で生かせる。たとえば、両端キューは連結リストで実装するのに適しており、先頭ノードと末尾ノードを常に指すポインタ変数を維持すれば、各挿入・削除操作はどれも \(O(1)\) になる。
Q：図「連結リストの定義と格納方式」で、薄青色のノードポインタ部分は 1 つのメモリアドレスを占めているのですか？ それともノード値と半分ずつなのでしょうか？
この模式図は定性的な表現にすぎず、定量的な表現は具体的な状況に応じて分析する必要がある。
- ノード値が占める領域は型によって異なり、たとえば
int、long、double、インスタンスオブジェクトなどがある。 - ポインタ変数が占めるメモリ空間の大きさは、使用する OS やコンパイル環境によって異なり、多くは 8 バイトまたは 4 バイトである。
Q：リストの末尾への要素追加は常に \(O(1)\) ですか？
要素を追加する際にリスト長を超える場合は、先にリストを拡張してから追加する必要がある。システムは新しいメモリ領域を確保し、元のリストの全要素をそこへ移動するため、このとき時間計算量は \(O(n)\) になる。
Q：「リストの登場により配列の実用性は大きく向上したが、一部のメモリ空間が無駄になる可能性がある」というのは、容量、長さ、拡張倍率のような追加変数が占めるメモリのことですか？
ここでいう空間の無駄には主に 2 つの意味がある。一方では、リストには初期長が設定されるが、必ずしもそれだけ必要とは限らない。もう一方では、頻繁な拡張を防ぐため、拡張時には通常ある係数、たとえば \(\times 1.5\) を掛ける。このため、多くの空きスロットが生じ、通常それらを完全に埋めることはできない。
Q：Python で n = [1, 2, 3] を初期化した後、この 3 つの要素のアドレスは連続しています。しかし m = [2, 1, 3] を初期化すると、各要素の id は連続しておらず、それぞれ n 内の同じ値と一致していることがわかります。これらの要素のアドレスが連続していないなら、m も配列なのですか？
仮にリスト要素を連結リストのノード n = [n1, n2, n3, n4, n5] に置き換えたとしても、通常この 5 つのノードオブジェクトもメモリ上の各所に分散して格納される。それでも、与えられたリストインデックスに対して、私たちは依然として \(O(1)\) 時間でノードのメモリアドレスを取得し、対応するノードにアクセスできる。これは、配列に格納されているのがノードそのものではなく、ノードへの参照だからである。
多くの言語と異なり、Python では数値もオブジェクトとしてラップされており、リストに格納されているのは数値そのものではなく、数値への参照である。そのため、2 つの配列内の同じ数値が同一の id を持つことがあり、しかもそれらの数値のメモリアドレスは連続している必要がない。
Q：C++ STL の std::list はすでに双方向連結リストを実装していますが、アルゴリズム本ではあまり直接使われないようです。何か制約があるのでしょうか？
一方では、私たちは多くの場合、アルゴリズムの実装に配列を好み、必要なときにだけ連結リストを使う。その主な理由は 2 つある。
- 空間オーバーヘッド：各要素には 2 つの追加ポインタ（前の要素用と次の要素用）が必要なため、
std::listは通常std::vectorより多くの空間を消費する。 - キャッシュ非効率：データが連続して格納されていないため、
std::listはキャッシュの利用効率が低い。一般には、std::vectorのほうが性能がよい。
もう一方では、連結リストを使う必要がある代表的な場面は主に二分木とグラフである。スタックやキューについては、連結リストではなく、たいてい言語が提供する stack と queue を使う。
Q：res = [[0]] * n という操作で 2 次元リストを生成した場合、それぞれの [0] は独立していますか？
独立していない。この 2 次元リストでは、すべての [0] は実際には同一オブジェクトへの参照である。そのうちの 1 つを変更すると、対応するすべての要素が一緒に変化することがわかる。
2 次元リスト内の各 [0] を独立させたい場合は、res = [[0] for _ in range(n)] を使って実現できる。この方式の原理は、独立した [0] リストオブジェクトを \(n\) 個初期化していることにある。
Q：res = [0] * n という操作で生成されたリストでは、それぞれの整数 0 は独立していますか？
このリストでは、すべての整数 0 が同一オブジェクトへの参照である。これは、Python が小さな整数（通常は -5 から 256）に対してキャッシュプール機構を採用し、オブジェクトの再利用を最大化して性能を向上させているためである。
それらは同じオブジェクトを指しているが、それでもリスト内の各要素は独立して変更できる。これは、Python の整数が「イミュータブルオブジェクト」だからである。ある要素を変更するとき、実際には別のオブジェクトへの参照に切り替わるのであって、元のオブジェクトそのものを変更しているわけではない。
しかし、リスト要素が「ミュータブルオブジェクト」（たとえばリスト、辞書、クラスインスタンスなど）である場合は、ある要素を変更するとそのオブジェクト自体が直接変更され、そのオブジェクトを参照しているすべての要素に同じ変化が生じる。