データ構造（配列・リスト・木構造）とは？わかりやすく解説

データ構造（配列・リスト・木構造）をイメージでつかむ

配列はデータを連続して並べ、何番目かを表す番号（添字）を指定して直接読み書きします。リストは各データが次のデータの位置（ポインタ）をもってつながり、途中への挿入や削除はポインタの付け替えだけで済みます。木構造は根から枝分かれして階層を表す構造で、子が最大2つの木を2分木と呼びます。

たとえると：配列は番号の付いたロッカー（5番をすぐ開けられる）、リストは「次はあの人」と指名していく伝言ゲームの列、木構造は家系図やパソコンのフォルダです。

配列は、同じ種類のデータを連続した領域に並べ、何番目かを表す番号（添字、要素番号）を指定して目的の要素を直接読み書きするデータ構造です。表計算のセルや、擬似言語の問題で使う変数の並びがこれに当たります（何番から数えるかは問題文の指示に従います）。途中に新しいデータを挿入したり削除したりするときは、後ろの要素を1つずつずらす必要があります。リスト（連結リスト）は、各要素がデータと「次の要素の位置」を表すポインタをもち、ポインタでつながったデータ構造です。途中への挿入や削除は、前後の要素のポインタを付け替えるだけで済みますが、n番目の要素を読むときは先頭から順にポインタをたどる必要があります。次の要素だけを指す単方向リストのほか、前の要素も指す双方向リストがあります。木構造は、1つの根（ルート）から枝分かれして階層を表すデータ構造で、途中の要素を節（ノード）、子をもたない末端の要素を葉（リーフ）と呼びます。上下の関係は親と子で表し、どの節も子を最大2つまでしかもたない木を2分木と呼びます。フォルダの構成や組織図が身近な例です。

押さえどころ

• 配列＝添字で直接読み書きできる。途中に挿入すると後ろの要素をずらす必要がある
• リスト＝ポインタでつながる。挿入・削除はポインタの付け替えだけ、読むときは先頭からたどる
• 木構造＝根・節・葉で階層を表す。子が最大2つなら2分木