4.5 まとめ¶
1. 重要な復習¶
- 配列と連結リストは2つの基本的なデータ構造であり、コンピュータメモリにおける2つの格納方法を表しています：連続空間格納と非連続空間格納です。それらの特性は互いに補完し合います。
- 配列はランダムアクセスをサポートし、使用するメモリが少ない一方で、要素の挿入と削除は非効率的で、初期化後の長さが固定されています。
- 連結リストは参照（ポインタ）の変更によって効率的なノードの挿入と削除を実装し、長さを柔軟に調整できますが、ノードアクセス効率が低く、より多くのメモリを消費します。
- 連結リストの一般的な種類には、単方向連結リスト、循環連結リスト、双方向連結リストがあり、それぞれに独自の応用シナリオがあります。
- リストは要素の順序付けられたコレクションで、追加、削除、変更をサポートし、通常は動的配列に基づいて実装され、配列の利点を保持しながら柔軟な長さ調整を可能にします。
- リストの出現により配列の実用性が大幅に向上しましたが、一部のメモリ空間の無駄につながる可能性があります。
- プログラム実行中、データは主にメモリに格納されます。配列はより高いメモリ空間効率を提供し、連結リストはメモリ使用においてより柔軟です。
- キャッシュは、キャッシュライン、先読み、空間的局所性、時間的局所性などのメカニズムを通じてCPUに高速データアクセスを提供し、プログラム実行効率を大幅に向上させます。
- より高いキャッシュヒット率により、配列は一般的に連結リストよりも効率的です。データ構造を選択する際は、特定のニーズとシナリオに基づいて適切な選択をすべきです。
2. Q & A¶
Q：配列をスタックに格納するかヒープに格納するかは、時間と空間効率に影響しますか？
スタックとヒープの両方に格納される配列は連続したメモリ空間に格納され、データ操作効率は本質的に同じです。しかし、スタックとヒープには独自の特性があり、以下の違いが生じます。
- 割り当てと解放効率：スタックはより小さなメモリブロックで、コンパイラによって自動的に割り当てられます。ヒープメモリは比較的大きく、コードで動的に割り当てることができ、断片化しやすいです。したがって、ヒープでの割り当てと解放操作は一般的にスタックよりも遅くなります。
- サイズ制限：スタックメモリは比較的小さく、ヒープサイズは一般的に利用可能なメモリによって制限されます。したがって、ヒープは大きな配列の格納により適しています。
- 柔軟性：スタック上の配列のサイズはコンパイル時に決定される必要がありますが、ヒープ上の配列のサイズは実行時に動的に決定できます。
Q：なぜ配列は同じ型の要素を必要とし、連結リストは同じ型の要素を強調しないのですか？
連結リストは参照（ポインタ）によって接続されたノードで構成され、各ノードはint、double、string、objectなど、異なる型のデータを格納できます。
対照的に、配列要素は同じ型である必要があり、これにより対応する要素位置にアクセスするためのオフセットを計算できます。例えば、intとlong型の両方を含む配列で、単一要素がそれぞれ4バイトと8バイトを占有する場合、配列に2つの異なる長さの要素が含まれているため、以下の式を使用してオフセットを計算できません。
Q：ノードを削除した後、P.nextをNoneに設定する必要がありますか？
P.nextを変更しなくても問題ありません。連結リストの観点から、ヘッドノードからテールノードまでの巡回でPに遭遇することはもうありません。これは、ノードPがリストから効果的に削除されたことを意味し、Pが指す場所はもはやリストに影響しません。
ガベージコレクションの観点から、Java、Python、Goなどの自動ガベージコレクションメカニズムを持つ言語では、ノードPが収集されるかどうかは、それを指す参照がまだあるかどうかに依存し、P.nextの値には依存しません。CやC++などの言語では、ノードのメモリを手動で解放する必要があります。
Q：連結リストでは、挿入と削除操作の時間計算量はO(1)です。しかし、挿入や削除前の要素検索にはO(n)時間がかかるので、なぜ時間計算量はO(n)ではないのですか？
要素を最初に検索してから削除する場合、時間計算量は確かにO(n)です。しかし、連結リストの挿入と削除におけるO(1)の利点は他のアプリケーションで実現できます。例えば、連結リストを使用した両端キューの実装では、常にヘッドとテールノードを指すポインタを維持し、各挿入と削除操作をO(1)にします。
Q：「連結リストの定義と格納方法」の図で、薄青色の格納ノードは単一のメモリアドレスを占有しますか、それともノード値と半分を共有しますか？
図は単なる定性的な表現であり、定量的分析は特定の状況に依存します。
- 異なる型のノード値は異なる量の空間を占有します。例えば、int、long、double、オブジェクトインスタンスです。
- ポインタ変数によって占有されるメモリ空間は、使用されるオペレーティングシステムとコンパイル環境に依存し、通常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] * self.size()を初期化すると、resの各要素は同じアドレスを参照しますか？
いいえ。しかし、この問題は二次元配列で発生します。例えば、二次元リストres = [[0]] * self.size()を初期化すると、同じリスト[0]を複数回参照することになります。
Q：ノードを削除する際、その後続ノードへの参照を断つ必要がありますか？
データ構造とアルゴリズム（問題解決）の観点から、プログラムのロジックが正しい限り、リンクを断たなくても問題ありません。標準ライブラリの観点から、リンクを断つ方が安全で論理的に明確です。リンクを断たず、削除されたノードが適切にリサイクルされない場合、後続ノードのメモリのリサイクルに影響を与える可能性があります。