配列とリンクリスト

配列は、要素の集まりを保存するための最も一般的なデータ構造です。ほとんどのプログラミング言語には、配列を簡単に宣言し、その中の要素にアクセスするためのメソッドが用意されています。リンクテーブル、より具体的には単一リンクテーブルも、要素の集まりを格納するために使用できるデータ構造である。一連のノードからなり、各ノードは次のノードへの参照を持っている。

図1は、配列の宣言と値の代入によく使われるコードの一部です。図2は、メモリ上の配列の様子を示しています。

上のコードでは，5個の整数を格納できる配列を定義し，インデックス0から4でアクセスできるようにしています．配列の重要な特性は、配列全体がメモリのブロックとして割り当てられ、各要素は配列内の独自のスペースを持つことです。配列は一度定義すると、そのサイズは固定されます。したがって、コンパイル時に配列の大きさが決まらない場合は、安全な大きさの配列を定義する必要があります。しかし、多くの場合、実際に使用する要素の数は、割り当てた数よりも少ないのです。そのため、実際にはかなりの量のメモリが無駄になっています。一方、「十分な大きさの配列」が実際には十分な大きさでない場合、プログラムはクラッシュします。

リンクリストは、その要素にそれぞれ個別のメモリブロックを割り当て、これらの要素をチェーンのリンクとして連結することで全体の構造が得られます。図3の各フィールドには、2つのリンクリストの要素がある。dataフィールドは実際に格納されているデータを保持し、nextフィールドはチェーンの次の要素への参照を保持する。リンクリストの先頭の要素がリンクリストのヘッドとして格納される。

図3：リンクテーブルの構成要素

図4は、3つの要素を含むリンクテーブルを描いたものである。各要素にはそのデータが格納され、最後の要素を除くすべての要素には次の要素への参照が格納されます。最後の要素の次のフィールドにヌル値が含まれている。リストのどの要素にもアクセスするには、先頭から始めて必要な要素が満たされるまで次のポインタを追いかけます。