データ構造の基礎——アルゴリズム効率を支える 4 つの柱

def analyze_time_complexity():
    """計算量の基本概念"""

    complexities = {
        'O(1)': '定数時間（ハッシュマップの検索）',
        'O(log n)': '対数時間（二分探索）',
        'O(n)': '線形時間（配列の線形探索）',
        'O(n log n)': '準線形時間（マージソート）',
        'O(n²)': '二次時間（バブルソート）',
        'O(2ⁿ)': '指数時間（再帰的フィボナッチ）'
    }

    return complexities

# 使用例
complexities = analyze_time_complexity()
for notation, description in complexities.items():
    print(f"{notation}: {description}")

【データ構造選びの指針】

1. 検索が多い場合
   - ハッシュマップ：O(1) 検索
   - 二分探索木：O(log n) 検索

2. 挿入・削除が多い場合
   - リンクリスト：O(1) 挿入・削除（先頭）
   - 動的配列：O(n) 挿入・削除（中間）

3. 順序を維持したい場合
   - 配列：インデックスで順序保持
   - ツリー：ソート済み順序

4. FIFO/LIFO が必要な場合
   - キュー：FIFO（先入れ先出し）
   - スタック：LIFO（後入れ先出し）

class Array:
    """配列の基本概念（Python リスト）"""

    def __init__(self):
        self.data = []

    def append(self, value):
        """末尾に追加：O(1)"""
        self.data.append(value)

    def insert(self, index, value):
        """途中に挿入：O(n)（要素シフトが必要）"""
        self.data.insert(index, value)

    def delete(self, index):
        """削除：O(n)（要素シフトが必要）"""
        del self.data[index]

    def search(self, value):
        """検索：O(n)（線形探索）"""
        try:
            return self.data.index(value)
        except ValueError:
            return -1

    def get(self, index):
        """インデックスアクセス：O(1)"""
        return self.data[index]

# 使用例
arr = Array()
arr.append(10)  # [10]
arr.append(20)  # [10, 20]
arr.append(30)  # [10, 20, 30]
arr.insert(1, 15)  # [10, 15, 20, 30]

print(f"配列：{arr.data}")
print(f"15 のインデックス：{arr.search(15)}")
print(f"インデックス 2 の要素：{arr.get(2)}")

class Node:
    """リンクリストのノード"""

    def __init__(self, value):
        self.value = value
        self.next = None  # 次のノードへのポインタ

class LinkedList:
    """単方向リンクリスト"""

    def __init__(self):
        self.head = None
        self.size = 0

    def prepend(self, value):
        """先頭に追加：O(1)"""
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def append(self, value):
        """末尾に追加：O(n)"""
        new_node = Node(value)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:  # 末尾まで移動：O(n)
                current = current.next
            current.next = new_node
        self.size += 1

    def insert_after(self, target_value, new_value):
        """指定値の後に挿入：O(n)"""
        current = self.head
        while current:
            if current.value == target_value:
                new_node = Node(new_value)
                new_node.next = current.next
                current.next = new_node
                self.size += 1
                return True
            current = current.next
        return False

    def delete(self, value):
        """削除：O(n)"""
        if not self.head:
            return False

        if self.head.value == value:
            self.head = self.head.next
            self.size -= 1
            return True

        current = self.head
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                self.size -= 1
                return True
            current = current.next

        return False

    def search(self, value):
        """検索：O(n)"""
        current = self.head
        index = 0
        while current:
            if current.value == value:
                return index
            current = current.next
            index += 1
        return -1

    def to_list(self):
        """Python リストに変換"""
        result = []
        current = self.head
        while current:
            result.append(current.value)
            current = current.next
        return result

# 使用例
ll = LinkedList()
ll.prepend(30)  # 30
ll.prepend(20)  # 20 → 30
ll.prepend(10)  # 10 → 20 → 30
ll.append(40)   # 10 → 20 → 30 → 40
ll.insert_after(20, 25)  # 10 → 20 → 25 → 30 → 40

print(f"リンクリスト：{ll.to_list()}")
print(f"サイズ：{ll.size}")
print(f"25 のインデックス：{ll.search(25)}")
ll.delete(20)
print(f"削除後：{ll.to_list()}")

