単方向リストの勉強(基本情報 平成24年春期 午前問7)

はじめに

データ構造とアルゴリズムについて,再度勉強中です.
配列やFIFO, LIFOについては実際のプログラミング時にもよく利用する一方,リスト構造についてはなかなか使う機会がなく,忘れがちだったのでこの機会にまとめておきます.

単方向リスト構造について

単方向リストとは,データ部ポインタ部を持つセルのリンク配置によって構成されるデータ構造の1つです.
つまり,複数のセルをポインタによって数珠つなぎのような形にすることで,データをまとめて扱うことを可能にしたデータ構造です.
慣例的に,先頭セルを指すポインタを head末尾セルを指すポインタを tailと呼びます.

配列では,データを扱う際に添え字を利用してA[2]のようにデータにアクセスするといった「ランダムアクセス」が可能でした.
一方で,単方向リストでは, head及び tailのポインタから目的のデータまで順番にセルを辿ることで,データを扱います.

図で表すと,以下のようにになります.

f:id:Szarny:20171012222925p:plain:w700

なお, Data_nのセルに,後続セルへのポインタが設定されていないのは,それが最後のセルだからです.
プログラムで実装する際には,Nullに設定するのが一般的です.

単方向リスト構造におけるデータ操作

ここからは,基本情報で出題された問題を基に,単方向リスト構造におけるデータ操作の手順について確認していきます.

基本情報 平成24年春期 午前問7

多数のデータが単方向リスト構造で格納されている。このリスト構造には,先頭ポインタとは別に,末尾のデータを指し示す末尾ポインタがある。次の操作のうち,ポインタを参照する回数が最も多いものはどれか。

ア リストの先頭にデータを挿入する。
イ リストの先頭のデータを削除する。
ウ リストの末尾にデータを挿入する。
エ リストの末尾のデータを削除する。

リストの先頭にデータを挿入する

元々のリストと,やりたいことを図で示すと,以下のようになります.
f:id:Szarny:20171012222925p:plain:w700
f:id:Szarny:20171012224135p:plain:w700

  1. 新しいセルを作成する
  2. 新しいセルが Data_1のセルを指すようにする
  3.  headが新しいセルを指すようにする

以上の処理は, headのポインタにアクセスできれば可能です.
なぜなら,新しいセルのポインタに設定するアドレス( Data_1のアドレス)は, headに設定されていたポインタのアドレスだからです.
つまり,参照が必要なのは headだけです.

なお,2と3を入れ替えると, headが先に更新されてしまいます.そのため, Data_1のセルのアドレスが分からなくなり,設定に失敗します.

リストの先頭のデータを削除する

元々のリストと,やりたいことを図で示すと,以下のようになります.
f:id:Szarny:20171012222925p:plain:w700
f:id:Szarny:20171012224932p:plain:w700

  1.  head Data_2のセルを指すようにする

以上の処理は, head Data_1のセルにアクセスできれば可能です.
 Data_2のセルのアドレスは, Data_1のセルのポインタに設定されています.つまり, Data_1のセルにアクセスできれば必要な情報は全て揃います.
つまり,参照が必要なのは head Data_1のセルです.

リストの末尾にデータを挿入する

元々のリストと,やりたいことを図で示すと,以下のようになります.
f:id:Szarny:20171012222925p:plain:w700
f:id:Szarny:20171012230023p:plain:w700

  1. 新しいセルを作成する
  2.  Data_nのセルが新しいセルを指すようにする
  3.  tailが新しいセルを指すようにする

以上の処理は, tail Data_nのセルにアクセスできれば可能です.
新しいセルのアドレスは既知ですが, Data_nのポインタに新しいセルのアドレスを設定するには, Data_nまで到達する必要があります.
 Data_nへは tailを辿ればすぐに到達できるので,そこで設定を行い,後は tailに新しいセルのアドレスを設定すれば完了です.

なお,2と3を入れ替えると, tailが先に更新されてしまいます.そのため, Data_nのセルのアドレスを知るためには,わざわざ headから Data_nまで辿る必要が生じます.

リストの末尾のデータを削除する

元々のリストと,やりたいことを図で示すと,以下のようになります.
f:id:Szarny:20171012222925p:plain:w700
f:id:Szarny:20171012230556p:plain:w700

  1.  Data_{n-1}のアドレスを tailのポインタに設定する
  2.  Data_{n-1}のポインタをNullに設定する

この2つの処理を行うには, Data_{n-1}にアクセスする必要があります.
なぜなら, Data_{n-1}のセルのアドレスを知ることと,そのポインタを更新することの両方が必要だからです.
しかし, Data_{n-1}にアクセスするには, headから順番に辿るしか方法がありません.
つまり,データ数 nに応じた回数分,リンクをたどる必要が生じるということです.

問題のまとめ

操作に応じたリンクの参照内容をまとめると,以下のようになります.

操作 参照先
リストの先頭にデータを挿入する  head
リストの先頭のデータを削除する  head,  Data_1
リストの末尾にデータを挿入する  tail,  Data_{n}
リストの末尾のデータを削除する  head,  Data_1,  Data_2, ...,  Data_{n-2},  Data_{n-1}

以上より,最も参照回数が多くなるのは

「エ リストの末尾のデータを削除する」

です.

おわりに

単方向リスト構造について,基本情報の過去問を用いてまとめました.
いずれ言語を使った実装も行ってみようと考えています.