リスト（データ構造） – ウィキペディア

Posted on by
before-content-x4

一 出現したリスト データ要素が順番に保存される動的なデータ構造です。それを作成する場合、要素の最大数を決定する必要はなく、期間中に必要に応じて数が異なる場合があります。

after-content-x4

データ型

l a {displaystyle l_ {a}}

タイプの要素を含む単純なチェーンリスト

a {displaystyle a}

再帰的に定義されています

l = n 私 l ‘ [ a 、 l a ] {displaystyle l = operatorname {mathit {nil}} mid [、a、l_ {a}、]}

。技術的な実装は通常、ネットデータ自体と後継ノードへの参照で構成される個々のノードによって実行されます。最後のノードでは、いわゆるゼロポインターが後継ノードとして与えられます。

n 私 l {displaystyle operatorname {mathit {nil}}}

呼ばれています。 [初め]

初等リストの操作は、最初のノードによるリストの拡張と、最初の結び目の削除であり、時間内に

o （ 初め ）） {displaystyle {mathcal {o}}（1）}

行うことができます。

after-content-x4

単に3つの値で鎖でつながれたリスト

利点

  • 検索が行われ、挿入が見つかった場合、挿入の努力はいつでもあります
  • 追加のメモリ要件が低い（1ポインター）。

短所

  • 検索コストはです

アプリケーション [ 編集 | ソーステキストを編集します ]

単純なチェーンリストは、アレイを賢明に機能させることができなくなる非常に動的な環境で使用されます。これらは構文操作に対処することを非常に困難にするためです。データ型を備えた単純なチェーンリストも同様です

l の = n 私 l ‘ [ の 、 l の ] {displaystyle l_ {u} = operaname {mathit {nyl}} mid [、u、l_ {u}、]}

と

の = l の ‘ と {displaystyle u = l_ {u} mid e}

したがって

と {displaystyle e}

他の基本的なLISPデータ型、プログラミング言語LISPの中央データ型。 LISPプログラムでさえ、そのようなリストでさえあります。

3つの値のダブルチェーンリスト

シンプルフレームリストとは対照的に、各要素には、後続の要素と以前の要素の両方のポインターがあります。

前身 最初と 後継者ポインター 最後の要素のポイントゼロを指します。この特別な要素は、ダブルチェーンリストの開始と終了を決定するのに役立ちます。 [初め]

利点

  • リストから要素を削除することができます
  • リストは、背面から前面に反復することができます。

短所

  • 追加の手のより高いメモリ要件。
  • 削除および挿入すると、次のリスト要素の前身も調整する必要があります。

ヘッドをリストします [ 編集 | ソーステキストを編集します ]

リストヘッド（またはリストアンカー）は、リスト内のノードの数などの追加情報を含めることができるデータフィールドです。最初の要素を指します。

船舶リスト [ 編集 | ソーステキストを編集します ]

戦いのリストと同様に、データはスキープリストのコンテナにも保存されます。これらには、次のコンテナにキーとポインターが含まれています。ただし、コンテナには、直接従わない他の容器へのスキープレート内のポインターを含めることもできます。したがって、キーをスキップできます。各容器には一定の高さがあります

h {テキストスタイルh}

どちらの周り

初め {テキストスタイル1}

容器を含む手の数よりも小さい。手はからです

0 {テキストスタイル0}

それまで

h {テキストスタイルh}

番号付き。基本的に、スキープリストは、フィールドのバイナリ検索を模倣します。

Skip-Liste mit mehreren Sprüngen

スキップリストでは、3つのタイプのタイプ間で区別が行われます。

  1. バランスが取れています 船
  2. 不均衡 スキープリスト（写真を参照）
  3. ランダム化 船

コンテンツのコンテンツは、すべてのタイプで許可されています。ただし、ランダム化されたスキープリストを必ずしも注文する必要はありませんが、アウトとバランスの取れたスキープリストが配置されています。実装の努力を増やす中間ステーションを挿入することにより、平均アクセス時間と関連する複雑さを減らすことができます。スキープリストの原則の拡張は、「残基」を可能にする二重リンクリストの原理へのリンクです。ただし、バランスの取れたスキープリストが発生した場合、これは複雑さを軽減するものではありませんが、不均衡なスキープリストが発生した場合、これは分配される可能性があり、次の中間ステーション近くの要素へのアクセスが増加します。

操作の挿入、検索、削除には、予想される期間があります

o （ ログ ⁡ n ）） {displaystyle {mathcal {o}}（log n）}

。

容器の高さの計算

ランダム化されたスキープリスタでは、高さが計算されます

h {テキストスタイルh}

無作為に。特定の高さが達成される可能性は、次のように決定できます。

初め 2⋅2h{Text Style {frac {1} {2cdot 2^{h}}}}

ランダム化されていないスキープリストの場合、高さはポインターの高さを持つ各ポインターがあるように決定されます

と {テキストスタイルz}

コンテナの上

2 と {テキストスタイル2^{z}}

位置はリストにさらに戻ることができます – その間のすべてのコンテナは、ポインターよりも高さが低くなります。

適応リッスン [ 編集 | ソーステキストを編集します ]

個々のステップあたりの開始からの距離を持つ簡単なリンクリストの要素にアクセスする努力が増加するため、適応リストの原則が見つかりました。この努力を可能な限り低く保つために、リスト要素はアクセス頻度に従ってソートされます。 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();
}
  1. ↑ a b ゼロポインターの代わりにガードポインターまたはセンチネルを使用すると、検索ループの比較を保存できます。
  2. ↑ geeksforgeeks： 抽象データ型
  3. ↑ java.util.list Java API仕様
  4. ↑ java.util.linkedList Java API仕様
  5. ↑ java.util.arraylist Java API仕様
after-content-x4