ヤマザキの地球偵察記録

ヤマザキさんの個人的な記録・備忘録です。

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

配列

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