プログラムの処理効率アップに意外と重要!データ構造の初歩


プログラムの処理効率アップに意外と重要!データ構造の初歩

効率的なプログラムを作るには、アルゴリズム(処理手順)と同じくらいデータ構造が重要になります。

この記事では配列をはじめとした、初歩的なデータ構造について詳しく解説します。

ちょっとした違いを知るだけで、プログラミングに差が出てきます。ぜひ最後までご覧ください。

目次
  1. データ構造と配列
  2. 配列はすべてのデータ構造の基本
  3. 連想配列は、検索に適したデータ構造
  4. キューとスタック
  5. キュー
  6. スタック
  7. その他のデータ構造と実装
  8. まとめ

データ構造と配列

データを取り出しやすくするために決まった形で配置する方法を、データ構造と呼びます。

さっそく解説していきますね。

配列はすべてのデータ構造の基本

配列は、複数のデータ(変数)を格納するためのデータ構造です。

配列のルールは、格納するデータを同じデータ型(整数型、文字列型など)に統一することです。

配列を利用するときには、あらかじめ格納するデータの数を指定します。配列にデータを格納するには、配列の全体がおさまる連続したメモリー領域の確保が必要なためです。

image

配列に格納された個々のデータを要素と呼び、先頭から順番に通し番号(添字、英語ではindex)がついています。

たとえば"array"という配列の先頭にあるデータを呼び出したいとき、array[0]と記述します。

この呼び出し方は、どのような言語でもほぼ同じです。添字の番号は0からはじまることを覚えておいてください。

配列は一番シンプルなデータ構造です。どのようなデータ構造がよいか迷ったとき、まず配列を使って実装できないか検討しましょう。

同じデータ型で、あらかじめ数が決まっているデータ(例:一週間あたりの日数)なら、配列で実装できます。

連想配列は、検索に適したデータ構造

添字をテキストに置き換えた、連想配列という配列もあります。通常の配列と違い、連想配列では添字に任意の文字列を指定可能です。

連想配列の添字はキーとも呼ばれます。

image

連想配列はキーが文字列型になっているため、対応するデータをプログラム内から直接指定して呼び出しやすいデータ構造です。そのため連想配列は、キーワードで検索したいデータを格納するのに向いています。

キューとスタック

キュースタックは、一時的に複数のデータを格納するためのデータ構造です。このような記憶領域をバッファと呼びます。

プログラミングでバッファを実装するとき、基本的には配列を使います。

キューとスタックの違いは、配列にデータを格納する順番と、配列からデータを取り出す順番です。

キュー

キューは、データを順番に処理するためのデータ構造です。

データを格納する処理の順番は先入れ先出し(First In First Out:FIFO形式)で、日本語に訳すと"待ち行列"という意味になります。

その名のとおり、キャンセル待ちの座席などを処理するのに向いています。

image

プログラミングで実装するときは、配列の末尾にデータを追加し、配列の先頭からデータを取り出すイメージです。

スタック

スタックは、逆から順番にデータを取り出したいときに使うデータ構造です。

最後に入れたデータを先に取り出すため、LIFO形式(Last In First Out)とも呼ばれます。

image

アプリケーションの"元に戻す"(Undo)や、Webブラウザの履歴など、直近のデータにさかのぼる処理に適しています。

スタックを実装するときは、配列の末尾からデータを追加・取り出しをおこなうイメージです。

その他のデータ構造と実装

これまで解説したもの以外にも、さまざまなデータ構造があります。

データ構造は基本的に、配列とポインタを使って実装が可能です。

ポインタは次のデータがどこにあるかを示す特殊なデータで、配列の要素データなど変数と組み合わせて使います。

[主なデータ構造の概要]

データ構造 概要
リスト 配列の要素どうしを、ポインタで数珠つなぎに接続したデータ構造。
配列と似ているが、格納したいデータの個数をあらかじめ決められないときに使う。
ハッシュテーブル 連想配列の添字(テキスト)を数値(ハッシュ値)に変換し、さらに格納方法を工夫してより速く検索できるよう改良したデータ構造。
ヒープ 1つのデータ要素+2つのポインタでつながるツリー状の階層を持つ(木構造二分木)。
データを格納する過程で、大きさを比べ順序をつけたい(ソートしたい)場合に使うデータ構造。
二分探索木 ヒープと同様ツリー状の階層を持つ構造で、あるデータをもとに次のデータを探索し、少ない手順でより速く取り出したいときに使うデータ構造。

利用するアルゴリズムによって、最適なデータ構造は変わります。特に大量のデータを処理する場合には、用途に適したデータ構造を利用すれば処理をより速くおこなうことが可能です。

言語によって配列やリストなどの仕様が違うため、実装するときには使う言語に合った資料を調べましょう。

Webサイト担当者としてのスキルが身に付く

CodeCampの無料体験はこちら

まとめ

データ構造の初歩について解説しました。

プログラムの処理効率を考えるときに注目されやすいのはアルゴリズムですが、格納しやすく取り出しやすいデータ構造にすることも重要です。

アルゴリズムについては、参考になる記事がありますのでご覧になってください。

参考記事:プログラミングに必須のアルゴリズム入門!勉強法についても解説

アルゴリズムとデータ構造について知り、プログラミングに興味がわいたらCodeCampでプログラミングを学んでみませんか?

オンラインの体験レッスンがありますので、お気軽にご相談ください。


関連記事

鳥飼千愛
この記事を書いた人
鳥飼千愛
\ 無料体験開催中!/自分のペースで確実に習得!
オンライン・プログラミングレッスンNo.1のCodeCamp