データ構造完全整理2025：ArrayからTrie、B-Treeまで — 面接に出る全データ構造

O(1)        — 定数時間     例: 配列インデックスアクセス
O(log n)    — 対数時間     例: 二分探索
O(n)        — 線形時間     例: 配列走査
O(n log n)  — 線形対数     例: マージソート
O(n^2)      — 二次時間     例: バブルソート
O(2^n)      — 指数時間     例: フィボナッチ再帰
O(n!)       — 階乗         例: 順列生成

n       O(1)  O(log n)  O(n)   O(n log n)  O(n^2)     O(2^n)
10      1     3         10     33          100        1,024
100     1     7         100    664         10,000     1.27e30
1000    1     10        1000   9,966       1,000,000  ---
10000   1     13        10000  132,877     1億         ---

動的配列のappend:
  通常: O(1) — 空きスロットに追加
  時々: O(n) — 配列が満杯になると2倍のサイズにコピー

  n回のappend総コスト: n + n/2 + n/4 + ... ≈ 2n
  償却コスト: O(2n/n) = O(1)

インデックス:  0    1    2    3    4
             [10] [20] [30] [40] [50]
              ^                    ^
           arr[0]              arr[4]

# 動的配列の実装
class DynamicArray:
    def __init__(self):
        self.size = 0
        self.capacity = 1
        self.data = [None] * self.capacity

    def append(self, value):
        if self.size == self.capacity:
            self._resize(2 * self.capacity)
        self.data[self.size] = value
        self.size += 1

    def _resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data = new_data
        self.capacity = new_capacity

    def get(self, index):
        if 0 <= index < self.size:
            return self.data[index]
        raise IndexError("Index out of range")

単方向連結リスト (Singly):
  [10|->] -> [20|->] -> [30|->] -> [40|->] -> None

双方向連結リスト (Doubly):
  None <- [<-|10|->] <-> [<-|20|->] <-> [<-|30|->] -> None

循環連結リスト (Circular):
  [10|->] -> [20|->] -> [30|->] -> [10|->] (先頭に戻る)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

    def prepend(self, val):
        new_node = ListNode(val, self.head)
        self.head = new_node

    def delete(self, val):
        dummy = ListNode(0, self.head)
        prev, curr = dummy, self.head
        while curr:
            if curr.val == val:
                prev.next = curr.next
                break
            prev, curr = curr, curr.next
        self.head = dummy.next

    def reverse(self):
        prev, curr = None, self.head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        self.head = prev

push(10) -> push(20) -> push(30) -> pop()

  |    |   |    |   | 30 |   | 20 |
  |    |   | 20 |   | 20 |   |    | <- 30を返す
  | 10 |   | 10 |   | 10 |   | 10 |
  +----+   +----+   +----+   +----+

# スタック — Pythonリストで実装
class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items.pop()

    def peek(self):
        return self.items[-1] if self.items else None

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

enqueue(10) -> enqueue(20) -> enqueue(30) -> dequeue()

Front ->                                    Front ->
[10]      [10][20]     [10][20][30]       [20][30]  <- 10を返す

先頭から挿入/削除 <- [10][20][30] -> 末尾から挿入/削除

key: "apple" -> hash("apple") -> 3
key: "banana" -> hash("banana") -> 7
key: "cherry" -> hash("cherry") -> 3  <- 衝突！

バケット:
[0] ->
[1] ->
[2] ->
[3] -> ("apple", 100) -> ("cherry", 300)  <- チェイニング
[4] ->
[5] ->
[6] ->
[7] -> ("banana", 200)

[3] -> ("apple", 100) -> ("cherry", 300) -> None

線形探査（Linear Probing）:
  hash("cherry") = 3 -> 使用中 -> 4を確認 -> 空き -> 格納

二次探査（Quadratic Probing）:
  hash("cherry") = 3 -> 3+1^2=4 -> 3+2^2=7 -> ...

二重ハッシュ（Double Hashing）:
  hash("cherry") = 3 -> 3 + hash2("cherry") -> ...

