データ構造
データ構造（データこうぞう、英: data structure）とは、コンピュータプログラミングでの、データの集まりの形式化された構成である。格納された各データの参照や修正といった管理を容易にするための構成である[1][2][3][4][5]。一定の関係性を持たせたデータ型のコレクションであり、データ値に適用するための関数や手続きも格納されることがある[6]。データの代数的構造とも言われる。
概要
[編集]ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的な性能は最良のデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。
多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりも重要な構成要素とされていることにも現れている。現代的なプログラミング言語は異なるアプリケーションにおいてデータ構造の安全な再利用を可能とするように、実装の詳細をインターフェースの背後に隠蔽するための、モジュール化のしくみを備えている。C++やJavaなどのオブジェクト指向プログラミング言語はクラスをこの目的のために用いている。
データ構造は専門的な、あるいは非専門的な（すなわち、あらゆる）プログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造が利用可能となっている。データ構造が実装を表すのかそれともインターフェースを表すのかについての議論は多少ある。どのように見えるのかは相対的な問題であるのかもしれない。データ構造は関数同士の間のインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。
基本的なデータ構造の例
[編集]- 配列
- リスト
- 木
- ファイル
- ハッシュ表
- 辞書
- 集合
- レコード
脚注
[編集]- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press. ISBN 978-0262033848
- ^ Black, Paul E. (15 December 2004). “data structure”. In Pieterse, Vreda; Black, Paul E.. Dictionary of Algorithms and Data Structures [online]. National Institute of Standards and Technology 2018年11月6日閲覧。
- ^ "Data structure". Encyclopaedia Britannica. 17 April 2017. 2018年11月6日閲覧。
- ^ ゴンザロ・ナバロ：「コンパクトデータ構造 実践的アプローチ」、講談社サイエンティフィク、(2023年7月26日)、ISBN 978-4-06-512476-5
- ^ 定兼邦彦：「簡潔データ構造」、共立出版、ISBN 978-4-320-12174-4 (2018年2月25日)
- ^ Wegner, Peter; Reilly, Edwin D. (2003-08-29). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. pp. 507–512. ISBN 978-0470864128
