Linked data structure とは

コンピュータサイエンスでは、リンクされたデータ構造は、リンクされ、参照(リンクまたはポインタ)によって編成された一連のデータレコード(ノード)で構成されるデータ構造です。データ間のリンクは、コネクタとも呼ばれます。
リンクされたデータ構造では、リンクは通常、逆参照または同等性の比較のみが可能な特殊なデータ型として扱われます。したがって、リンクされたデータ構造は、ポインタに関する算術演算の実行を必要とする配列および他のデータ構造と対比される。この区別は、ノードが実際には単一の配列の要素として実装されていても参照が実際には配列インデックスである場合でも保持されます。これらのインデックスで算術演算が行われない限り、データ構造は基本的にリンクされたものです。
ダイナミックアロケーションを使用し、配列インデックスリンクを使用するという2つの方法でリンクを行うことができます。
リンクされたデータ構造には、リンクされたリスト、検索ツリー、エクスプレッションツリー、および他の多くの広く使用されるデータ構造が含まれます。また、トポロジカルなソートやセット・ユニオン・ファインドなど、多くの効率的なアルゴリズムのキーとなるビルディング・ブロックです。