データ構造とは

データ構造は、数値、文字、ブール値、整数などのプリミティブなデータ型を一貫性のある形式に結合します。これらのプリミティブなデータ・タイプは、それぞれ1つの値のみで保持されます。これらをデータ構造に組み合わせると、並べ替え、検索、挿入、削除などのより高度なデータ操作が可能になります。

たとえば、毎日の売上高を追跡したい営業チームを考えてみましょう。各データ ポイントを個別に記録する代わりに、チームはこのデータを「配列」と呼ばれるタイプのデータ構造に保管することができました。（詳細については、「データ構造の種類」を参照してください）。

Pythonでは、配列は次のようになります。

daily_sales = [500, 800, 600, 1200, 950]

配列を使用すると、チームはデータをすべてまとめて保存し、必要なときにデータ・ポイントを簡単に取得し、個々の要素と配列全体の両方に対して関数を実行できます。

コンピューター・プログラマーは、効果的なアプリケーションを構築するためにデータ構造に依存しています。コンピューター・サイエンスとデータサイエンスの分野において、データ構造はオペレーティング・システム、データベース、Webサイト、グラフィック、分析、ブロックチェーン、機械学習（ML）のアプリケーションなどに不可欠です。

データ構造は効果的なコードを書く基礎となるため、プログラミングの初心者に最初に教えられる内容の1つとなることが多いです。また、コンピューター・プログラミング分野の求職者が面接でよく質問されるトピックでもあります。

データ構造が重要なのは、コンピューターが大規模で複雑な情報セットを処理しやすくなるためです。データ要素を論理的に編成することにより、データ構造はコンピューター・コードの効率性を高め、コードの理解を容易にします。

プログラマーは、データ構造を使用して、コンピューティング・タスクを完了するための一連の命令であるアルゴリズムの速度と強度を向上させます。コンピューター・プログラミング分野では、この組み合わせは「データ構造とアルゴリズム」の「DSA」として知られています。DSAは、プログラマーが時間と空間の複雑度という2つの課題を解決するのに役立ちます。

時間の複雑度は、インプット量に基づいてアルゴリズムがタスクを完了するのにかかる時間の尺度です。空間の複雑度は、インプット量に基づいてアルゴリズムが使用するメモリーの量の尺度です。

数学的なメトリクスであるBig O記法を使用すると、プログラマーは空間と時間の複雑度を測定できます。これにより、特定のタスクにおいてどのデータ構造とアルゴリズムが最速のランタイムと最大のスペース効率を実現するかを判断できます。

データ構造は、複雑な問題を迅速に解決する手法である動的計画法でも重要な役割を果たします。

動的計画法では、再帰を使用して問題をより小さなコンポーネントに分割します。次に、プログラムはそれらのコンポーネントのソリューションを見つけ、サブソリューションを再構成して元の問題に対する完全なソリューションを作成します。

データ構造は、プログラムに各サブソリューションを保管および取得する方法を提供し、プロセス中にデータ要素を論理的に編成し続けることで、動的計画法を可能にします。

例えば、計算された値は配列に保持できます。完全なソリューションを作成するときにこれらの値を再計算する代わりに、プログラムは配列から値を取得できます。

これらの機能により、プログラマーは時間を節約し、問題をより効率的に解決できます。

データ構造は、線形と非線形の2つの主なカテゴリーに分かれています。

線形データ構造では、データが一列に並べられ、各データ要素が連続的に配置されます。この配置により、要素を順番にたどってアクセスすることが簡単になります。

線形データ構造は、簡単に実装できると考えられています。このカテゴリーの一般的なデータ構造には、配列、リンク・リスト、キューなどがあります。

非線形データ構造では、構成ロジックは線形の連続的な配置とは異なります。例えば、データ・ポイントを階層的に順序付けしたり、ネットワーク内で接続したりできます。

非線形構造内の要素は単一の線で相互に接続されていないため、線形データ構造の場合のように、1 回の実行ですべての要素を横断してアクセスすることはできません。非線形データ構造の例としては、ツリーやグラフなどがあります。

プログラマーが使用するデータ構造には、構築しているシステムとデータを使用して実行する必要のある内容に応じて、いくつかの種類があります。一般的なデータ構造には、次のものがあります。

• 配列
• キュー
• スタック
  
• リンク・リスト
• 木
• グラフ
• ハッシュ

