けけずんセルフハッキング

忘れそうなことをメモる。

情報工学レクチャーシリーズ:アルゴリズムとデータ構造 第二章「アルゴリズムの基本データ構造」

配列

  • メモリ上に連続した領域を確保する
  • データの追加・削除は先頭から走査する必要があるので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)