リスト・木・ハッシュ表の操作

リストは要素を順番に並べたデータ構造であり、配列で実現する方法とポインタで実現する方法がある。木構造は親子関係で要素を階層的に持つ構造であり、ハッシュ表はキーの値から格納場所を計算して、データを速く探す仕組みである。これらは追加、削除、探索の速さがそれぞれ異なるため、扱うデータの量と操作の種類に応じて選ぶ必要がある。

リストの実現方式と操作

配列で実現したリストは、要素を連続した領域に格納するため、添字によって任意の要素を直接参照できる。一方で、リストに入れられる最大個数に応じた領域をあらかじめ確保するので、実際の要素数が少ないと使われない領域が生じる。 挿入や削除では後ろの要素を移動する必要があり、位置によっては時間がかかる。 ポインタで実現したリストは、各要素が次の要素を指すポインタを持つ。 挿入位置の要素を指すポインタが分かっていれば、新しい要素を確保してポインタを付け替えるだけで追加でき、要素数や位置によらず必要な操作は一定である。ただし、任意の位置へは先頭から順にたどる必要があり、添字による直接参照はできない。 双方向リストは、各要素が次と前の両方の要素を指す形である。配列で三つの配列 elem、next、prev を使って表す場合、新しい要素は配列の末尾に追加し、挿入位置の前後の要素の next と prev を書き換える。 先頭と末尾の要素番号を表す Head と Tail も、挿入によって変わる場合があるので併せて更新する必要がある。

単方向リストの末尾操作とポインタのたどり回数

単方向の線形リストでは、先頭からのポインタだけで要素をたどる。先頭への追加や末尾への追加は、先頭ポインタや末尾ポインタから直接参照して行える。これに対して末尾のデータを削除するには、その一つ前のデータを新しい末尾にする必要がある。 単方向リストでは末尾から前をたどれないため、先頭から各ポインタをたどって末尾の一つ前を探すことになり、ポインタをたどる回数が最も多くなる。