リンクデータ構造

リンクリストは、メモリ内の物理的な配置ではなく、構造体自体にデータの一部として格納される論理的なリンクによって順序付けられた構造体の集合です。隣接するメモリ位置に格納される必要はありません。すべての構造体には、データフィールドとアドレスフィールドがあります。アドレスフィールドには、後続の要素のアドレスが格納されます。

連結リストは、単方向連結、双方向連結、多重連結のいずれかであり、線形または循環のいずれかになります。

基本特性

• ノードと呼ばれるオブジェクトは、線形の順序でリンクされている。
• リストの最初のノードへの参照は常に保持されます。これは「ヘッド」または「フロント」と呼ばれます。^{[ 3 ]}

3つのノードを持つ連結リストは、それぞれ2つのフィールド（整数値と次のノードへのリンク）を含みます。

struct LinkedList { T value ; // 格納された値LinkedList next ; // 次のノードへの参照 (最後のノードの場合は null) }

探索木とは、ノードに何らかの順序付けられた集合からデータ値を格納できる木構造のデータ構造であり、木を順方向に走査する際に、格納された値の昇順でノードが訪問される。

基本特性

• ノードと呼ばれるオブジェクトは、順序付けられた集合に格納される。
• 順序通りの走査では、ツリー内のデータが昇順で読み出されます。

配列と比較して、リンクデータ構造はデータの整理とメモリ割り当てにおいてより高い柔軟性を提供します。配列では、配列のサイズを最初に正確に指定する必要があり、これはメモリの無駄遣いにつながる可能性があり、また、後々の機能に何らかの形で支障をきたすような恣意的な制限となる可能性もあります。リンクデータ構造は動的に構築されるため、プログラムが必要とするサイズを超えることはありません。また、作成時にどれだけのメモリ領域を割り当てるべきかを推測する必要もありません。これは、メモリの無駄遣いを避ける上で重要な特徴です。

配列では、配列要素はメモリ上の連続した（連結された）領域に配置される必要があります。しかし、リンクデータ構造では、各ノードへの参照によって、次のノードを見つけるために必要な情報が得られます。また、リンクデータ構造のノードは、配列とは異なり、物理メモリ内の異なる場所に個別に移動しても、ノード間の論理的な接続は維持されます。さらに、適切な注意を払えば、他のプロセスやスレッドがデータ構造の別の部分を操作している最中でも、特定のプロセスやスレッドがデータ構造の一部にノードを追加したり削除したりすることができます。

一方、リンクデータ構造では、特定のノードにアクセスするには、各ノードに格納されている参照の連鎖をたどる必要があります。構造にn 個のノードがあり、各ノードに最大でb 個のリンクが含まれている場合、log _b nステップ未満では到達できないノードがいくつか存在し、これらのノードへのアクセス処理が遅くなります。これは、特にノード数が多い構造の場合、かなりの速度低下につながることがあります。多くの構造では、最悪の場合、一部のノードへのアクセスにn − 1 ステップかかる可能性があります。これに対し、多くの配列データ構造では、エントリ数に関係なく、一定回数の操作で任意の要素にアクセスできます。

概して、これらの連結データ構造は動的データ構造によって実装されます。これにより、特定の領域を再利用することが可能になります。これらのデータ構造を使用することで、メモリをより効率的に利用できます。メモリは必要に応じて割り当てられ、不要になった時点で解放されます。

リンクされたデータ構造は、（ノードが個別に割り当てられる場合）相当なメモリ割り当てオーバーヘッドが発生する可能性があり、（一般的に参照の局所性が低いため）メモリページングやプロセッサのキャッシュアルゴリズムを阻害する可能性があります。場合によっては、リンクされたデータ構造は、競合する配列構造よりも多くのメモリ（リンクフィールド用）を使用することもあります。これは、リンクされたデータ構造が連続していないためです。配列とは異なり、データのインスタンスはメモリ全体に分散している可能性があります。

配列ではn番目の要素にすぐにアクセスできますが、リンクデータ構造では複数のポインタをたどる必要があるため、要素へのアクセス時間は構造内の要素の位置によって異なります。

ポインタマシンなど、連結構造の制約を強制する一部の理論的計算モデルでは、多くの問題が制約のないランダムアクセスマシンモデルよりも多くのステップを必要とする。