Javaのデータ構造

データ構造の代表例

・配列
・連結リスト
・スタック
・キュー
・グラフ
・ツリー
・ハッシュテーブル

配列のメリット／デメリット

メリット
・添え字（＝インデックス、キー）で個々の値を区別してアクセスできる

デメリット
・値の挿入や削除が苦手

配列同士の代入

参照渡し

コレクションフレームワークとは

「広く受け入れられ確立した共通部品」としてのデータ構造クラスのAPI群

コレクションフレームワーク２分類

・Collection系
・Map系

Collectionとは

要素の集まり

Collection系２分類

・List系
・Set系

Listのメリット

事前にサイズを決める必要がない（メモリの許す限り要素を追加できる）

List

・ArrayList ：配列
・LinkedList：連結リスト

ひとまずArrayListを選んでおけばいい

Setデータ構造とは

・重複要素を排除するコレクション（同じ要素を後から追加しても無視する）
・内部で順序を管理しない（インデックスによる要素アクセス、要素削除ができない）

Collectionに関連する型

・Iterable型  ：抽象型：反復子を提供できる何か
・Collection型：抽象型：要素の集まり
・List型      ：抽象型：順序付きの要素の集まり
・ArrayList型 ：実装型：配列データ構造で実装したList
・LinkedList型：実装型：連結リストデータ構造で実装したList
・Set型       ：抽象型：重複のない要素の集まり（Set）
・HashSet型   ：実装型：ハッシュ値を利用したSetの実装

実装型／抽象型

・実装型：newできる
・抽象型：newできない

連結リストとは

ひとつひとつの値を「エントリ」として保持しつつ、各エントリが「自分の次に位置するエントリ」を知っている、という構造

連結リストのメリット／デメリット

メリット
・追加や削除の効率において優れている

デメリット
・ランダムアクセス（例：150番目の値）が苦手

スタックとは

入れ物の中に要素を積み上げていくようなデータ構造。先入れ後出し

プッシュ／ポップ

・プッシュ（push）：要素を投入すること
・ポップ（pop）　 ：要素を取り出すこと

キューとは

パイプの中に要素が順番に並ぶようなデータ構造。先入れ先出し

エンキュー／デキュー

・エンキュー（enqueue）：データを投入すること
・デキュー（dequeue）　：データを取り出すこと

Mapデータ構造とは

・ディクショナリ（辞書）と呼ばれるデータ構造
・辞書における単語の役割を「キー」、説明文の役割を「バリュー（値）」と呼ぶ
・ジェネリクスは型を２つ指定する（キーとバリュー）