コンピューターサイエンス 学び直し データ構造編
今月からコンピューターサイエンスを学び直しているので、そのアウトプットをしようと思います。
そもそも、コンピュータサイエンスとは、「コンピュータを利用して様々な課題を解決する方法を研究する学問」と言えます。
コンピュータサイエンスが扱う分野は、プログラミング言語やフレームワークだけでなく、ハードウェアや設計パターン、アルゴリズムなど多岐にわたります。
これらを組み合わせ、最適な選択をし、社会的学術的な課題を解決していくことが、コンピュータサイエンスの本質です。
今回は、プログラムの基本となる「データ構造」について解説していきます。
データ構造
データ構造は、コンピュータ上でデータを効率的に格納・組織化するための手法や方法のことです。
コンピュータプログラムにおいて、データはさまざまな形式やサイズで表現されますが、それを効率的に操作し、必要な情報を取り出すためには、適切なデータ構造を使用する必要があります。
データ構造は、データの格納方法やアクセス方法、操作方法に関するルールや手順を提供します。
例えば、配列やリスト、スタック、キュー、ツリー、グラフなど、さまざまなデータ構造が存在します。
それぞれのデータ構造は、異なる特性や利点を持ち、特定の目的に最適化されています。
なので、用途に合わせて適切なデータ構造を選ぶ必要があります。
連結リスト
連結リストは、データがメモリ上の連続したブロックに格納されないデータ構造です。
その代わり、データはポインタによって接続された一連のシーケンスで構成されています。
これは、データが連続したメモリに格納される配列とは対照的になります。
連結リストでは、各要素はノードと呼ばれます。
各ノードには、データ要素と次のノードへの参照が格納されます。
この参照によって、あるノードから次のノードにアクセスすることができます。
ノードは一列に連なっており、次のノードへの参照をたどることで、リスト全体をたどることができます。
つまり、あるノードから次のノードへ移動するためには、次のノードへの参照を使います。
これにより、データ要素を順番にたどりながら、リスト全体を走査することができます。
片方向リスト
片方向リストは、連結リストの中でも最も基本的な形態の一つです。
各ノードはデータを格納する変数と、次のノードを指すポインタ変数から構成されています。
次のノードを指すポインタは、リストの最後尾に達した場合には null 値を格納するか、空のリストを指すこともあります。
重要な点として、ノードにおける next 変数には参照（メモリアドレス）が格納されていることに留意する必要があります。
実際に格納されるのは次のノードオブジェクトの参照であり、これを通じて次のノードにアクセスすることができるため、ポインタと呼ばれています。
連結リストは、要素がメモリ上で非連続的に配置されているため、要素にアクセスするためにはポインタをたどる必要があります。
そのため、連結リストのインデックス操作は、i 番目の要素に到達するために、i-1 番目までの全ての要素を辿る必要があります。
この操作は、最悪の場合、リストの長さに比例して O(n) の時間がかかります。
一方、配列では、データが連続的に格納されているため、インデックス演算は O(1) の時間計算量で実行できます。
配列では、指定したインデックスに直接アクセスすることができます。
したがって、連結リストのインデックス操作は配列のインデックス操作よりも効率が悪いと言えます。
配列はそのサイズが固定で、サイズを変更するには新しい、より大きな配列を作成する必要がありました。
一方、連結リストは各ノードが次のノードへの参照（通常はポインタ）を持つシンプルなデータ構造を利用しており、これによりリストのサイズを容易に調整することが可能になります。
連結リストの特性を活用すれば、既知のノードの直後に新しい要素を挿入することは O(1) の時間計算量で可能です。
ただ、既知ではない場合、この操作は O(n) の時間計算量がかかります。
ちなみに、削除する場合も同様です。
双方向リスト
双方向リストは、連結リストの 1 つで、双方向の走査を可能にするものです。
双方向リストでは、各ノードが次のノードへの単一のポインタだけでなく、前のノードへのポインタも含んでいます。
このため、リストを順方向と逆方向の両方で走査することができます。
双方向リストは一般に、片方向リストよりもやや複雑で、より多くのメモリを必要とします。
これは、ノードごとに 1 つだけでなく 2 つのポインタを必要とするからです。
しかし、双方向の探索が必要な場合などには有効になります。
通常リストを使う場合では、配列の方が汎用性が高く、高速で処理を行うことができます。
しかし、グラフ内のポインタなど、連結リストの特性を本質的に使用するアルゴリズム等、連結リストの使用が好まれるケースもあります。
これ以外では、ランダムにデータにアクセスして要素を入れ替えるような時ではなく、多くの要素の挿入や削除を行う場合には連結リストを使うのが一般的です。それは連結リストが動的で、リストを容易に縮小、拡大することができるからです。
スタック
スタックは、LIFO（Last-In-First-Out）の原則に従った線形データ構造です。
スタックに追加された最後の要素が、最初に削除される要素と一致します。
スタックに値を追加することを「プッシュ」取り出すことを「ポップ」と言います。
スタックは配列や連結リストを使用して実装され、幅広い用途で使用されます。
ゲームやアプリの「元に戻す」ボタンは良い例です。
ここで行った操作をスタックに積んでおき、元に戻す時は最後の操作から取り出して消去します。
したがって、直近の操作を撤回することが可能になります。
キュー
キューは、FIFO（First-In-First-Out）の原則に従ったデータ構造です。
これは「最初に入ったものが最初に出てくる」という規則を意味します。
たとえば、スーパーマーケットのレジの行列を想像してみてください。
最初に並んだ人（データ）が最初にレジで会計（削除）されます。これがキューの動作原理です。
キューは配列や連結リストなどのデータ構造を用いて実装することが可能で、受け取ったデータをその順番に処理することが求められる多くの場面で利用されます。
両端キュー
両端キューはその名の通り、両端からデータを追加や削除できるようになったキューです。
一般的なキューでは、データは一端からしか追加できず、もう一方の端からしか削除できません。
一方で、両端キューでは、両端からデータを追加や削除することができるようになっています。
両端キューはデックと呼ばれることもあります。
これは、スタックとキューの両方の操作を行う必要がある場合に、便利なデータ構造になっています。
木構造
次に木構造について解説していきます。
まず、関係が深いグラフについて説明します。
グラフは、コンピュータの計算や解析の重要な道具です。
これは、物事の関係性を視覚的に表現するのにとても役立ちます。
例えば、人々の友人関係やウェブサイト間のリンク、都市間の交通ネットワークなど、生活の中で様々な場面で使われています。
グラフ理論において、個々の要素は頂点またはノード、2 つの要素間の関係は辺と呼ばれます。
グラフの中には、一つの頂点から出発して、同じ頂点に戻ってくるような辺の辿り方ができるものがあります。
これを閉路と呼びます。
しかし、閉路が一つもないグラフ、つまり一つの道を進んだら同じ場所に戻ってくることがないような形状を木構造と呼びます。
これはまるで街を出発点から目的地まで一直線に進む道のりのようなものです。
グラフ
グラフは主に、有向グラフと無向グラフの 2 つに分類されます。
有向グラフとは、頂点と向きを持つ辺（矢印）により構成されたグラフであり、無向グラフとは、頂点と辺により構成されたグラフを指します。
ツリー
グラフ内に特定の構造が形成されることがあります。
これらの構造の中で最も重要なものの一つに木（tree）があります。
木は非環状無向グラフです。
ツリーは非周期的であるため、すべての辺は一度だけ連結されます。
つまり、一つの点からスタートして同じ点に戻ることなく全ての点をたどれる形状を持ちます。
また、閉路を持たないグラフを森と呼びます。
つまり、無向グラフが非周期的で、どこかの点で切断されているならば、それは森と呼ばれ、連結した森は木となります。
ノードの関係
あるノードを選んで、それを一番「上」にあると考えると、そのノードを基準として 2 つのノードに上下の関係を考えることができます。
このとき、その一番上の区別されたノードを根ノードといいます。
そして、このように特定のノードを一番上、つまり「根」として持つ木構造を根付き木と言います。
これは、通常の木構造とは異なり、始点となるノードが明確に定められているためです。
根からノード B に至るまでの経路上にノード A が存在する場合、ノード A をノード B の先祖 、逆にノード B をノード A の子孫と呼びます。
また、ノード X とノード Y が共通の親を持つとき、ノード X とノード Y は兄弟と呼ばれます。
ノードに子がない場合、それは葉ノードと呼ばれます。
葉ノードは木構造の下位の末端にあるノードであり、1 つの木に複数存在することがあります。
部分木
部分木とは、その木構造の一部を切り取ったもので、その切り取った部分もまた頂点と辺で繋がれている小さな木構造になっているものを指します。
例えば、ノード R を根として持つ部分木とは、ノード R と、ノード R から続いている全ての子孫を含んだ部分を指します。
高さとは、あるノードについて、そのノードからその子孫である葉ノードへの辺の数の最大値を指します。
根ノードの高さはその木構造の高さになります。
深さとは、逆に、あるノードについて、そのノードから根ノードまでの辺の数のことを指します。
根ノードの深さは 0 になります。階層とは、深さ x のすべてのノードが存在する領域のことを指します。
まとめ
今回はプログラムの基本となる「データ構造」について解説しました。
今回学んだ知識を使うことで、プログラムをよりわかりやすく、効率的に記述することができます。
引き続き学んだ内容をアウトプットしていこうと思うので、参考にしてください。
宣伝
0からエンジニアになるためのノウハウをブログで発信しています。
また、YouTubeでの動画解説も始めました。
インスタの発信も細々とやっています。
興味がある方は、ぜひリンクをクリックして確認してみてください！
Discussion