配列
- メモリ上に連続した領域を確保する
- データの追加・削除は先頭から走査する必要があるので
O(n) - 書き込み、読み込み共に
O(1) - 配列は宣言時の長さから変更が出来ない = いわゆる静的配列
連結リスト
- メモリ上に連続して領域を確保するわけではなく、必要に応じて確保する
- {データ、次のレコードを指すポインタ}という構造の構造体と、リストの先頭を指すポインタから構成される
- リスト先頭に対するデータの追加、削除は
O(1) - 連結リスト内の要素の探索は時間がかかる
- リストの構造上、使用するメモリ領域は配列よりも大きくなる
スタック
- LIFO(Last In First Out)
- 後から入れたものが先に出て行く構造
- pushでデータの追加、popでデータの取り出しを行う
- push, pop のどちらも
O(1)
キュー
- FIFO(First In First Out)
- 先に入れた奴が先に出て行く構造
- enqueueでデータの追加、dequeueでデータの取り出しを行う
- enqueue, dequeueのどちらも
O(1)