def compare_array_vs_linked_list(n=10000):
    """配列とリンクリストのパフォーマンス比較"""
    import time

    # 配列テスト
    arr = []
    start = time.time()
    for i in range(n):
        arr.insert(0, i)  # 先頭挿入
    array_prepend = time.time() - start

    arr = list(range(n))
    start = time.time()
    _ = arr[n // 2]  # 中央アクセス
    array_access = time.time() - start

    # リンクリストテスト
    ll = LinkedList()
    start = time.time()
    for i in range(n):
        ll.prepend(i)  # 先頭挿入
    linked_prepend = time.time() - start

    start = time.time()
    _ = ll.search(n // 2)  # 中央アクセス
    linked_access = time.time() - start

    return {
        '先頭挿入（配列）': f"{array_prepend:.4f}秒",
        '先頭挿入（リンクリスト）': f"{linked_prepend:.4f}秒",
        '中央アクセス（配列）': f"{array_access:.6f}秒",
        '中央アクセス（リンクリスト）': f"{linked_access:.4f}秒"
    }

# 使用例（小規模でテスト）
results = compare_array_vs_linked_list(1000)
for operation, time_taken in results.items():
    print(f"{operation}: {time_taken}")

class Stack:
    """スタック（後入れ先出し：LIFO）"""

    def __init__(self):
        self.items = []

    def push(self, value):
        """プッシュ：O(1)"""
        self.items.append(value)

    def pop(self):
        """ポップ：O(1)"""
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        """トップ要素確認：O(1)"""
        if not self.is_empty():
            return self.items[-1]
        return None

    def is_empty(self):
        """空判定：O(1)"""
        return len(self.items) == 0

    def __len__(self):
        return len(self.items)

# 使用例：バックトラック（行き止まり検出）
def solve_maze_with_stack(maze, start, end):
    """スタックを使った迷路探索（深さ優先探索）"""
    stack = Stack()
    stack.push((start, [start]))  # (現在位置，経路)
    visited = set()

    while len(stack) > 0:
        (current, path) = stack.pop()

        if current == end:
            return path

        if current in visited:
            continue

        visited.add(current)

        # 隣接セルをスタックにプッシュ
        for neighbor in get_neighbors(maze, current):
            if neighbor not in visited:
                stack.push((neighbor, path + [neighbor]))

    return None  # 経路なし

def get_neighbors(maze, pos):
    """迷路の隣接セル取得（簡易版）"""
    x, y = pos
    neighbors = []
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]):
            if maze[nx][ny] == 0:  # 0=通路
                neighbors.append((nx, ny))
    return neighbors

# 使用例
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]

path = solve_maze_with_stack(maze, (0, 0), (4, 4))
print(f"経路：{path}")

【スタックのユースケース】

1. 関数呼び出し（コールスタック）
   - 再帰呼び出しの管理
   - ローカル変数の保存

2. 式の評価
   - 逆ポーランド記法
   - 括弧の整合性チェック

3. バックトラック
   - 迷路探索
   - パズルSolver

4. 履歴管理
   - ブラウザの「戻る」ボタン
   - テキストエディタの Undo

from collections import deque

class Queue:
    """キュー（先入れ先出し：FIFO）"""

    def __init__(self):
        self.items = deque()  # 両端キュー：O(1) 操作

    def enqueue(self, value):
        """エンキュー：O(1)"""
        self.items.append(value)

    def dequeue(self):
        """デキュー：O(1)"""
        if not self.is_empty():
            return self.items.popleft()
        return None

    def front(self):
        """先頭要素確認：O(1)"""
        if not self.is_empty():
            return self.items[0]
        return None

    def is_empty(self):
        """空判定：O(1)"""
        return len(self.items) == 0

    def __len__(self):
        return len(self.items)

# 使用例：幅優先探索（BFS）
def shortest_path_bfs(maze, start, end):
    """キューを使った最短経路探索（幅優先探索）"""
    queue = Queue()
    queue.enqueue((start, [start]))
    visited = set()

    while len(queue) > 0:
        (current, path) = queue.dequeue()

        if current == end:
            return path

        if current in visited:
            continue

        visited.add(current)

        # 隣接セルをキューにエンキュー
        for neighbor in get_neighbors(maze, current):
            if neighbor not in visited:
                queue.enqueue((neighbor, path + [neighbor]))

    return None  # 経路なし

# 使用例
path = shortest_path_bfs(maze, (0, 0), (4, 4))
print(f"最短経路：{path}")

【キューのユースケース】

1. タスクスケジューリング
   - OS のプロセス管理
   - 印刷ジョブ管理

2. 幅優先探索（BFS）
   - 最短経路探索
   - ソーシャルネットワーク（友達の友達）

3. メッセージキュー
   - 非同期処理
   - ワークキュー

4. バッファリング
   - ストリーミング再生
   - 入出力バッファ

def compare_stack_vs_queue():
    """スタックとキューの動作比較"""

    print("【スタック（LIFO）】")
    stack = Stack()
    for i in range(1, 4):
        stack.push(i)
        print(f"プッシュ：{i} → {stack.items}")

    while len(stack) > 0:
        print(f"ポップ：{stack.pop()} → {stack.items}")

    print("\n【キュー（FIFO）】")
    queue = Queue()
    for i in range(1, 4):
        queue.enqueue(i)
        print(f"エンキュー：{i} → {list(queue.items)}")

    while len(queue) > 0:
        print(f"デキュー：{queue.dequeue()} → {list(queue.items)}")

