データ構造

データ構造

問題を効率的に解くに当たって、機械にどのような情報を持たせるか、によって計算量や時間は変わってくる。

よく見る例としては、配列・リストの違いが挙げられる。

配列・リストは、どちらもデータを順序立てて記録するときに使う。(この用語の使われ方はハッキリとした定義があるわけではなく、言語等によって変わるが、ひとまずは以下に示すものを指すということで)

配列

配列は、データ数分の領域をメモリ上に確保し、順番に格納する。

      ┌─┬─┬─┬─┬─┐
データ│ 3│ 1│ 4│ 1│ 5│
      └─┴─┴─┴─┴─┘
メモリ [ 0][ 1][ 2][ 3][ 4]

リスト

リストは、データはメモリ上にはバラバラに存在し、値と次のメモリアドレスをセットで保持する。

        値  次
      ┌─┬─┐  ┌─┬─┐  ┌─┬─┐
データ│ 3│10│→│ 1│50│→│ 4│20│→ …
      └─┴─┘  └─┴─┘  └─┴─┘
メモリ [ 0]        [10]        [50]

比較

配列リスト
必要メモリ領域
ランダムアクセス速い順番に辿るため遅い
要素の数固定増減可能
入れるデータの型固定自由
要素の途中への追加・途中からの削除後ろを1つずつずらすため遅いアドレスの書き換えのみで済むため速い

など、両者にメリットデメリットがあることがわかる。

要素数が変わったり追加削除が頻繁に行われるならリスト、データが大量だったり速度が求められる場合には配列、など、適切なデータ構造を使い分けることがよりよいプログラムには重要となる。

programming_algorithm/data_structure.txt · 最終更新: 2017/10/08 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0