配列は、最も基本的で広く使用されているデータ構造の1つです。同様のタイプのデータ項目を隣接するメモリの場所に保管します。この構造により、同じタイプの項目を簡単に見つけてアクセスできるようになります。

用途： 配列の一般的な用途には、データの並べ替え、保管、検索、アクセスなどがあります。配列は、キューやスタックなどの他のデータ構造を実装するための基盤としても使用できます。

例： コールセンターの毎日の平均顧客満足度スコアの配列は次のようになります。

average_customer_score = [4, 3.5, 3.7, 4.1, 3.4, 4.9]

キューのデータ構造は、「先入れ先出し」の「FIFO」と呼ばれるあらかじめ決められた順序でデータ操作を実行します。つまり、最初に追加されたデータ項目が最初に削除されることになります。プログラマーは、多くの場合、このデータ構造を使用して、待機リストに似た優先順位キューを作成します。

用途：キュー・データ構造は、プレイリスト内の次の曲、共有プリンターにアクセスできる次のユーザー、またはコールセンターで応答する次の通話を決定するために使用できます。

例：コールセンターの担当者と話すのを待っている顧客は、次のようなキューに入れられる場合があります。

queue = [customer 1, customer 2, customer 3]

担当者が対応可能になると、キューの最初の顧客と自動的に接続され、その顧客はリストから削除されます。その際のキューは次のようになります。

queue = [customer 2, customer 3]

キューと同様に、スタック データ構造は、あらかじめ決められた順序でデータ操作を実行します。ただし、スタックでは FIFO ではなく、「後入れ先出し」を意味する「LIFO」形式が使用されます。最後に追加されたデータ項目が最初に削除されます。

用途:スタックを使用すると、コンピュータ コード内の括弧やタグを正しく開閉したり、ブラウザの最近の履歴を追跡したり、アプリケーションの最近の操作を元に戻したりすることができます。

例： 多くのアプリは、スタックを使用してユーザーのアクションを追跡し、簡単に元に戻すことができます。例えば、テキスト・エディターは次のようなスタックを保持します。

recent_actions = [typing ‘.’, space, typing ‘T’]

ユーザーが「元に戻す」ボタンを押すと、スタック内の最新のアクション（「T」の入力）が元に戻されます。スタックは次のようになります。

recent_actions = [typing ‘.’, space]

リンク・リストはデータ項目を線形の順序で保管し、各項目はリスト内の次の項目に接続されます。この構造により、データのコレクション全体を移動することなく、新しい項目を挿入したり、既存の項目を削除したりすることが容易になります。

用途：リンク・リストは、Webブラウザーの履歴、メディア・プレーヤーのプレイリスト、アプリケーション操作の取り消しややり直しなどのケースで頻繁に挿入や削除を行うためによく使用されます。

例：メディア・プレーヤー内のビデオのリンク・リストの簡略化バージョンは次のようになります。

Video 1 – Video 2 – Video 3

リスト内の各オブジェクトは次のオブジェクトを指しているため、Video 1が終了すると、メディア・プレーヤーにVideo 2を開始するように指示します。

データの木構造はプレフィックス木とも呼ばれ、データ要素間の階層関係を確立するのに役立ちます。単一の親ノードは木構造の最上位に配置され、子サブノードはその下の後続のレベルで分岐します。

二分探索木、AVL木、B木などの異なるクラスのツリーには、異なるプロパティーがあり、異なる機能をサポートします。例えば、二分探索木では、各ノードには最大2つの子ノードが含まれます。この構造は、データ・セットの高速検索のサポートに役立ちます。

用途：木構造は、組織図、ファイル・システム、ドメイン・ネーム・システム、データベース・インデックス、機械学習アプリケーションの決定木などの階層を表すためによく使用されます。

例：

グラフ・データ構造は、頂点とエッジを使用して、さまざまなオブジェクト間の関係を整理します。頂点は点で「表される」データ・ポイントであり、エッジは頂点同士を接続する線です。

例えば、地図上では、都市が頂点となり、都市同士を結ぶ道路がエッジとなります。Facebookでは、ユーザーが頂点となり、ユーザー同士を繋ぐ関係性がエッジとなります。

用途：:グラフ・データ構造は、複雑な関係性の網の中でデータを検索する検索アルゴリズムで使用されることがよくあります。一般的な例としては、データをレベルごとに検索する幅優先探索や、複数のレベルのデータをドリルダウンして情報を検索する深さ優先探索などがあります。