compare_stack_vs_queue()

class HashMap:
    """ハッシュマップ（辞書）の基本概念"""

    def __init__(self, capacity=16):
        self.capacity = capacity
        self.buckets = [[] for _ in range(capacity)]  # 衝突はチェイン法
        self.size = 0

    def _hash(self, key):
        """ハッシュ関数"""
        return hash(key) % self.capacity

    def put(self, key, value):
        """挿入：平均 O(1)"""
        index = self._hash(key)
        bucket = self.buckets[index]

        # 既存キー更新
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return

        # 新規追加
        bucket.append((key, value))
        self.size += 1

        # リサイズ（簡易版）
        if self.size > self.capacity * 0.75:
            self._resize()

    def get(self, key):
        """検索：平均 O(1)"""
        index = self._hash(key)
        bucket = self.buckets[index]

        for k, v in bucket:
            if k == key:
                return v

        raise KeyError(key)

    def remove(self, key):
        """削除：平均 O(1)"""
        index = self._hash(key)
        bucket = self.buckets[index]

        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return True

        return False

    def _resize(self):
        """リサイズ：O(n)"""
        old_buckets = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0

        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)

    def __len__(self):
        return self.size

    def __repr__(self):
        items = []
        for bucket in self.buckets:
            for key, value in bucket:
                items.append(f"{key}: {value}")
        return "{" + ", ".join(items) + "}"

# 使用例
hm = HashMap()
hm.put("name", "Alice")
hm.put("age", 30)
hm.put("city", "Tokyo")

print(f"ハッシュマップ：{hm}")
print(f"name: {hm.get('name')}")
print(f"age: {hm.get('age')}")

hm.remove("city")
print(f"削除後：{hm}")

class TreeNode:
    """二分探索木のノード"""

    def __init__(self, value):
        self.value = value
        self.left = None   # 小さい値
        self.right = None  # 大きい値

class BinarySearchTree:
    """二分探索木"""

    def __init__(self):
        self.root = None

    def insert(self, value):
        """挿入：平均 O(log n)、最悪 O(n)"""
        self.root = self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        """再帰的挿入"""
        if node is None:
            return TreeNode(value)

        if value < node.value:
            node.left = self._insert_recursive(node.left, value)
        elif value > node.value:
            node.right = self._insert_recursive(node.right, value)
        # 重複は挿入しない

        return node

    def search(self, value):
        """検索：平均 O(log n)、最悪 O(n)"""
        return self._search_recursive(self.root, value)

    def _search_recursive(self, node, value):
        """再帰的検索"""
        if node is None:
            return False

        if node.value == value:
            return True
        elif value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)

    def delete(self, value):
        """削除：平均 O(log n)、最悪 O(n)"""
        self.root = self._delete_recursive(self.root, value)

    def _delete_recursive(self, node, value):
        """再帰的削除"""
        if node is None:
            return None

        if value < node.value:
            node.left = self._delete_recursive(node.left, value)
        elif value > node.value:
            node.right = self._delete_recursive(node.right, value)
        else:
            # 削除対象発見

            # 子なし
            if node.left is None and node.right is None:
                return None

            # 右子のみ
            if node.left is None:
                return node.right

            # 左子のみ
            if node.right is None:
                return node.left

            # 両方あり：右部分木の最小値で置換
            min_value = self._find_min(node.right)
            node.value = min_value
            node.right = self._delete_recursive(node.right, min_value)

        return node

    def _find_min(self, node):
        """最小値探索"""
        while node.left:
            node = node.left
        return node.value

    def inorder_traversal(self):
        """中間順走査：ソート済み順序"""
        result = []
        self._inorder_recursive(self.root, result)
        return result

    def _inorder_recursive(self, node, result):
        """再帰的中間順走査"""
        if node:
            self._inorder_recursive(node.left, result)
            result.append(node.value)
            self._inorder_recursive(node.right, result)

# 使用例
bst = BinarySearchTree()
for value in [50, 30, 70, 20, 40, 60, 80]:
    bst.insert(value)

print(f"ソート済み：{bst.inorder_traversal()}")
print(f"40 を検索：{bst.search(40)}")  # True
print(f"25 を検索：{bst.search(25)}")  # False

bst.delete(30)
print(f"削除後：{bst.inorder_traversal()}")

