リンクリストとはどのようなデータ構造ですか?-よくある問題-php.cn

リンクリストは、物理ストレージユニット上の非連続かつ非順次のストレージ構造です。データ要素の論理的順序は、リンクリスト内のポインタリンクの順序によって実現されます。簡単に言えば、リンクストレージ線形リストの構造生成されたテーブルを「連結リスト」と呼びます。リンクリストの各データ要素は 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 つの手順を実行する必要があります:

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