リンクされたリストについて詳しく解説

導入

リンクリストは、コンピュータサイエンスにおいて、同じタイプの要素の任意のサイズの順序付けされたコレクションを表すデータ構造を指定します。

リストの要素へのアクセスは順番に行われます。各要素は次の要素へのアクセスを許可します (アクセスが絶対的に行われるテーブルの場合とは異なり、テーブルの各セルの直接アドレス指定によって)。

リンクされたリストの原理は、各要素がdataに加えて、リスト内で論理的に隣接する要素へのポインタを持つことです。したがって、任意の時点での要素の挿入と削除が単純なアクセスよりも比較的頻繁に行われる場合は、処理速度の理由からリストの使用をお勧めします。

実際、挿入または削除は最大 2 回の書き込みアクセスのみを必要とするため、一定時間内に実行されます。一方、ランダムに配置された要素にアクセスするには、選択した要素からインデックスを分離する各要素をトラバースする必要があります。したがって、要素に順番にアクセスする方が良いでしょう。

リンクリストにはいくつかの種類があり、主に次の 2 つの属性によって特徴付けられます。

単純にリンクされたリスト。それぞれ値 12、99、および 37 を持つ 3 つの要素で構成されます。

反対側の図にあるように、リンクリストの各要素は 2 つの情報で構成されています。

リストの 1 つの要素のみがポイントされるため、アクセスは一方向のみになります。

単純リンクリストとの違いは、今回は前の (または先行する) 要素へのポインターが追加されることです。したがって、アクセスは両方向、つまり後続者から後続者へ、または先行者から先行者へ行うことができます。

この構造は、メモリ(リストの要素ごとに 1 つのポインタ) と更新のための命令の数においてより高価です。単純にリンクされたリストの場合と比較して、挿入にはポインタのコピーが 4 つかかります。

一方、これにより、隣接する要素へのポインタを持たなくても、要素の前後に挿入できます。単純リンクリストでは、後続として、または (排他的に) 要素に対して相対的な 1 つの位置にのみ挿入できます。前任者として。

二重結合をチェックすることで、二重リンクリストの整合性をチェックすることもできます。

サイクルは、リンクされたリストがループ (または閉じたチェーン) を形成する際に示す特性です。チェーンの開始またはチェーンの終了という概念が消えます。

循環 (または循環) リストは、最後の要素が最初の要素への参照を持つ場合に作成されます (リストが二重リンクされている場合、最初の要素も最後の要素への参照を持ちます)。

このタイプのリストを使用する場合は、要素の検索が失敗した場合など、未定義の走査を避けるための予防措置が必要です。