必須基礎知識、データ構造を理解しよう！配列や連結リストなどの入門書

最終更新日 2023年5月26日

ITエンジニアの必須知識であるデータ構造について、配列や連結リストなどを理解し、その魅力に迫ります。
このコンテンツでは例としてPython3を使用します。

データ構造の基本的な構成要素

データ構造は、データを効率的なアクセスと操作ができるように、データを組織化し保存する方法です。データの収集、アクセス、使用方法を決定するため、優れたソフトウェアシステムの根幹を形成します。例えば、データ構造はデータを保存するための青写真のようなものです。Pythonでは、リスト、タプル、セット、辞書などのデータ構造が組み込まれています。

# リストの例
my_list = [1, 2, 3, 4, 5]
print(my_list)

データ構造とは

データ構造とは、簡単に言うとデータをまとめるための構造です。データを特定のレイアウトで保存するためのコンテナとして機能します。このレイアウトによって、データを特定の方法で処理できます。データ構造にはさまざまな種類があり、それぞれデータの整理と管理を効率的に行うために設計されています。例えば、Pythonでは配列データ構造は同じデータ型の複数の項目を格納でき、そのインデックスを介して各項目にアクセスできます。

# 配列の例
import array
my_array = array.array('i', [1, 2, 3, 4, 5])
for i in my_array:
    print(i)

なぜITエンジニアはデータ構造について学ぶ必要があるのか

データ構造を理解することはITやプログラミングの分野で活躍しようとする人にとって基本的なことです。適切なデータ構造を使用することで、ソフトウェアアプリケーションの性能を大幅に向上させることができます。さらに、コンピュータサイエンスとプログラミングの領域における多くの問題は、データ構造を正しく理解し適用することでより簡単に解決できます。

# データ構造はプログラムのパフォーマンス向上と問題解決の効率化に役立つ
# 例: setの使用で重複しない要素を見つける
my_list = [1, 2, 2, 3, 4, 4, 5, 5]
unique_elements = set(my_list)
print(unique_elements)  # 出力: {1, 2, 3, 4, 5}

配列の簡便性と効率性

配列はコンピュータサイエンスにおいて最もシンプルで最もよく使われるデータ構造の1つです。配列は同じ種類のアイテムを保持できる連続したメモリのブロックとして機能します。この連続したストレージの性質により、配列の要素にアクセスする際には目的の要素のインデックスを参照するだけでよいので非常に高速で簡単です。

# Pythonで配列を作る例
import array
arr = array.array('i', [1, 2, 3, 4])
print(arr[2])  # 出力: 3

配列とは

データ構造における配列とは、少なくとも1つの配列インデックスまたはキーによって識別される要素（値または変数）の集合体のことです。配列の主な特徴は、1つの変数に複数の値を格納しそれぞれのインデックスを介してアクセスできることです。Pythonでは配列の組み込みサポートはありませんが、リストやarrayモジュールを使って同様の機能を実現できます。

# リストを配列として扱う
my_list = [10, 20, 30, 40, 50]
print(my_list[3])  # 出力: 40

配列のメリットとデメリット

配列にはいくつかの利点があります。インデックスを利用したランダムアクセスが可能なため要素へのアクセスが高速になります。また、キャッシュの局所性も高いため、スピードとパフォーマンスが向上します。しかし、配列にはいくつかの制約もあります。配列の場合、同じ型しか配列内に加えられない他、作れるのは1次元配列のみとなります。

# 配列内の型を複数にしたらエラーになる
import array
arr = array.array('i', [1, 'hello', {}])
# 出力:
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# TypeError: an integer is required (got type str)

この例では、配列の最初の要素に整数を持っているため、その後の文字列や辞書型の値は加えることができません。ある種のアプリケーションでは制限になる可能性があります。しかし、Pythonのリストはこの点でより柔軟性を持っています。

連結リストとは

連結リストは、配列とは異なり連続したメモリ位置に格納されません。各ノードには値と次のノードへの参照（リンク）が含まれています。最後のノードはリストの終わりを意味するnull値にリンクしています。連結リストは動的であるため、実行中にサイズを変更でき、要素の追加や削除に柔軟に対応できます。

