データ構造の基本

要点と定義

データ構造は、データをどのように並べて保持し、どのような手順で取り出したり追加・削除したりするかを定める仕組みです。目的に合う構造を選ぶと、必要な操作を行いやすくなります。

配列は、要素を位置（添字）で管理する構造です。位置を指定すれば任意の要素を直接参照できます。一方、途中や先頭への挿入・削除では、並びを保つために他の要素を移動させる場合があります。配列で実現したリストの特徴を判断する問題では、この「位置による直接参照」と「挿入時に要素をずらす場合があること」の区別が必要です。

リストは、要素を順につないで扱う構造です。ポインタを使うリストでは、各要素が次の要素を指します。先頭からポインタをたどって任意の位置を探すため、位置が分からない要素の参照には先頭からの探索が必要です。既存要素の間に挿入するときは、前の要素が新要素を指し、新要素が元の次要素を指すようにつなぎ替えます。例えば A→B の間に X を挿入するなら、A→X→B とします。配列のように間の要素を順にずらす必要はありません。配列上の番号と、リストをたどったときの順番は別物です。

スタックは、最後に入れたデータを先に取り出す構造です。後入れ先出しとも呼びます。追加をプッシュ、取り出しをポップといい、どちらも一番上の要素に対して行います。したがって、途中の要素だけを直接取り出すことはできません。操作列を追うときは、上に積まれたデータから順に書くと状態を確認しやすくなります。

待ち行列（キュー）は、先に入れたデータを先に取り出す構造です。先入れ先出しとも呼びます。追加は末尾、取り出しは先頭から行います。追加と取り出しを順番に適用すれば、次に取り出されるデータを特定できます。後から追加したデータが、先に入ってまだ残っているデータを追い越すことはありません。

適用条件と例

配列とポインタを使うリストは、操作の得意不得意を比べて選びます。位置を指定して何度も参照するなら、配列の直接アクセスが便利です。要素間への挿入や削除が多く、対象位置の要素まで既にたどり着いているなら、ポインタのつなぎ替えで対応できます。ただし、ポインタ方式でも対象位置を探す時間は必要です。挿入自体が常に高速とは限らず、先頭からの探索が必要な場合はその分の手間がかかります。

配列で先頭に X を挿入する例では、A、B、C が並んでいるとき、並びを保つには A、B、C を後ろへ移動して X、A、B、C とする必要があります。末尾への追加なら、空き領域があるなどの条件では既存要素の移動を避けられます。容量や実装方法によって処理は異なるため、配列ならどの挿入も同じ手間だとは限りません。