Summary
- プログラム＝データの操作（データの入力→操作→出力）
- データの効率的な操作は、データを適切な形で（＝データ構造）適切な仕方で（＝アルゴリズム）で処理することにより達成される。
- アルゴリズムの評価指標＝計算量（complexity）
- 計算量の種別
- 時間計算量（time complexity）：処理の速度
- 領域計算量（space complexity）：必要なメモリ領域
- 時間と空間のトレードオフ＝以下のトレードオフ
- 遅いがメモリをあまり消費しないアルゴリズム
- 早いがメモリをたくさん消費するアルゴリズム
- 計算量の入力データの種別
- 最大計算量（worst-case complexity）←最大の入力データ（普通はこれ）
- 平均計算量（expected complexity）←全入力データに対する計算量の平均
- 計算量の種別
- データ構造に関連する基本用語
- データ型（data type）：データの扱い方を規定する形式
- 抽象データ型（abstract data type）：データ型＋そのデータ型のデータに対する操作（※inheritanceとpolymorphismの要素を除外したclassと同義）
- データ構造（data structure）：抽象データ型におけるデータ型を具体的に表現したもの
- 「データ型（data type）」の分類
- primitive
- numeric
- integral
- floating point
- boolean
- numeric
- reference
- class
- interface
- array
- primitive
- ラッパークラス（wrapper class）＝プリミティブ型を包み込んでオブジェクト（＝ reference型）として扱えるようにしてくれるクラス
- ボクシング変換（boxing conversion）：プリミティブ型→ラッパークラス
- 例：int→Integer
- 自動変換：Integer x = 100;
- 手動変換：Integer x = new Integer(100);
- アンボクシング変換（unboxing conversion）：ラッパークラス→プリミティブ型
- 例：Integer→int
- 自動変換：int a = x;
- 自動変換：int a = x.intValue();
- ボクシング変換（boxing conversion）：プリミティブ型→ラッパークラス
- プリミティブ型（primitive型）と参照型（reference型）の違い
- プリミティブ型：変数には値が直接入っている
- 参照型：変数には参照値（＝オブジェクトのポインタ）が入っている
- shallow copyとdeep copy
- shallow copy：オブジェクトの複製時に参照をそのままコピー
- deep copy：オブジェクトの複製時に参照先の値まで含めてコピー
- 補足：clone()メソッドはshallow copy
- オブジェクトの同一性と等値性
- 同一性：参照値が等しい（==演算子・!=演算子）
- 等値性：値が意味的に等しい（equalsメソッド）
- 補足：異なる変数が別々の場所に格納された3という値を参照することがあり得る。
- referenceを実例で理解する
- int[] array; //配列への参照を型として持つ変数arrayが確保されるが、配列の実体は生成されておらず、従ってそのメモリアドレスも格納されていない。
- int[] array = new int[100]; //int型の要素100個から成る配列が生成され、その配列のポインタが変数arrayに代入されている。
- ジェネリクス（generics）
- List<String>のように<>の記号を用いてクラスやメソッドの「型パラメータ（type parameter）」を指定できる機能（Jaba1.4で追加される以前は全てObject型だったのでその都度型キャストする必要があった）
- 「データ構造（data structure）」の分類
- linear
- array（≒list）
- stack
- queue
- linked list
- singly linked list
- doubly linked list
- circular linked list
- non-linear
- tree
- graph
- linear
- 「データ構造（data structure）」の分類（解説付）
- linear
- array（≒list）：順序付けられた要素の集合
- stack：LIFOに従う（＝先頭のみ挿入・削除される）リスト
- queue：FIFOに従う（＝先頭のみ削除・末端のみ挿入される）リスト
- 補足：店の行列などと一緒
- linked list：別の要素とリンク（link）によってつながった構造を持つリスト
- singly linked list：前の要素が次の要素へのリンクを持つリスト
- doubly linked list：前後の要素が相互に繋がったリスト
- circular linked list：最後の要素のリンクがnullではなく、先頭の要素を示すようなリスト
- non-linear
- tree：階層型のデータ構造
- graph：nodes同士がedgeによって繋がったデータ構造
- linear