例：

「ハッシュ・テーブル」または「ハッシュ・マップ」とも呼ばれるハッシュ・データ構造は、ハッシュ関数を使用してデータ値を保管します。ハッシュ関数はハッシュを作成します。ハッシュは、メモリー内の特定のデータ値の位置に対応する一意のデジタル・キーです。

ハッシュ・テーブルには、すべてのハッシュとデータ値のペアの検索可能なインデックスが含まれており、テーブルへのデータへのアクセス、テーブルからのデータの追加および削除が迅速かつ簡単に行えます。

用途：ハッシュ・データ構造は、電話帳、辞書、人事ディレクトリーからデータをすばやく取得するのに役立ちます。また、データベースのインデックス作成、パスワードの保管、ITシステムの負荷分散にも使用できます。

例：スマートフォンの連絡先リストを整理するハッシュ・テーブルの簡略化バージョンは次のようになります。

ハッシュ関数は、各キーを適切なインデックスにマップします。そのため、ユーザーがキー（連絡先の名前）を入力すると、ハッシュ・テーブルは同じインデックス（連絡先の番号）に関連する値を返します。

データ構造は抽象データ型の具体的な形式を実装するため、ソフトウェア・アプリケーションの設計において非常に重要です。

抽象データ型とは、データ型の動作と、それに対して実行できる操作を分類する数学モデルです。例えば、キューの抽象データ型は、FIFOの原則に従ってキューの動作を定義します。キュー・データ構造は、コンピューター・プログラムがFIFO原則をそのデータに適用できるように、データをキューにフォーマットする手段を提供します。

Python、Java、JavaScriptなどの多くのプログラミング言語には、開発者がより効率的に作業するための組み込みデータ構造が含まれます。

コンピューター・プログラムにおけるデータ構造の一般的なユースケースには、次のようなものがあります。

• データ・ストレージと組織
• インデックス化
• データ交換
• 検索
• 拡張性

データ構造は、高いレベルのデータの永続性でデータを論理的かつ効率的に保管できるため、データベースや他のアプリケーションからデータに簡単にアクセスできます。また、データ構造は大量のデータに論理的な組織化を実現し、データの並べ替え、順序付け、処理をより簡単に行うことができます。

例えば、Webサイトではリンク・リストを使用して、ユーザーのアクティビティー・ログを保管できます。リストにはイベントが時系列で記録され、イベント間のリンクにより、各セッションを通じてユーザーが行った操作の全体像を把握するのに役立ちます。

データ構造は、データ値をデータベース内の対応するデータ項目にマッピングすることで情報をインデックス化できるため、データ・レコードの検索とアクセスが容易になります。

例えば、EコマースのWebサイトでは、ハッシュ・テーブルを使用してカテゴリーごとに商品にインデックスを付けることができます。ユーザーが1つのカテゴリーだけを表示したい場合、Webサイトはハッシュ値を使用して、すべての商品データベースを検索する代わりに、関連するすべての商品情報をすばやく取得できます。

データ構造によってデータが整理されるため、アプリケーション間で簡単にデータを共有できます。例えば、多くのアプリはキューを使用して、TCP/IPなどのプロトコルを介してパケットを管理および送信します。キューは、パケットが作成された順序で送受信することに役立ちます。

データ構造は、アプリケーションやエンドユーザーが理解しやすいようにデータを整理することで、データの検索と場所の特定を容易にします。

例えば、グラフ・データ構造を使用すると、ユーザーはソーシャル・メディア・サイトで知人を簡単に見つけることができます。グラフ・データ構造は、頂点またはノード間の関係を記録します。検索アルゴリズムは、ノードからノードへの接続をたどって、関連するユーザーを効率的に特定することができます。

データ構造は、コンピューター・プログラムが大規模なデータ・セットを処理し、複雑な問題を解決し、リソースをより効率的に使用できるようにすることで、システムの拡張性をサポートします。

例えば、ハッシュ・テーブルと木構造の両方を使用すると、大規模なデータ・セット内の関連情報を見つけやすくなります。すべての要素を検査する代わりに、システムは正しいキーを使用するか、木構造内の正しいパスに従うだけで済みます。これにより、システムは大量のデータを検索するために多くのリソースを割く必要がなくなるため、パフォーマンスを高く維持できます。