データを一直線に並べたデータ構造である

・ポインタを用いるため、連続した領域にデータを格納する必要がなく、メモリの使用効率が高い。 ・データの追加、削除はポインタの差し替えのみで実現できるため、時間計算量が小さい

・データへアクセスする際には、ポインタをたどらなくてはならないため、時間計算量が大きい

・循環リスト ・双方向リスト

データを１つに並べたデータ構造のことである。

・データが連続して格納されるため、データへのアクセスが簡単である。

・データを連続して格納する必要があるため、メモリの使用効率が悪い ・データの追加や削除をする場合、その分だけデータをずらさなければならないため、時間計算量が大きくなってしまう。

データを格納していき、最後に格納したデータから処理を行うものである

・プッシュ:スタックにデータを追加 ・ポップ:スタックからデータを取り出す

・Webブラウザの戻るボタンなど

データを格納していき、最初に格納したデータから処理を行うものである。

・エンキュー:キューにデータを追加 ・デキュー:キューからデータを取り出す

・プリンターなどに用いられる

「キー」と「値」の組み合わせを１つのかたまりとして管理するデータ構造のことである

・ハッシュ関数を用いることでデータの操作を効率的に行うことが可能である。 ・データが衝突した場合でもチェイン法や開番地法を利用することで柔軟に対応できる。

・ハッシュテーブルで用意した配列が大きすぎる場合、格納されない配列が多くなってしまい、メモリの無駄遣いになってしまう ・ハッシュ関数に偏りがあると、データの衝突が多くなってしまう。

プライオリティーキューの１つで、木構造を用いて実装するデータ構造である。

・子は親より常に大きいか等しいという条件を満たす。 ・根には最小値か最大値が格納されているため、ヒープソートを実装する際に用いる

親の値に比べて、左の子の値が小さく、右の子の値が大きいという制約を持つ2分木のことである

・データを削除する際は左部分木の最大値か右部分木の最小値を入れ替える。 ・データの追加や削除を行う場合は木の高さの分だけ比較することになるため、時間計算量はO(log n)となる ・木が偏ってしまった場合は、一直線になってしまい、O(n)になってしまう。

・平行二分木 ・B木

各ノードは最大で二つの子ノードを持つことと、各ノードは１つの親ノードを持つことができるという特性を持った木構造のデータ構造のことである。

・挿入、削除、探索について、どの操作を行なっても平均時間計算量はO(log n) ・時間計算量がO(log n)と高速であるため、ソートアルゴリズムや検索アルゴリズムなど、広い分野で利用されている。