リンクリストとはどのようなデータ構造ですか?

リンク リストは、物理ストレージ ユニット上の非連続かつ非順次のストレージ構造です。データ要素の論理的順序は、リンク リスト内のポインタ リンクの順序によって実現されます。簡単に言えば、リンク ストレージ線形リストの構造 生成されたテーブルを「連結リスト」と呼びます。リンク リストの各データ要素は 2 つの部分で構成されます: 1. 「データ フィールド」と呼ばれる情報自体、2. 「ポインタ フィールド」と呼ばれる直接の後続要素へのポインタ。これら 2 つの情報部分は、「ノード」と呼ばれるデータ要素の記憶構造を形成します。n 個のノードはポインタ フィールドを介して互いにリンクされ、リンク リストを形成します。

このチュートリアルの動作環境: Windows 7 システム、Dell G3 コンピューター。

データ構造は、コンピューターがデータを保存および整理する方法です。データ構造とは、相互に 1 つ以上の特定の関係を持つデータ要素のコレクションを指します。多くの場合、データ構造を慎重に選択すると、操作効率やストレージ効率が向上します。データ構造は、多くの場合、効率的な検索アルゴリズムやインデックス付け技術に関連しています。

データ構造内の リンク リスト

リンク リストは非線形物理ストレージ ユニット。連続的で非順次的なストレージ構造では、データ要素の論理的順序は、リンク リスト内のポインタ リンク順序によって実現されます。リンク リストは一連のノードで構成され (リンク リストの各要素はノードと呼ばれます)、ノードは実行時に動的に生成できます。

論理構造上に次々に存在するデータは、実際に格納される際には順序表のように隣り合っていません。これに対して、データはメモリ内のさまざまな場所にランダムに分散されており、このような記憶構造を線形リストのリンクストレージと呼びます。

分散ストレージのため、データ要素間の論理関係を反映するために、各データ要素には、保存時にその直接の後続要素、つまり各データ要素を指すポインタが装備されている必要があります。どちらも次のデータ要素を指します (最後のデータ要素は NULL (空) を指します)。

#上図に示すように、各データ要素がポインタで次のデータ要素にリンクされるとチェーンが形成され、チェーンの先頭が配置されます。最初のデータ要素では、この保存方法はチェーン ストレージです。

線形テーブルの連結記憶構造によって生成されるテーブルを「連結リスト」と呼びます。

リンクされたリスト内のデータ要素の構成

各要素自体は 2 つの部分で構成されます:

• それ自体の情報は「データ フィールド」と呼ばれ、

• 直接の後続のものを指すポインタは「ポインタ フィールド」と呼ばれます。

これら 2 つの情報部分は、「ノード」と呼ばれるデータ要素の記憶構造を構成します。 n 個のノードはポインタ フィールドを介して互いにリンクされ、リンク リストを形成します。

ヘッド ノード、ヘッド ポインタ、および最初のノード

ヘッド ノード: 場合によっては、リンク リストの最初のポイントに追加ノードはノードの前に追加されます。ノードのデータ フィールドには通常、データは格納されません (場合によっては、リンク リストの長さなどの情報も格納される場合があります)。このノードはヘッド ノードと呼ばれます。

ヘッド ノードのポインター フィールドが空 (NULL) の場合、リンク リストが空のリストであることを示します。リンク リストにはヘッド ノードは必要ありません。特定の問題に対処する場合、リンク リストにヘッド ノードを追加すると問題が簡単になります。

ヘッド ノード: リンク リストの最初の要素が配置されるノードで、ヘッド ノードの後の最初のノードです。

ヘッド ポインタ: 常にリンク リストの最初のノードの位置を指します (リンク リストにヘッド ノードがある場合、ヘッド ポインタはヘッド ノードを指します。それ以外の場合、ヘッド ポインタは最初のノードを指します)ノード）。

ヘッド ノードとヘッド ポインターの違い: ヘッド ポインターは、ヘッド ノードまたはリンク リストの最初のノードを指すポインターです。ヘッド ノードはデータを含む実際のノードです。フィールドとポインタフィールド。プログラム内でこの 2 つが直接表れるのは、ヘッド ポインターは宣言されるだけで記憶領域は割り当てられないこと、およびヘッド ノードが宣言されてノードの実際の物理メモリが割り当てられることです。

#リンク リスト構造を使用すると、データ サイズを事前に知る必要があるという配列リンク リストの欠点を克服できます。コンピュータのメモリ空間を最大限に活用し、柔軟なメモリ ダイナミクスを実現できます。しかし、リンクリストは配列のランダム読み取りの利点を失い、同時にノードのポインタフィールドの増加によりリンクリストのスペースオーバーヘッドが比較的大きくなります。リンク リストの最も明白な利点は、通常の配列で関連する項目を配置する方法が、これらのデータ項目がメモリまたはディスク上で配置される順序とは異なる場合があり、データへのアクセスには、多くの場合、異なる配置間の切り替えが必要になることです。 ＃＃＃＃＃＃＃＃＃＃＃＃特徴＃＃＃＃＃＃

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

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

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

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

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

リンク リストからのノードの挿入と削除

リンク リストでは、テーブル上の任意の位置でノードの挿入と削除が可能ですが、ランダム アクセスは許可されません。

1. リンク リストへのノードの挿入

• リンク リストへの先頭ノードの挿入は、挿入位置により 3 種類に分かれます:

• リンク リストの先頭、つまり先頭ノードと最初のノードの間に挿入します。

• リンク リスト内の特定の位置に挿入します。リンクされたリストの途中;

• リンクされたリストの最後に挿入;

挿入はされますが位置が違っても挿入方法は同じです。上の図に示すように、これは 2 つのステップに分かれています:

• 新しいノードの次のポインタを挿入位置の後のノードにポイントします。

  # 挿入位置の前のノードの次のポインタは、挿入ノードを指します;

• ヒント: 挿入操作を実行するときは、まず挿入位置で前のノードを見つける必要があります。図 4 でも、これはノード 1 を見つけることであり、対応するノード 2 はノード 1 の次のポインタによって表すことができます。実装プロセス中に他の補助ポインタを追加する必要があります。

2. リンク リストからノードを削除する

リンク リストからノードを削除する必要がある場合は、次の 2 つの手順を実行する必要があります:

リンクされたリストからノードを削除します;

• ノードを手動で解放し、ノードが占有しているメモリ領域をリサイクルします;

• その他の関連事項詳細については、

  FAQ
列をご覧ください。

以上がリンクリストとはどのようなデータ構造ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。