データ構造の完全ガイド——配列から木・グラフまで実装で理解する

# Python のリスト（動的配列）
arr = [10, 20, 30, 40, 50]

# インデックスアクセス - O(1)
print(arr[2])  # 30

# 末尾への追加 - 平均 O(1)（amortized）
arr.append(60)

# 途中への挿入 - O(n)（要素をシフトする必要あり）
arr.insert(2, 25)  # [10, 20, 25, 30, 40, 50, 60]

# 削除 - O(n)
arr.remove(30)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def append(self, data):
        """末尾に追加 - O(n)"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:  # 末尾まで辿る必要あり
                current = current.next
            current.next = new_node
        self.size += 1

    def insert(self, index, data):
        """途中に挿入 - O(n)"""
        new_node = Node(data)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
        else:
            current = self.head
            for _ in range(index - 1):
                if current is None:
                    raise IndexError("Index out of range")
                current = current.next
            new_node.next = current.next
            current.next = new_node
        self.size += 1

    def delete(self, data):
        """値で削除 - O(n)"""
        current = self.head
        prev = None

        while current:
            if current.data == data:
                if prev:
                    prev.next = current.next
                else:
                    self.head = current.next
                self.size -= 1
                return True
            prev = current
            current = current.next
        return False

    def search(self, data):
        """線形探索 - O(n)"""
        current = self.head
        index = 0
        while current:
            if current.data == data:
                return index
            current = current.next
            index += 1
        return -1

class SentinelLinkedList:
    """番兵（ダミーノード）を使った実装"""
    def __init__(self):
        self.head = Node(None)  # 番兵
        self.head.next = self.head  # 循環リスト

    def append(self, data):
        """O(1) - 番兵があるので境界条件不要"""
        new_node = Node(data)
        new_node.next = self.head.next
        self.head.next = new_node

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

    def push(self, item):
        """積み込み - O(1)"""
        self.items.append(item)

    def pop(self):
        """取り出し - O(1)"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items.pop()

    def peek(self):
        """頂上要素の確認 - O(1)"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

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

# 使用例
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 3
print(stack.pop())  # 2

def is_valid_parentheses(s: str) -> bool:
    """括弧の整合性をスタックでチェック"""
    stack = Stack()
    pairs = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in '({[':
            stack.push(char)
        elif char in ')}]':
            if stack.is_empty() or stack.pop() != pairs[char]:
                return False

    return stack.is_empty()

# テスト
print(is_valid_parentheses("()[]{}"))  # True
print(is_valid_parentheses("(]"))      # False
print(is_valid_parentheses("([)]"))    # False
print(is_valid_parentheses("{[]}"))    # True

def factorial_recursive(n):
    """再帰版 - スタックオーバーフローのリスク"""
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)

def factorial_iterative(n):
    """スタックを使った反復版 - 安全"""
    stack = Stack()

    # 積む
    while n > 1:
        stack.push(n)
        n -= 1

    # 出し掛け算
    result = 1
    while not stack.is_empty():
        result *= stack.pop()

    return result

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        """追加 - O(1)"""
        self.items.append(item)

    def dequeue(self):
        """取り出し - O(1)"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.items.popleft()

    def peek(self):
        """先頭要素の確認 - O(1)"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

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

# 使用例
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # 1
print(queue.dequeue())  # 2

from collections import deque

def bfs(graph, start):
    """キューを使った幅優先探索"""
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

# グラフ例
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

import heapq

# ヒープは最小要素が先頭に来る
heap = []
heapq.heappush(heap, (2, "タスク B"))
heapq.heappush(heap, (1, "タスク A"))  # 優先度 1 が最高
heapq.heappush(heap, (3, "タスク C"))

print(heapq.heappop(heap))  # (1, "タスク A")
print(heapq.heappop(heap))  # (2, "タスク B")

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

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

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

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

        # なければ追加
        bucket.append((key, value))

        # ロードファクターが閾値を超えたらリハッシュ
        if self._load_factor() > 0.75:
            self._resize()

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

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

        raise KeyError(f"Key not found: {key}")

    def delete(self, key):
        """削除 - 平均 O(1)"""
        index = self._hash(key)
        bucket = self.table[index]

        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return v

        raise KeyError(f"Key not found: {key}")

    def _load_factor(self):
        """ロードファクター = 要素数 / バケット数"""
        n_elements = sum(len(bucket) for bucket in self.table)
        return n_elements / self.size

    def _resize(self):
        """リハッシュ - O(n)"""
        old_table = self.table
        self.size *= 2
        self.table = [[] for _ in range(self.size)]

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

def count_words(text):
    """ハッシュテーブルで単語頻度をカウント"""
    word_count = {}  # Python の dict はハッシュテーブル実装

    for word in text.lower().split():
        word = word.strip(".,!?")
        word_count[word] = word_count.get(word, 0) + 1

    return word_count

text = "Hello world. Hello Python. World is great."
print(count_words(text))
# {'hello': 2, 'world': 2, 'python': 1, 'is': 1, 'great': 1}

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def inorder(self, node, result=None):
        """中間順走査（左→根→右）"""
        if result is None:
            result = []
        if node:
            self.inorder(node.left, result)
            result.append(node.value)
            self.inorder(node.right, result)
        return result

    def preorder(self, node, result=None):
        """先行順走査（根→左→右）"""
        if result is None:
            result = []
        if node:
            result.append(node.value)
            self.preorder(node.left, result)
            self.preorder(node.right, result)
        return result

    def postorder(self, node, result=None):
        """後行順走査（左→右→根）"""
        if result is None:
            result = []
        if node:
            self.postorder(node.left, result)
            self.postorder(node.right, result)
            result.append(node.value)
        return result

# 使用例
#       1
#      / \
#     2   3
#    / \
#   4   5
tree = BinaryTree()
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.left.left = TreeNode(4)
tree.root.left.right = TreeNode(5)

print(tree.inorder(tree.root))    # [4, 2, 5, 1, 3]
print(tree.preorder(tree.root))   # [1, 2, 4, 5, 3]
print(tree.postorder(tree.root))  # [4, 5, 2, 3, 1]

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        """挿入 - 平均 O(log n), 最悪 O(n)"""
        def _insert(node, value):
            if node is None:
                return TreeNode(value)
            if value < node.value:
                node.left = _insert(node.left, value)
            else:
                node.right = _insert(node.right, value)
            return node

        self.root = _insert(self.root, value)

    def search(self, value):
        """検索 - 平均 O(log n), 最悪 O(n)"""
        def _search(node, value):
            if node is None:
                return False
            if node.value == value:
                return True
            if value < node.value:
                return _search(node.left, value)
            return _search(node.right, value)

        return _search(self.root, value)

    def delete(self, value):
        """削除 - 平均 O(log n), 最悪 O(n)"""
        def _delete(node, value):
            if node is None:
                return None

            if value < node.value:
                node.left = _delete(node.left, value)
            elif value > node.value:
                node.right = _delete(node.right, value)
            else:  # 削除対象発見
                # 子が 0 個または 1 個
                if node.left is None:
                    return node.right
                if node.right is None:
                    return node.left

                # 子が 2 個：右部分木の最小値で置き換え
                min_node = self._find_min(node.right)
                node.value = min_node.value
                node.right = _delete(node.right, min_node.value)

            return node

        self.root = _delete(self.root, value)

    def _find_min(self, node):
        while node.left:
            node = node.left
        return node

class MinHeap:
    def __init__(self):
        self.heap = []

    def push(self, value):
        """挿入 - O(log n)"""
        self.heap.append(value)
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        """最小要素の取り出し - O(log n)"""
        if not self.heap:
            raise IndexError("Heap is empty")

        min_val = self.heap[0]
        last = self.heap.pop()

        if self.heap:
            self.heap[0] = last
            self._sift_down(0)

        return min_val

    def _sift_up(self, index):
        """親へ上がる"""
        while index > 0:
            parent = (index - 1) // 2
            if self.heap[index] < self.heap[parent]:
                self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
                index = parent
            else:
                break

    def _sift_down(self, index):
        """子へ下がる"""
        n = len(self.heap)
        while True:
            smallest = index
            left = 2 * index + 1
            right = 2 * index + 2

            if left < n and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < n and self.heap[right] < self.heap[smallest]:
                smallest = right

            if smallest != index:
                self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
                index = smallest
            else:
                break

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

import heapq
from math import inf

def dijkstra(graph, start):
    """ヒープを使った最短経路探索 - O((V+E)log V)"""
    dist = {node: inf for node in graph}
    dist[start] = 0
    pq = [(0, start)]  # (距離，ノード)

    while pq:
        d, node = heapq.heappop(pq)

        if d > dist[node]:
            continue  # 古いエントリ

        for neighbor, weight in graph.get(node, {}).items():
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return dist

# グラフ例
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

print(dijkstra(graph, 'A'))  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}