技術記事ノックのメモ書き - データ構造について -

• データ構造とは

  • データをコンピュータの中で扱う際にデータを格納する一定の形式

    • 何種類かある

  • 事前に考え、最適なデータ構造を選択する必要がある

• それぞれの特徴(長所と短所)の理解が必要

1. Bag
   重複したデータを格納出来る => 延べ人数を記録するようなデータ
   重複を許さない物を set という => ユニークな人数を記録するようなデータ
   
   
2. Sequence
   1. 配列(Array)
      同じような型(数値や文字列)のデータをインデックスをもとに格納する
      = 同一の型のデータを一列に並べた物
      領域の拡張が出来ない => 予め余分に領域を確保しておくか、より大きい配列に現在の内容をコピーする必要がある
      ※先頭が0番、最後の要素はN-1番
   2. リスト(List)　一番基本的なデータ構造
      各要素に次の要素のリンクを保持させる。
      最後の要素は次の要素へのリンクを持たせない事で表現する
      • 単方向リスト = 値と次へのリンクを保持する
      • 双方向リスト = 値と前後のリンクを保持する
        
        
3. Tree
   階層関係を表す事が出来る
   (ツリー構造を見た感じ、Linuxのディレクトリ構造に近いか)
   Gitのデータ構造もこれかな？
   
   
4. Map
   一つの要素内に、データの場所を表すキーとバリューを対応付けて格納する

まとめ

•  Bag
  重複した値でも格納する事が出来るが、Setでは重複した値は格納出来ない
  • 実装方法
    配列、木構造
• Sequence
  インデックスで管理された要素に順にデータを格納する
  • 実装方法
    配列、リスト
• Tree
  階層構造(親子関係)をもったデータを格納出来る
  • 実装方法
    二分深索木
• Map
  KeyとValueを紐づけてデータを格納する
  
  • 実装方法
    ハッシュ
    
    
• スタック
  • LIFO ( Last In , First Out )
    • 操作で「元に戻す」がまさにそれ
  • データを積む事をプッシュ
  • データを取り出す事をポップ
• キュー
  • スタックの正反対の概念
  • FIFO ( First In , First Out )
    • 先に並んだ人が先にお店に入れるような感じ
• リングバッファ
  • キューの問題点
    • データの追加が困難
    • データを追加したり取り出したりする毎にデータの列を移動させるのは効率が悪い
  • 上記の問題を防ぐためにリングバッファが考えられた
    • キューの配列の先頭と末尾を結びつけ、リングであるかのような構造にし、キューの使用回数を無制限にするための工夫