Load Factor = 格納済み要素数 / バケット数

LF > 0.75 -> リハッシュ（バケット数を2倍に拡張、全要素を再配置）

class HashMap:
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]
        self.load_factor_threshold = 0.75

    def _hash(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        if self.size / self.capacity >= self.load_factor_threshold:
            self._rehash()

        idx = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx][i] = (key, value)
                return
        self.buckets[idx].append((key, value))
        self.size += 1

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        raise KeyError(key)

    def _rehash(self):
        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)

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

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

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

    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node

    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if not node or node.val == val:
            return node
        if val < node.val:
            return self._search(node.left, val)
        return self._search(node.right, val)

    def inorder(self, node, result=None):
        if result is None:
            result = []
        if node:
            self.inorder(node.left, result)
            result.append(node.val)
            self.inorder(node.right, result)
        return result

不均衡発生時に回転（Rotation）で均衡を復元:

LL回転（Right Rotation）:      RR回転（Left Rotation）:
    z                              z
   /                                \
  y         ->      y                 y       ->      y
 /                 / \                \             / \
x                 x   z                x           z   x

LR回転:                        RL回転:
    z                              z
   /                                \
  x         ->      y                x       ->      y
   \               / \             /               / \
    y             x   z           y               z   x

ルール:
1. 全ノードは赤または黒
2. ルートは黒
3. 全リーフ（NIL）は黒
4. 赤ノードの子は全て黒（連続する赤は不可）
5. 任意ノードから全リーフまでの黒ノード数は同一

        (B:8)
       /      \
    (R:3)    (R:10)
    / \        \
 (B:1)(B:6)  (B:14)
       / \     /
    (R:4)(R:7)(R:13)

B-Tree（次数3）:
          [10, 20]
         /   |    \
   [3,7]  [12,15] [25,30,40]

B+Tree（次数3）:
          [10, 20]
         /   |    \
   [3,7]  [10,15] [20,25,30]
      -> -> -> -> ->     <- リーフノードが連結リストで接続

配列: [1, 3, 5, 7, 9, 11]

区間合計 Segment Tree:
              [36]           (0-5)
           /        \
        [9]          [27]     (0-2), (3-5)
       /   \        /    \
     [4]   [5]   [16]   [11]  (0-1),(2),(3-4),(5)
    / \          / \
  [1] [3]     [7] [9]

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.build(arr, 1, 0, self.n - 1)

    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self.build(arr, 2 * node, start, mid)
            self.build(arr, 2 * node + 1, mid + 1, end)
            self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        left = self.query(2 * node, start, mid, l, r)
        right = self.query(2 * node + 1, mid + 1, end, l, r)
        return left + right

Min Heap:                 Max Heap:
      1                        9
     / \                      / \
    3   5                    7   8
   / \ / \                  / \ / \
  7  8 9  10               3  5 4  6

インデックス:  0  1  2  3  4  5  6
Min:         [ 1, 3, 5, 7, 8, 9, 10]

親: (i-1) // 2
左の子: 2*i + 1
右の子: 2*i + 2

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

    def push(self, val):
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        if not self.heap:
            raise IndexError("Heap is empty")
        self._swap(0, len(self.heap) - 1)
        val = self.heap.pop()
        if self.heap:
            self._sift_down(0)
        return val

    def _sift_up(self, i):
        parent = (i - 1) // 2
        while i > 0 and self.heap[i] < self.heap[parent]:
            self._swap(i, parent)
            i = parent
            parent = (i - 1) // 2

    def _sift_down(self, i):
        n = len(self.heap)
        while True:
            smallest = i
            left = 2 * i + 1
            right = 2 * i + 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 == i:
                break
            self._swap(i, smallest)
            i = smallest

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def heap_sort(arr):
    import heapq
    heapq.heapify(arr)
    return [heapq.heappop(arr) for _ in range(len(arr))]

単語: "cat", "car", "card", "dog", "do"

