単方向リストとは
単方向リストとは、各要素が次の要素への参照だけを持つ構造で、配列の添字とは別に参照をたどります。
配列の添字順と、データを読む順番は同じとは限りません。単方向リストは、現在の要素が持つ「次の要素への参照」を頼りに進む構造です。
基本の仕組み
1始まりの例で、data[1]=A、data[2]=B、data[3]=C、next[1]=3、next[3]=2、next[2]=null、先頭が1なら、読む順はA→C→Bです。添字を1ずつ増やすのではなく、1→3→2とnextをたどります。
現在位置pのデータを読み、その後でp=next[p]へ更新します。pが終了を表す値になれば止めます。終了値が未定義（null）か0か、添字が0始まりか1始まりかは設問の定義に従い、終了値を配列の添字として参照しないようにします。
途中へ要素を挿入するときは参照の付け替えが必要です。ただし、走査の問題では挿入処理を勝手に追加しません。各反復の「更新前のp」「読んだdata[p]」「次のp」を表にすると、データ値と添字を混同しにくくなります。
配列によるリスト表現
配列で単方向リストを表すときは、各要素の値だけでなく次要素の添字を保持します。先頭添字からnextをたどり、終端値で止めます。挿入では新要素のnextを旧後続へ設定してから、直前要素のnextを新要素へ変えます。
| 操作 | 更新する参照 |
|---|---|
| 走査 | 現在位置から次位置へ |
| 途中挿入 | 新要素と直前要素のnext |
| 削除 | 直前要素のnext |
試験に出る
- 配列の添字順ではなくnextをたどる読み順。
- data[p]を読んでからp=next[p]へ更新する順序。
- 終了値を配列の添字として参照しないこと。
- 0始まりか1始まりかを設問の定義で確認すること。
- データ値と添字、更新前と更新後のpを混同しないこと。
重要な言葉
- 単方向リスト
- 各要素が次の要素への参照だけを持つ構造。
- 添字
- 配列の要素を指定する番号。
- 終了値
- 走査の終わりを表す値。nullや0など設問の定義による。
- 走査
- 要素を順にたどって調べること。
確認問題
確かめようこの例でAを読んだ次にdata[2]を読む？
いいえ。next[1]=3なので、次はdata[3]のCです。
単方向リストは、配列の添字を1ずつ増やして読む。
終了を表す値を、配列の添字として参照してよい。
data[1]=A、next[1]=3のとき、Aの次に読むのは？
単方向リストの走査でpを更新する正しい順序は？
配列の添字順と、データを読む順番は同じとは限りません。は、現在の要素が持つ「次の要素への」を頼りに進む構造です。
1始まりの例で、data[1]=A、data[2]=B、data[3]=C、[1]=3、next[3]=2、next[2]=null、先頭が1なら、読む順はです。添字を1ずつ増やすのではなく、1→3→2とnextをたどります。
のデータを読み、その後でp=next[p]へ更新します。pが終了を表す値になれば止めます。終了値が未定義（null）か0か、添字が0始まりか1始まりかは設問の定義に従い、を配列の添字として参照しないようにします。
途中へ要素を挿入するときはが必要です。ただし、走査の問題では挿入処理を勝手に追加しません。各反復の「」「読んだdata[p]」「次のp」を表にすると、データ値と添字を混同しにくくなります。
出典・参考資料
試験の公式案内と、この記事の参考にした学習資料です。
編集：Pinternet Works · 更新日：
教材の編集方針・訂正について