配列
データを格納するためのコンピュータ内のメモリ空間の連続ブロック。
利点
- 作るのはとても簡単
- O(1)時間で配列の添え字から要素を検索できます。
デメリット
- ビルド時に連続した領域を確保する必要があります。
- ある要素が存在するかどうかを照会るには、配列全体を走査する必要があり、これにはO(n)個の時間がかかります。
- 要素の削除と追加にかかる時間は同じO(n)
連鎖リスト
- 単一リンクテーブル： リンクテーブルの各要素は実際には個別のオブジェクトであり、すべてのオブジェクトは各要素の参照フィールドによってリンクされています。
- 二重リンク・テーブル: 単一リンク・テーブルとは異なり、二重リンク・テーブルには各ノードに 2 つの参照フィールドがあります。
利点
- 連結されたテーブルにより、メモリ領域を柔軟に割り当て可能
- 要素の前の要素がわかっていれば、O(1)時間で要素を削除または追加できます。もちろん、ページは、それが単一リンク・テーブルか二重リンク・テーブルかによって異なりますが、二重リンク・テーブルでは、要素の次の要素がわかっていれば、O(1)時間で要素を削除または追加できます。
デメリット
- 添え字ですぐに読める配列とは異なり、チェーン・テーブルの先頭から1つずつ読み始めなければなりません。
- k番目の要素を照会るのにかかる時間はO(k)、最大O(n)、つまり最後の要素を見つけるのにかかる時間は
アプリケーションシナリオ
解決しようとする問題が多くの高速クエリを必要とする場合、連鎖テーブルは適切ではないかもしれません。問題が発生し、データの要素数が不明確で、要素の追加や削除が頻繁に必要な場合は、連鎖テーブルがより適切です。
スタック
スタックの最大の特徴はLIFOで、スタック内のデータに対して、すべての操作はスタックの先頭で行われ、スタックの先頭の要素しか見ることができず、スタックの先頭の要素しかデータに押し込むことができず、スタックの先頭の要素しかデータから飛び出すことができません。
の実装
スタックのデータ構造を実装するために単一のリンクされたテーブルが使用され、単一のリンクされたテーブルのヘッドはスタックの先頭です。
同様の効果を得るために配列とポインタを使用することを意図している場合、配列の長さが変わると、最後の要素の最後に新しい要素を追加するだけで、時間の複雑さはもはやO(1)ではなく、空間の複雑さは最適化されません。
アプリケーションシナリオ
問題を解くとき、直近の操作だけが注目される必要があり、操作を完了した後、さらに直近の操作に期待する必要があります
フォーメーション
キューは、スタックと違って、順番に並んでいるような先入れ先出しが最大の特徴で、キュー内のデータについては、キューの末尾にあるデータの追加と、キューの先頭にあるデータの削除だけが許され、両端の閲覧は
