基本情報技術者試験対策（38）「基本的なデータ構造」

リスト
リストの長所
リストの短所
リストの種類
二分探索木
ヒーブ
キューとスタック

リスト (list)は、配列の1つの要素に、データの値と、次にどの要素とつながっているか、という二つの情報を持たせたものである。このつながりの情報をポインタ (pointer) と呼ぶ。「次のデータはここです」とポイントしている(指している) からである。

リストの例を示す【下図】。リストを構築するには、リストの本体となる配列と、リストの先頭の要素を指す変数が必要である (末尾の要素を指す変数を用意することもある)。ここでは、配列 A[0] ～A[4]がリストの本体で、変数Topがリストの先頭の要素を指している。

変数Top の値は3なので、先頭はA[3]である。配列の1つの要素には、適当な文字列のデータと、ポインタ (次の要素の番号) が入っている。リストの末尾では、ポインタをー1とすることで、次の要素がないことを示している。ー1は、要素番号としてあり得ない数字だからである。

リストの長所

リストの特徴は、データの物理的な並び順とは無関係に、ポインタで要素をたどることである。例えば、先ほどの図に示したリストは、物理的には A[0]→A[1]→A[2]→A[3] →A[4] という順序でメモリ内に並んでいるが、ポインタで要素をたどるのでTop→A[3]→A[0]→A[2]→A[4] →A[1] という順序になる。このような特徴から、リストには、通常の配列と比べて、要素の挿入と削除が効率的に行えるという長所がある【下図】。

例えば、100個の要素がある通常の配列とリストで、先頭から50番目と51番目の要素の間に新たな要素を挿入するとしよう。通常の配列の場合は、51番目以降の50個の要素を1つずつ後ろにずらして格納位置を空けてから (①)、新たな要素を挿入することになる (②)。 50個の要素をずらすには、多くの時間がかかる。

それに対して、リストの場合は、リストの末尾の101番目に新たな要素を追加し(①)、50番目の要素のポインタを101番目の要素にコピーしてから（②）50番目のポインタを101番目の要素番号にすれば (③)、挿入が完了する。ほとんど時間がかからない。

リストへの要素の挿入は、物理的には配列の末尾に追加されているが、ポインタをたどると、途中に挿入されていることになる。

同様の仕組みで、リストから要素を削除する処理も、削除する要素のポインタを1つ前の要素にコピーするだけで済み、効率的に実現できる【下図】。例えば、”XX”→ “YY’’→”ZZ” とつながっているリストで、 “YY” のポインタを1つ前の”XX” にコピーすると、 “XX” → “ZZ” というリストになり、 “YY”が削除される。 “YY” は、物理的にはメモリ上に残っているが、リストからは削除されている。

リストの短所

リストには、通常の配列と比べて、短所もある。それは、「先頭から80番目の要素を読み出す」や「先頭から80番目の要素を更新する」のように、任意の番号を指定して要素を読み書きするときに、処理が遅いことである。
通常の配列であれば、要素番号を指定して、すぐに80番目の要素を読み書きできる。それに対して、リストでは、先頭から順番に80個の要素をたどってから、80番目の要素を読み書きすることになる。

リストの種類

リストの種類には、前から後ろだけにたどれる単方向リスト、前から後ろだけでなく、後ろから前にもたどれる双方向リスト、および末尾と先頭の要素がつながっている環状リストがある【下図】。これまでの例で示したリストは、どれも単方向リストである。

二分探索木

リストの1つの要素に2つのポインタを持たせ、 1つの要素から2つの要素にたどれるようにしたデータ構造を二分木 (binary tree) と呼ぶ。このような形式で要素をつないでいくと、木のような形状 (木を上下逆にした形状)になるからである。試験問題で取り上げられる二分木の種類には、データを探索するための「二分探索木」と、データを整列するための「ヒープ」がある。
はじめに、二分探索木の仕組みを説明しよう。二分探索木は、要素の左側により小さい値をつなぎ、右側により大きい値をつないだ二分木である。データを1つずつ追加することで、だんだん木が伸びていく。下の例題は、与えられたデータを使って二分探索木を構築する問題である。木では、四角形ではなく円で要素を示すことが慣例になっている。要素と要のつながりは、円をつなぐ線で示す。

（例題）与えられたデータで二分探索木を構築する (H23 特別問5)

8、12、5、3、10、7、 6というデータを順番につないで、紙の上に二分探索木の絵を描いてみよう。最初の8は、木の先頭の要素になり、これを根と呼ぶ。これ以降のデータは、根を起点として、木の先の適切な位置につないでいく。手順を下図に示す。

正解は、手順7と同じ絵になっている選択肢エである。木では、データとデータをつなぐ線を枝と呼ぶ。根以外のデータは、そこから枝が伸びているものを節と呼び、枝が伸びていない先端のものを葉と呼ぶ。これらの呼び名は、自然界の木と同様である。

二分探索木を使ってデータを探索するときには、根からスタートして、目的のデータの大小で、左または右に枝をたどっていく。例えば、二分探索木で6を探索する場合は、下図のように木の枝をたどっていき4回の処理で見つかる。二分探索木を使えば、二分探索法と同様に、効率的にデータを見つけられる。

ヒーブ

ヒープ (heap)は、直訳すると「堆積物」という意味である。ヒープは、1つの要素が2つの要素につながった二分木の一種なのだが、データの配置方法が、木よりも堆積物に似ている。堆積物のように、大きなデータの上に小さなデータが積み上がったデータ構造である (目的によっては、小さなデータの上に大きなデータが積み上がったデータ構造にする場合もある)。

ヒープの例を示す【下図】。
破線の三角形で囲んだ3つの要素の中で、上にある要素が下にある要素より小さくなるように配置する。下にある要素の左右は関係なく、下の2つより上の1つが小さければよいのである。

ヒープソート

ヒープを使うと、データをソートできる。下の要素より上の要素が小さいので、ヒープの根には、全体で最も小さいデータがある。これを取り出してから、残ったデータをヒープに再構築する。今度は、ヒープの根には、2番目に小さいデータがある。これを取り出して、先ほど取り出し最も小さいデータの後ろに並べる。以下同様に、ヒープの再構築と、根のデータを取り出して、後ろに並べることを繰り返せば、データを昇順(小さい順) にソートできる。このアルゴリズムをヒープソートと呼ぶ。

キューとスタック

すぐに処理しないデータを一時的に格納しておくための配列をバッファ(buffer = 緩衝材、緩衝記憶領域) と呼ぶ。バッファの種類には、「キュー」と「スタック」がある。キューとスタックは、データの格納と取り出しのルールが違う。

キュー

キューは、FIFO (First In First Out) 形式のバッファである。キューに最初に格納したデータが (first in)、最初に取り出される (first out)。キューにデータを格納することをエンキュー (enqueue)、キューからデータを取り出すことをデキュー (dequeue)と呼ぶ。

キューは、順番通りに処理するための普通のバッファである。例えば、A、B、Cの順にエンキューされたデータは、そのままA、B、Cの順にデキューされる。この様子が、順番を待っている行列に似ているので、キュー (queue =待ち行列)と呼ぶ【下図】。