データ構造
データ構造（データこうぞう、英: data structure）とは、コンピュータプログラミングでの、データの集まりの形式化された構成である。格納された各データの参照や修正といった管理を容易にするための構成である[1][2][3][4] 。一定の関係性を持たせたデータ型のコレクションであり、データ値に適用するための関数や手続きも格納されることがある[5]。データの代数的構造とも言われる。
概要
[編集]ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。
多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェースの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。
データ構造は専門的な、あるいは非専門的な（すなわち、あらゆる）プログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造がサポートされている。データ構造が実装を表すのかインターフェースを表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。
脚注
[編集]- ^ 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
- ^ Wegner, Peter; Reilly, Edwin D. (2003-08-29). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. pp. 507–512. ISBN 978-0470864128