def analyze_tree_balance():
    """木の平衡状態による性能差"""

    # 平衡な木の場合（log₂100万 ≈ 20）
    balanced_height = 20
    print(f"平衡な木（100 万要素）：最大{balanced_height}回の比較")

    # 偏った木の場合（100 万）
    skewed_height = 1_000_000
    print(f"偏った木（100 万要素）：最大{skewed_height}回の比較")

    print(f"\n性能差：{skewed_height / balanced_height}倍")

analyze_tree_balance()

【主要な平衡木】

1. AVL 木
   - 部分木の高さ差 ≤ 1
   - 厳密な平衡、検索重視

2. 赤黒木
   - 緩和された平衡
   - 挿入・削除頻繁な場合に有利
   - Java TreeMap、C++ std::map

3. B 木
   - 多分探索木
   - ディスクアクセス最小化
   - データベースインデックス

def choose_data_structure(requirements):
    """要件に基づいてデータ構造を選択"""

    decision_tree = {
        'key_value_pairs': {
            'order_matters': 'OrderedDict（Python 3.7+ は dict）',
            'order_not_matters': 'dict（ハッシュマップ）',
            'sorted_keys': 'SortedDict または 二分探索木'
        },
        'ordered_collection': {
            'frequent_access': 'list（配列）',
            'frequent_insert_delete_start': 'collections.deque（リンクリスト）',
            'frequent_insert_delete_middle': 'list（ただし O(n)）'
        },
        'special_requirements': {
            'fifo': 'queue.Queue（キュー）',
            'lifo': 'list（スタック）',
            'priority': 'heapq（ヒープ）',
            'unique_elements': 'set（ハッシュセット）',
            'fast_lookup': 'dict（ハッシュマップ）'
        }
    }

    return decision_tree

# 使用例
ds = choose_data_structure({})
print("【キー・バリュー】")
for req, structure in ds['key_value_pairs'].items():
    print(f"- {req}: {structure}")

print("\n【順序付きコレクション】")
for req, structure in ds['ordered_collection'].items():
    print(f"- {req}: {structure}")

print("\n【特殊要件】")
for req, structure in ds['special_requirements'].items():
    print(f"- {req}: {structure}")

def compare_all_data_structures():
    """全データ構造のパフォーマンス比較"""

    comparison = """
【データ構造の計算量比較】

                | 検索   | 挿入   | 削除   | アクセス
----------------|--------|--------|--------|--------
配列（list）     | O(n)   | O(n)   | O(n)   | O(1)
リンクリスト     | O(n)   | O(1)*  | O(1)*  | O(n)
スタック        | -      | O(1)   | O(1)   | O(1)**
キュー          | -      | O(1)   | O(1)   | O(1)**
ハッシュマップ   | O(1)   | O(1)   | O(1)   | -
二分探索木      | O(log n)| O(log n)| O(log n)| -

* 先頭の場合
** トップ/先頭のみ

【メモリ効率比較】

                | メモリ効率 | キャッシュ効率
----------------|-----------|---------------
配列            | 高        | 高（連続）
リンクリスト     | 中        | 低（分散）
ハッシュマップ   | 中        | 中
ツリー          | 中        | 低
    """

    return comparison

print(compare_all_data_structures())

def demonstrate_hash_collisions():
    """ハッシュ衝突による性能劣化"""

    # 悪いハッシュ関数（常に同じ値を返す）
    class BadHashMap:
        def __init__(self):
            self.bucket = []  # 1 つのバケットに全部

        def put(self, key, value):
            self.bucket.append((key, value))  # 全部追加

        def get(self, key):
            for k, v in self.bucket:  # 線形探索：O(n)
                if k == key:
                    return v
            raise KeyError(key)

    # 1000 件插入
    bad_map = BadHashMap()
    for i in range(1000):
        bad_map.put(f"key_{i}", i)

    # 検索は O(n) に劣化
    import time
    start = time.time()
    for i in range(1000):
        _ = bad_map.get(f"key_{i}")
    elapsed = time.time() - start

    print(f"悪いハッシュマップ：{elapsed:.4f}秒（O(n²)）")

demonstrate_hash_collisions()

【配列の種類】

固定長配列（C 言語など）:
・コンパイル時にサイズ決定
・メモリ効率良し
・サイズ変更不可

動的配列（Python list）:
・実行時にサイズ変更
・内部で 2 倍戦略（amortized O(1)）
・メモリ効率は中程度

def demonstrate_skewed_tree():
    """偏った二分探索木の例"""

    bst = BinarySearchTree()

    # ソート済みデータ插入→右に偏る
    for i in range(1, 11):
        bst.insert(i)

    # 木の高さ：10（O(n)）
    print(f"要素数：10, 木の高さ：10")
    print(f"検索計算量：O(n) に劣化")

    # 対策：平衡木（AVL、赤黒木）を使用

demonstrate_skewed_tree()