リンクリストの特徴は、線形リストのデータ要素を任意の記憶単位の集合を用いて格納することであるため、各データ要素とその直接の後続データ要素との間の論理的関係を表現するために、 、データ要素については、自身の情報に加えて、その直接の後続を示す情報を格納する必要がある。
#特徴
単一リンクリスト、矢印の端がノード
線形テーブルのリンクされたストレージ表現は、線形テーブルのデータ要素を格納するために任意のストレージ ユニットのセットを使用することを特徴とします (このストレージ ユニットのセットは連続または不連続にすることができます)。 。したがって、各データ要素とその直接の後続データ要素との間の論理的関係を表現するために、データ要素には、それ自身の情報を格納することに加えて、その直接後続者を示す情報(つまり、ストレージ)も格納する必要がある。直接後継の場所の)。これら 2 つの情報は、線形テーブル内のデータ要素を表す「ノード」を形成します (概要の隣の図を参照)。線形テーブルのリンク ストレージ表現の欠点の 1 つは、数値を見つけるために最初から開始する必要があり、非常に面倒なことです。
状況に応じて、リンク リストの他の拡張を自分で設計することもできます。ただし、連結リストの点と辺は基本的に 1 対 1 に対応するため、辺にはデータが付加されません(最初または最後のノードを除きますが、特別な事情は生じません)。ただし、特殊な場合として、リンク リストがリンク リストのセクション内の前後のポインタの反転をサポートしている場合は、端に反転マークを追加する方が便利な場合があります。
非線形リンク リストの場合は、ツリーやグラフなどの他の関連データ構造を参照できます。また、複数の線形連結リストであるスキップ リストに基づくデータ構造もあり、挿入、削除、検索などの基本操作の速度は平衡二分木と同じ O(nlogn) に達します。
データ要素情報を格納するドメインをデータ ドメイン (ドメイン名を data とする) と呼び、直接後継の格納場所を格納するドメインをポインタ ドメイン (ドメイン名を next とする) と呼びます。 。ポインタフィールドに格納される情報は、ポインタまたはチェーンとも呼ばれます。
それぞれ、、、を表す N 個のノードが順番にリンクされているリンク リストは、線形リストのリンク ストレージ表現と呼ばれます。これは、このようなリンク リストの各ノードにはポインターが 1 つしか含まれていないためです。フィールド であるため、単一リンク リストまたは線形リンク リストとも呼ばれます。
以上がリンクリストの特徴は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。