Root
+-- c
|   +-- a
|       +-- t (*)
|       +-- r (*)
|           +-- d (*)
+-- d
    +-- o (*)
        +-- g (*)

(*) = 単語の終端

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self._find_node(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find_node(prefix) is not None

    def _find_node(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def autocomplete(self, prefix):
        """prefixで始まる全ての単語を返す"""
        node = self._find_node(prefix)
        if not node:
            return []
        results = []
        self._dfs(node, prefix, results)
        return results

    def _dfs(self, node, path, results):
        if node.is_end:
            results.append(path)
        for char, child in node.children.items():
            self._dfs(child, path + char, results)

グラフ:
  A --- B
  |   / |
  |  /  |
  C --- D

隣接リスト（Adjacency List）:
  A: [B, C]
  B: [A, C, D]
  C: [A, B, D]
  D: [B, C]

隣接行列（Adjacency Matrix）:
     A  B  C  D
  A [0, 1, 1, 0]
  B [1, 0, 1, 1]
  C [1, 1, 0, 1]
  D [0, 1, 1, 0]

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

BFS順序（Aから開始）:
Level 0: A
Level 1: B, C
Level 2: D

キュー: [A] -> [B, C] -> [C, D] -> [D] -> []

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    result = [start]
    for neighbor in graph[start]:
        if neighbor not in visited:
            result.extend(dfs(graph, neighbor, visited))
    return result

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (距離, ノード)

    while pq:
        dist, node = heapq.heappop(pq)
        if dist > distances[node]:
            continue
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return distances

from collections import deque

def topological_sort(graph, in_degree):
    queue = deque([v for v in graph if in_degree[v] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return result if len(result) == len(graph) else []  # サイクル検出

def bellman_ford(edges, num_vertices, start):
    distances = [float('inf')] * num_vertices
    distances[start] = 0

    for _ in range(num_vertices - 1):
        for u, v, w in edges:
            if distances[u] + w < distances[v]:
                distances[v] = distances[u] + w

    # 負のサイクル検出
    for u, v, w in edges:
        if distances[u] + w < distances[v]:
            return None  # 負のサイクルが存在

    return distances

初期状態: 各ノードが自分自身を代表
{0} {1} {2} {3} {4}

union(0, 1): {0, 1} {2} {3} {4}
union(2, 3): {0, 1} {2, 3} {4}
union(0, 3): {0, 1, 2, 3} {4}

find(1) == find(3)?  -> Yes（同じ集合）
find(1) == find(4)?  -> No（異なる集合）

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        # 経路圧縮（Path Compression）
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # ランクによる統合（Union by Rank）
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

Level 3: HEAD -------------------- 50 ------- NIL
Level 2: HEAD ---- 20 ----------- 50 --- 70 -- NIL
Level 1: HEAD -- 10 -- 20 -- 30 -- 50 -- 70 -- 80 -- NIL
Level 0: HEAD -- 10 -- 20 -- 30 -- 40 -- 50 -- 60 -- 70 -- 80 -- NIL

k=3 ハッシュ関数、m=10 ビット配列

insert("apple"):
  h1("apple")=2, h2("apple")=5, h3("apple")=8
  ビット配列: [0,0,1,0,0,1,0,0,1,0]

query("apple"): 位置2,5,8が全て1 -> 「おそらく存在する」
query("grape"): h1=1, h2=5, h3=7 -> 位置1が0 -> 「確実に存在しない」

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

高速な挿入/削除が重要？ -> ハッシュテーブルまたは連結リスト
ソート順序が必要？ -> BST系（AVL、Red-Black）
最小値/最大値を高速に？ -> ヒープ
文字列プレフィックス検索？ -> トライ
範囲クエリ？ -> セグメントツリーまたはB-Tree
集合所属の高速判定？ -> HashSetまたはBloom Filter
連結成分の管理？ -> Union-Find
最短経路？ -> グラフ + Dijkstra/BFS
FIFO？ -> キュー
LIFO？ -> スタック