データ構造は、データを効率よく保存、検索、修正、削除(CRUD)する目的でデータを構造化する方法です。
同じデータの群であってもどのように構造化するかによって問題を解決する時間やコストが変わります。効率よく問題を解決するためには適したデータ構造を使ってデータを扱う必要があります。
ADT(抽象データ型)
データをどんな形でどんな操作をして片付けるのかルールだけを意味する言葉です。”理論的な概念”みたいな感じです。
実際メモリー(記憶装置)の中でどんな動きをするかはADTの概念には含まれていません。ここではどうやってデータをCRUDするかだけが重要です。
代表的なADTはこれです。
- List:順番に並べているデータ
- Set:重複しないデータの集まり
- Map:キーと値の一対に形成されているデータ
- Stack:データを後入れ先出し (LIFO: Last In First Out) の構造で扱う
- Queue:データを先入れ先出し (FIFO: First In First Out) の構造で扱う
- Tree:データを段層的で親子関係を用いて扱う
- Graph:ノードとエッジによって構成され、複雑な接続関係を表現します
具体データ型
ADT具現したものです。ADTの概念を物理的だメモリー(記憶装置)と演算アルゴリズムでどうやってデータを保存するのかの概念が含まれています。
- List:ArrayList, LinkedList
- Set:HashSet、TreeSet
- Map:HashMap, TreeMap
- Stack:配列ベースStack、LinkedListベースStack
- Queue:配列ベースQueue、LinkedListベースQueue
- Tree:ポインタ(リンク)ベースの木、配列ベースのヒープ (Heap)
- Graph:隣接リスト