データ構造

配列


+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+

ヒープ


                       +---+
                       |   |
                       +-+-+
                         |
            +------------+-----------+
            |                        |
          +-+-+                    +-+-+
          |   |                    |   |
          +-+-+                    +-+-+
            |                        |
     +------+------+             +---+
     |             |             |
   +-+-+         +-+-+         +-+-+
   |   |         |   |         |   |
   +-+-+         +-+-+         +-+-+
     |             |             |
  +--+---+      +--+---+      +--+
  |      |      |      |      |
+-+-+  +-+-+  +-+-+  +-+-+  +-+-+
|   |  |   |  |   |  |   |  |   |
+---+  +---+  +---+  +---+  +---+

リングバッファ


            +---+       +---+
  +---------+   +-------+   +---------+
  |         +---+       +---+         |
  |                                   |
  |                                   |
+-+-+                               +-+-+
|   |                               |   |
+-+-+                               +-+-+
  |                                   |
  |                                   |
+-+-+                               +-+-+
|   |                               |   |
+-+-+                               +-+-+
  |                                   |
  |                                   |
  |         +---+       +---+         |
  +---------+   +-------+   +---------+
            +---+       +---+

ハッシュテーブル


+---+---+---+---+
|   |   |   |   |
+-+-+-+-+-+-+-+-+
  |   |   |   |
  |   |   |   +---------------------------------------+
  |   |   +-----------------------------------+       |
  |   +---------------------------+           |       |
  +-------------------+           |           |       |
                      |           |           |       |
                      v           v           v       v
        +---+---+---+-+-+---+---+-+-+---+---+-+-+---+-+-+
        |   |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+

連結リスト

+---+
|   |
+-+-+
  |
  v
+-+-+
|   |
+-+-+
  |
  v
+-+-+
|   |
+-+-+
  |
  v
+-+-+
|   |
+-+-+
  |
  v
+-+-+
|   |
+---+

グラフ



     +---+     +---+     +---+
     |   +--+  |   +-----+   |
     +-+-+  |  +---+     +-+-+
       |    |              |
       |    +--------------+
       |    |
     +-+-+  |  +---+     +---+
     |   |  +--+   |     |   |
     +-+-+  |  +---+     +---+
       |    |
       |    |
       |    |
     +-+-+  |  +---+     +---+
     |   +--+--+   +-----+   |
     +---+     +---+     +---+

2分木


                       +---+
                       |   |
                       +-+-+
                         |
            +------------+--------------+
            |                           |
          +-+-+                       +-+-+
          |   |                       |   |
          +-+-+                       +-+-+
            |                           |
     +------+------+             +------+------+
     |             |             |             |
   +-+-+         +-+-+         +-+-+         +-+-+
   |   |         |   |         |   |         |   |
   +-+-+         +-+-+         +-+-+         +-+-+
     |             |             |             |
  +--+---+      +--+---+      +--+---+      +--+---+
  |      |      |      |      |      |      |      |
+-+-+  +-+-+  +-+-+  +-+-+  +-+-+  +-+-+  +-+-+  +-+-+
|   |  |   |  |   |  |   |  |   |  |   |  |   |  |   |
+---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+

線形と非線形

線形データ構造

  • 配列

  • ヒープ

  • リングバッファ

  • ハッシュテーブル

非線形データ構造

  • 連結リスト

  • 2分木

  • グラフ

固定長か可変長か

固定長のデータ構造では、領域を確保すると長さを増やしたり減らしたりでき ない。コンパイル言語ではコンパイル時に必要なサイズを決定できるため、動 的に領域を確保する必要はない。可変長のデータ構造は、領域を確保した後で も長さを増やしたり減らしたりできる。可変長であるため、コンパイル時に必 要な長さを決定できず、実行時に領域を確保する必要がある。

固定長

  • 配列

  • ヒープ

  • リングバッファ

  • ハッシュテーブル

可変長

  • 連結リスト

  • 2分木

  • グラフ