リスト(データ構造) – ウィキペディア
一 出現したリスト データ要素が順番に保存される動的なデータ構造です。それを作成する場合、要素の最大数を決定する必要はなく、期間中に必要に応じて数が異なる場合があります。
データ型
タイプの要素を含む単純なチェーンリスト
再帰的に定義されています
。技術的な実装は通常、ネットデータ自体と後継ノードへの参照で構成される個々のノードによって実行されます。最後のノードでは、いわゆるゼロポインターが後継ノードとして与えられます。
呼ばれています。 [初め]
初等リストの操作は、最初のノードによるリストの拡張と、最初の結び目の削除であり、時間内に
行うことができます。
利点
- 検索が行われ、挿入が見つかった場合、挿入の努力はいつでもあります 。配列で 対照的に、データレコードをコピーする必要があります。
- 追加のメモリ要件が低い(1ポインター)。
短所
- 検索コストはです 、最も有利なものはすべての結び目を反復する必要があるため。
アプリケーション [ 編集 | ソーステキストを編集します ]
単純なチェーンリストは、アレイを賢明に機能させることができなくなる非常に動的な環境で使用されます。これらは構文操作に対処することを非常に困難にするためです。データ型を備えた単純なチェーンリストも同様です
と
したがって
他の基本的なLISPデータ型、プログラミング言語LISPの中央データ型。 LISPプログラムでさえ、そのようなリストでさえあります。
シンプルフレームリストとは対照的に、各要素には、後続の要素と以前の要素の両方のポインターがあります。
前身 最初と 後継者ポインター 最後の要素のポイントゼロを指します。この特別な要素は、ダブルチェーンリストの開始と終了を決定するのに役立ちます。 [初め]
利点
- リストから要素を削除することができます 要素の到着が起こらなかったとしても、起こりました。この場合、前任者の単純な鎖のリストを検索する必要があります。
- リストは、背面から前面に反復することができます。
短所
- 追加の手のより高いメモリ要件。
- 削除および挿入すると、次のリスト要素の前身も調整する必要があります。
ヘッドをリストします [ 編集 | ソーステキストを編集します ]
リストヘッド(またはリストアンカー)は、リスト内のノードの数などの追加情報を含めることができるデータフィールドです。最初の要素を指します。
船舶リスト [ 編集 | ソーステキストを編集します ]
戦いのリストと同様に、データはスキープリストのコンテナにも保存されます。これらには、次のコンテナにキーとポインターが含まれています。ただし、コンテナには、直接従わない他の容器へのスキープレート内のポインターを含めることもできます。したがって、キーをスキップできます。各容器には一定の高さがあります
どちらの周り
容器を含む手の数よりも小さい。手はからです
それまで
番号付き。基本的に、スキープリストは、フィールドのバイナリ検索を模倣します。
スキップリストでは、3つのタイプのタイプ間で区別が行われます。
- バランスが取れています 船
- 不均衡 スキープリスト(写真を参照)
- ランダム化 船
コンテンツのコンテンツは、すべてのタイプで許可されています。ただし、ランダム化されたスキープリストを必ずしも注文する必要はありませんが、アウトとバランスの取れたスキープリストが配置されています。実装の努力を増やす中間ステーションを挿入することにより、平均アクセス時間と関連する複雑さを減らすことができます。スキープリストの原則の拡張は、「残基」を可能にする二重リンクリストの原理へのリンクです。ただし、バランスの取れたスキープリストが発生した場合、これは複雑さを軽減するものではありませんが、不均衡なスキープリストが発生した場合、これは分配される可能性があり、次の中間ステーション近くの要素へのアクセスが増加します。
操作の挿入、検索、削除には、予想される期間があります
。
容器の高さの計算
ランダム化されたスキープリスタでは、高さが計算されます
無作為に。特定の高さが達成される可能性は、次のように決定できます。
ランダム化されていないスキープリストの場合、高さはポインターの高さを持つ各ポインターがあるように決定されます
コンテナの上
位置はリストにさらに戻ることができます – その間のすべてのコンテナは、ポインターよりも高さが低くなります。
適応リッスン [ 編集 | ソーステキストを編集します ]
個々のステップあたりの開始からの距離を持つ簡単なリンクリストの要素にアクセスする努力が増加するため、適応リストの原則が見つかりました。この努力を可能な限り低く保つために、リスト要素はアクセス頻度に従ってソートされます。 3つの基本的な戦略があります。
- Movetofront:これは、すべての要素アクセスに対して削除され、リストの先頭に挿入されます。
- Transpose:すべての要素で、それはその前身と交換されます(特別なケース:最初の要素)
- 満足:そのアクセス周波数は、各要素に対して保存されます。特定の間隔で、リストはアクセス周波数を使用してソートされます。
抽象データ型 [ 編集 | ソーステキストを編集します ]
データは、構造がカウンター、ポインター、および比較関数のアドレスで構成されるリストの一連のキーに保存されます。データノードには、データ構造のポインターと自己参照ポインターが含まれています。これは、リストの次の結び目を指します。
C ++では、リストは抽象データ型として定義できます。 [2]
struct ノード { 空所 * Datapointer ; ノード * リンク ; }; struct リスト { int カウント ; ノード * 頭 ; virtual int compare(List &other) = 0;
};
オブジェクト指向プログラミングのリスト [ 編集 | ソーステキストを編集します ]
オブジェクト指向のプログラミングでは、リストは多くのリスト操作によってデータカプセルの原則に従って特徴付けられます。内部的には、バイナリツリーなどのさまざまな複雑なデータ構造を使用できます。内部データ構造により、ソート、ソート付き挿入、最大の要素の削除などのその他の機能を提供することがよくあります。
アプリケーションに応じて、インターフェイスの具体的な実装間で意味があります リスト 選択する。たとえば、インデックスを介してインデックス経由でリストにアクセスされている場合、チェーンズリストは悪い選択になります。 n 操作が必要です n -TETに対処する要素。
したがって、インターフェイスに加えて、オブジェクト指向のライブラリでさまざまな具体的な実装が提供されることがよくあります。たとえば、Javaはプログラミング言語でインターフェイスとして入手できます java.util.list 、 [3] そして、とりわけがあります java.util.linkedList [4] と java.util.arraylist [5] 具体的な実装として提供されます。 C ++では、リストとベクトルが標準ライブラリに実装されています。
次の例はC#で書かれています。この目的のために、数字と後継ノードを保存できる結び目が定義されています。
クラス ノード { 公共 int エレメント = 0 ; 公共 ノード -up notをフォローします = ヌル ; }
リストに新しい要素を挿入します [ 編集 | ソーステキストを編集します ]
静的 空所 エレメント ( ノード ノード 、 int 新しい要素 )) { その間 ( ノード 。 -up notをフォローします != ヌル )) ノード = ノード 。 -up notをフォローします ; ノード 。 -up notをフォローします = 新しい ノード (); ノード 。 -up notをフォローします 。 エレメント = 新しい要素 ; }
要素を見つけます [ 編集 | ソーステキストを編集します ]
静的 ブール 要素検索 ( ノード ノード 、 int alteselement )) { その間 ( ノード != ヌル )) { もしも ( alteselement == ノード 。 エレメント )) 戻る 真実 ; ノード = ノード 。 -up notをフォローします ; } 戻る 間違い ; }
リストから要素を削除します [ 編集 | ソーステキストを編集します ]
静的 空所 アイテムレス ( ref ノード ノード 、 int alteselement )) { その間 ( ノード != ヌル && alteselement != ノード 。 エレメント )) ノード = ノード 。 -up notをフォローします ; ノード 現在 = ノード ; その間 ( 現在 != ヌル )) { もしも ( 現在 。 -up notをフォローします != ヌル && alteselement == 現在 。 -up notをフォローします 。 エレメント )) 現在 。 -up notをフォローします = 現在 。 -up notをフォローします 。 -up notをフォローします ; それ以外 aktuell = aktuell.folgeknoten;
}
}
オブジェクト指向言語でのリストの使用 [ 編集 | ソーステキストを編集します ]
この例は、C ++のリストの使用を示しています。
#含む #含む #含む
使用 名前空間 std ; int 主要 () { //初期化 自動 リスト = リスト < int > (); //最初に貼り付けます リスト 。 push_front ( 4 ); liste.push_front(3);
// am Ende anfügen
liste.push_back(5);
liste.push_back(6);
// die Liste enthält 3 4 5 6
// Durchlaufen der Liste
for (int element: liste)
cout << element << " ";
// Entfernen aller Zahlen größer als 4
liste.erase(remove_if(liste.begin(), liste.end(), [](int x) { return x > 4; }), liste.end());
cout << endl;
for (int element: liste)
cout << element << " ";
// Sortieren
liste.sort();
// Löschen
liste.clear();
}
- ↑ a b ゼロポインターの代わりにガードポインターまたはセンチネルを使用すると、検索ループの比較を保存できます。
- ↑ geeksforgeeks: 抽象データ型
- ↑ java.util.list Java API仕様
- ↑ java.util.linkedList Java API仕様
- ↑ java.util.arraylist Java API仕様
Recent Comments