4.6 演習¶

4.6.1 確認問題¶

配列と単方向連結リストに、どちらも [A, B, C, D, E] が順に保存されています。ここで 4 番目の要素 D を読み取ります。

配列では、どのインデックスを直接使えますか？
単方向連結リストでは、先頭ノード A から始めて、next をたどりながらどのノードを通りますか？
読み取る位置が後ろになるほど、2 つの構造で必要な手順はどのように変わりますか？位置を指定した読み取りを繰り返すには、どちらが適していますか？その理由も説明してください。

解答

インデックスが 0 から始まる場合、4 番目の要素のインデックスは 3 なので、配列では arr[3] を直接読み取れます。
単方向連結リストでは、必ず先頭から始めます。アクセスする経路は A → B → C → D で、next を 3 回たどります。
配列は先頭アドレスとインデックスから要素の位置を直接求められるため、位置を指定したアクセスの時間計算量は \(O(1)\) です。単方向連結リストで \(k\) 番目のノードにアクセスするには、先頭ノードから next を \(k-1\) 回たどる必要があり、最悪の場合は \(O(n)\) の時間がかかります。

ここでは位置を指定した読み取りだけを比較しており、連結リストがすべての操作で遅いという意味ではありません。

配列と単方向連結リストに、どちらも A、B、C、D が保存されています。ここで B の後ろに X を挿入します。

解答

配列では、まず D を 1 つ右へ移動し、次に C を 1 つ右へ移動します。最後に X をインデックス 2 に置くと、 [A, B, X, C, D] になります。
B.next はもともと C を指しています。まず X.next = B.next として X が C を指すようにし、次に B.next = X とします。その結果、A → B → X → C → D となります。元の接続を保存せずに先に B.next を上書きすると、C を見つけられなくなる可能性があります。
B の位置が分かっていれば、連結リストへの挿入は 2 つの接続を変更するだけなので、\(O(1)\) の時間で行えます。先頭から B を探す必要もある場合、その探索自体に \(O(n)\) の時間がかかる可能性があります。

配列を基に実装されたリストの現在の内容が [A, B, C]、長さが size = 3、容量が capacity = 4 であるとします。容量が足りないときは、新しい配列の容量を元の 2 倍にするものとします。

解答

D は最後の空き位置に置けます。このとき内容は [A, B, C, D]、 size = 4、capacity = 4 となり、容量を増やす必要はありません。
さらに E を追加するときは空き位置がないため、容量 8 の新しい配列を作り、既存の要素 A、B、C、D の 4 つをコピーしてから E を追加します。このとき size = 5、capacity = 8 です。
元の配列そのものが長くなったわけではありません。リストはより大きな新しい配列を作って既存の要素をコピーし、内部の保存先を新しい配列に切り替えます。そのため、利用者から見ると容量が増えたように見えます。

配列 digits には、0 以上の整数の各桁が左から右へ保存されています。たとえば、[3, 0, 8] は 308 を表します。数値 0 は [0] で表し、それ以外の入力の先頭の桁は 0 ではありません。

十進数の筆算と同じように、この整数に 1 を足し、結果を同じ配列形式で返してください。 digits は直接変更してかまいません。先頭に新しい繰り上がりが生じた場合は、より長い配列を返せます。

解法のヒント

単方向連結リストの先頭ノード head が与えられます。各ノードには、値と次のノードを指す next が含まれています。

反復を使ってすべてのノード間の接続を反転し、反転後の先頭ノードを返してください。新しい連結リストノードを作ってはいけません。

解法のヒント