リスト構造とは

リスト構造の基本

データ構造のうち、最も基本的なものが、リストです。リストとは、配列のようなもので、なかに複数のデータを入れることができます(図1-1.参照)。それぞれのものを、要素と呼びます。要素は順番に並べられ、順序付けには連続した整数値の順序番号(インデックス)が用いられます。個々の要素へアクセスするにはその順序番号を指定します。

図1-1.リスト構造
リスト構造

連結リスト

連結リストとは

リスト構造のうち、特に要素一つ一つがリンクによって接続されているものを、連結リストと言います。通常のリストが、配列のように順序番号(インデックス)で要素にアクセスするのに対し、リンクをたどってシーケンシャルにアクセスするために用いるのが、連結リストの特徴です。連結リストには、単方向リスト循環リスト双方向リストの三種類があります。以下、それぞれの特徴について説明していきましょう。

単方向リスト

連結リストの中で最も基本となるのがこの単方向リストです。各要素は次の要素へのただ一つのリンクを持ちます。最後の要素のリンクには null を用いて終端をあらわします。

図1-2.単方向リスト
単方向リスト

循環リスト

単方向リストの最後の要素が、先頭の要素にリンクして、あたかも循環しているようになったのが、循環リストです。リンクをたどって終端まで来ると、再び先頭に戻ります。

図1-3.循環リスト
循環リスト

双方向リスト

単方向リストが、次の要素へ一方向のリンクを持っているのに対し、双方向リストは、各要素が前後の要素と互いにリンクを持っています。先頭と終端をつなぎ合わせて、双方向の循環リストを作り出すことも可能です。

図1-5双方向リスト
双方向リスト

連想記憶とは

連想記憶の用途

リスト構造は、数値による番号付や、要素同士に関連性があるものを扱う場合には、最適なデータ構造です。それに対し、連想記憶とは、関連する要素どうしを結びつけて、検索を早く行えるようにするデータ構造です。

具体的な例を上げると、「春」「夏」「秋」「冬」という単語と、英語の「Spring」「Summer」「Autumn」「Winter」という単語を結びつけたいとします。この時、「春」と、「Spring」、「夏」と「Summer」といったように、数値で分類されているわけではないけれど、直接関連付けたいようなデータがある場合には、この方法が有効です。前述の例で言えば、「春」や「夏」がキーに、「Spring」や「Summer」が値になります。もちろん、逆も可能です。

これらの概念は、様々なプログラミング言語で利用可能です。例えば、C++言語、Java言語では、Map(マップ)、Python言語では辞書と呼ばれています。

なお、連想記憶を実装する方法には、連想配列以外にも、バイナリツリー(バイナリツリー)といった方法も存在します。

ハッシュテーブル

このように、関連性のある要素どうしを結びつけて記憶することを、連想記憶と言います。その際、標識となる要素のことを、キー(key)、対応する要素のことを値(value)と言います。連想記憶は、このハッシュテーブルを用いて実現されます。(図1-5.参照)

図1-5.ハッシュテーブル
ハッシュテーブル