# 単純な連結リストの例
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self, head=None):
        self.head = head

    def insert(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

my_list = LinkedList()
my_list.insert(1)
my_list.insert('Hello')
my_list.insert('World')
my_list.print_list()
# 出力:
# World
# Hello
# 1
# (空白)

連結リストの特徴

連結リストでは、各要素はdataとnextという2つのフィールドからなるノードと呼ばれる個別のオブジェクトに格納されています。dataフィールドには要素が格納され、nextフィールドにはリスト内の次のノードへのリンクが格納されます。連結リストはこのnextリンクを介してノードを接続することで形成されます。

# 連結リストへの要素の追加
def append(self, data):
    new_node = Node(data)
    if self.head.data is None:
        self.head = new_node
    else:
        cur_node = self.head
        while cur_node.next is not None:
            cur_node = cur_node.next
        cur_node.next = new_node

LinkedList.append = append
my_list.append(1)
my_list.append(2)

配列と連結リストを比較する

配列と連結リストはどちらも基本的なデータ構造ですが、その用途は異なります。配列はランダムアクセスに適しており、1要素あたりのメモリ使用量が少なくて済みます（追加の参照を保存する必要がないため）が、そのサイズは作成時に固定されます。一方、連結リストは動的であり、挿入や削除を効率的に行うことができますが、要素にアクセスするにはリストの先頭から順に走査する必要があります。

# 連結リストから削除
def delete(self, data):
    cur_node = self.head
    if cur_node.data == data:
        self.head = cur_node.next
    else:
        while cur_node is not None:
            if cur_node.data == data:
                prev_node.next = cur_node.next
                return
            prev_node = cur_node
            cur_node = cur_node.next

LinkedList.delete = delete
my_list.delete(1)

これは、連結リストの削除が配列に比べて容易であることを表しています。

LIFOとFIFOの原則からスタックとキューを理解する

スタックとキューは、より複雑なタイプのデータ構造であり特定の種類の操作を可能にします。

スタックはLIFO原則（Last In, First Out）に従っており、これは最近追加された要素が最初に取り除かれることを意味します。本の積み重ねを考えてみてください。一番上に置いた最後の本が一番最初に取り出されるのです。

対するキューは、FIFO原則（First In, Fist Out）に従っているため、金太郎飴のように入れ込んだ材料からカット（削除）されていきます。

スタックについて

スタックとは、LIFO（Last-in First-out）の原則に従って挿入・除去されるオブジェクトのコンテナのことです。プッシュダウンスタックでは、アイテムをスタックにプッシュしアイテムをスタックからポップするという2つの操作のみが許可されています。これは特定の順序で要素の追加と削除を可能にする単純なデータ構造です。

# リストを使ったスタックの例
stack = []
stack.append('a')
stack.append('b')
stack.append('c')
print('最初のスタック:', stack)
print('スタックから要素を削除:')
print(stack.pop())
print(stack.pop())
print('削除後のスタック:', stack)

キューを理解する

キューは、スタックとは異なりFIFO（First In, First Out）の原則に従っています。アイテムは後方から追加され、前方から取り除かれます。

# リストを使ったキューの例
queue = []
queue.append('1')
queue.append('2')
queue.append('3')
print('最初のキュー:', queue)
print('キューから要素をデキュー（削除）する:')
print(queue.pop(0))
print(queue.pop(0))
print('削除後のキュー:', queue)

スタックとキューの違い

スタックとキューはどちらも要素を保存するものですが、その運用原理は大きく異なっています。

スタックでは、最後に追加された要素（スタックの一番上）が最初に出てくることになります。一方、キューでは最初に追加された要素（待ち行列の最後尾）が最初に出てきます。スタックのこのLIFO特性は、バックトラック法のような特定のシナリオで有用であり、キューのFIFO特性はCPUスケジューリングや印刷要求のような状況に最適です。

ツリー構造＝木構造（tree）の複雑さを理解する

プログラミングの世界では、木（tree）は緑でもなく葉っぱもありませんが、ITの世界では欠かすことのできないデータ構造です。treeは、ノード（枝葉）をエッジ（端っこ）によってつないだものでサイクルはありません。ルートノード（根幹）があり、ルートを除くすべてのノードは上位のノードからちょうど1本のエッジでつながっています。

# ノードを使ったツリー構造のシンプルな例
class Node:
    def __init__(self, data):
        self.data = data
        self.children = []

root = Node('root')
child1 = Node('child1')
child2 = Node('child2')
root.children.append(child1)
root.children.append(child2)

データ構造におけるツリーとは

ツリー構造は、要素（ノードともいう）を親子関係で格納する階層的なデータ構造です。最上位のノードはルートと呼ばれ、ある要素の直下にある要素はその子要素となります。ツリーの各ノードはそれ自身のサブツリーを持ち、枝分かれして要素間の複雑な関係を表現します。

# ツリー構造のノードへアクセス
print('ルートノード:', root.data)
print('子要素:', [child.data for child in root.children])

二分木（バイナリーツリー）と二分探索木（バイナリーサーチツリー）

二分木（バイナリーツリー）とは、各ノードが最大2つの子を持つツリーの一種で、その子要素は左ノードと右ノードと呼ばれます。二分探索木（バイナリーサーチツリー=BST）は、各ノードに対してその左サブツリーの要素はそのノードより小さく、右サブツリーの要素は大きいという特性を持つ二分木です。

# シンプルな二分木
class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

root = Node(8)
root.left = Node(3)
root.right = Node(10)
root.left.left = Node(1)
root.left.right = Node(6)
root.right.right = Node(14)

# 二分木の要素へアクセス
print('ルートノード:', root.data)
print('左ノード:', root.left.data)
print('右ノード:', root.right.data)

全ノード走査や二分木のノード検索には、深さ優先探索や幅優先探索などの異なる走査アルゴリズムや、二分木の特別なインオーダー、プレオーダー、ポストオーダートラバースを理解する必要があります。

グラフを理解する

グラフは木をより一般化したものでデータ構造の中で最も柔軟なものです。人、Webページ、町など、あらゆるものの間の複雑な関係を表現できます。グラフは、頂点（ノード）の集合で、木構造で見られるような階層的な制約を受けずにエッジで相互接続できます。

# 隣接リストを使ったグラフのシンプルな例
class Graph:
    def __init__(self):
        self.graph = dict()

    def add_edge(self, node, neighbour):
        if node not in self.graph:
            self.graph[node] = [neighbour]
        else:
            self.graph[node].append(neighbour)

graph = Graph()
graph.add_edge('A', 'B')
graph.add_edge('B', 'C')
graph.add_edge('A', 'C')
print(graph.graph)
# 出力: {'A': ['B', 'C'], 'B': ['C']}

グラフで表現できる高度なデータ構造

グラフとはノードの集合体であり、そのノードのペアの集合体でありエッジと呼ばれるものです。エッジはノード間の関係を表します。グラフには、エッジがどの方向にも向かない無向グラフとエッジに方向性がある有向グラフ（ディグラフ）の2種類が存在します。

# 有向グラフにエッジを追加する
graph.add_edge('C', 'A')  # 注意: これはAからCへのつながりを意味しません
print(graph.graph)

実世界の問題におけるグラフの有用性

グラフは非常に汎用性が高く、下記例のような実世界のさまざまな問題で利用されています。これらの実世界の問題では、最短経路を求めたり、サイクルを検出したりすることが多く、いずれもグラフに関する共通の問題です。

ソーシャルネットワーク: 人をノード、友人関係をエッジとして表現
Webページ: ページをノード、ハイパーリンクをエッジとして表現
経路計画: 場所をノード、道路をエッジとして表現

# あるノードへのつながりを見つける例
def find_connections(graph, node):
    return graph.graph.get(node, [])

print('Aへのつながり:', find_connections(graph, 'A'))

注: このコードは、ノード'A'のすべての直接接続を表示します。間接的な接続やノード間の最短経路を探索するには、ダイクストラのアルゴリズムや幅優先探索（BFS）のようなより複雑なアルゴリズムが必要です。