リンクリストとは

リンク リストは、物理ストレージ ユニット上の非連続かつ非順次のストレージ構造です。データ要素の論理的順序は、リンク リスト内のポインタのリンク順序によって実現されます。 。リンク リストは一連のノードで構成され (リンク リストの各要素はノードと呼ばれます)、ノードは実行時に動的に生成できます。各ノードは 2 つの部分で構成されます。1 つはデータ要素を格納するデータ フィールドで、もう 1 つは次のノードのアドレスを格納するポインタ フィールドです。線形テーブルシーケンス構造と比較すると、演算が複雑になります。順序どおりに格納する必要がないため、リンク リストは挿入時に O(1) の複雑さを実現できます。これは、別の線形リストや逐次リストよりもはるかに高速ですが、ノードの検索や特定の番号付きノードへのアクセスには O(n ) 時間、線形テーブルと逐次テーブルの対応する時間計算量はそれぞれ O(logn) と O(1) です。

リンク リスト構造を使用すると、データ サイズを事前に知る必要があるという配列リンク リストの欠点を克服でき、コンピュータのメモリ空間を最大限に活用し、柔軟な動的メモリ管理を実現できます。 。しかし、リンクリストは配列のランダム読み取りの利点を失い、同時にノードのポインタフィールドの増加によりリンクリストのスペースオーバーヘッドが比較的大きくなります。リンク リストの最も明白な利点は、通常の配列で関連する項目を配置する方法が、これらのデータ項目がメモリまたはディスク上で配置される順序とは異なる場合があり、データへのアクセスでは、多くの場合、異なる配置間の切り替えが必要になることです。リンク リストでは、リスト上の任意の場所でノードの挿入と削除が可能ですが、ランダム アクセスは許可されません。リンク リストには、一方向リンク リスト、二重リンク リスト、循環リンク リストなど、さまざまな種類があります。リンク リストは、さまざまなプログラミング言語で実装できます。 Lisp や Scheme などの言語の組み込みデータ型には、リンク リストへのアクセスと操作が含まれます。 C、C、Java などのプログラミング言語やオブジェクト指向言語は、リンク リストを生成するために可変ツールに依存しています。

特長

線形テーブルのリンクされたストレージ表現の特徴は、任意のストレージ ユニットのセットを使用して線形テーブルのデータ要素を格納することです (このストレージ ユニットのセットは、連続的または異なる) 連続的)。したがって、各データ要素とその直接の後続データ要素との間の論理的関係を表現するために、データ要素には、それ自身の情報を格納することに加えて、その直接後続者を示す情報（つまり、ストレージ）も格納する必要がある。直接後継の場所の）。これら 2 つの情報は、線形テーブル内のデータ要素を表す「ノード」を形成します (概要の隣の図を参照)。線形テーブルのリンク ストレージ表現の欠点の 1 つは、数値を見つけるために最初から開始する必要があり、非常に面倒なことです。

状況に応じて、リンク リストの他の拡張を自分で設計することもできます。ただし、連結リストの点と辺は基本的に 1 対 1 に対応するため、辺にはデータが付加されません（最初または最後のノードを除きますが、特別な事情は生じません）。ただし、特殊な場合として、リンク リストがリンク リストのセクション内の前後のポインタの反転をサポートしている場合は、端に反転マークを追加する方が便利な場合があります。

非線形リンク リストの場合は、ツリーやグラフなどの他の関連データ構造を参照できます。また、複数の線形連結リストであるスキップ リストに基づくデータ構造もあり、挿入、削除、検索などの基本操作の速度は平衡二分木と同じ O(nlogn) に達します。

データ要素情報を格納するドメインをデータ ドメイン (ドメイン名を data とする) と呼び、直接後継の格納場所を格納するドメインをポインタ ドメイン (ドメイン名を next とする) と呼びます。 。ポインタフィールドに格納される情報は、ポインタまたはチェーンとも呼ばれます。

それぞれ、、、を表す N 個のノードが順番にリンクされているリンク リストは、線形リストのリンク ストレージ表現と呼ばれます。これは、このようなリンク リストの各ノードにはポインターが 1 つしか含まれていないためです。フィールド であるため、単一リンク リストまたは線形リンク リストとも呼ばれます。

以上がリンクリストとはの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。