連結リスト・スタック・キュー ── 線形データ構造の使い分け

2026/04/26

連結リスト・スタック・キュー ── 線形データ構造の使い分け

扱う概念：単方向/双方向連結リスト、LIFO（スタック）、FIFO（キュー）、デック（Deque）、単調スタック

線形データ構造 — 連結リスト・スタック・キュー

この章で何ができるようになるか：「配列でいいのに、なぜ連結リストが存在するのか」を説明でき、スタックとキューの典型的な適用場面を判断できるようになる。

連結リスト（Linked List）

各要素（ノード）が「値」と「次のノードへのポインタ」を持つ。

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self._size = 0

    def prepend(self, val):
        """先頭に挿入 — O(1)"""
        self.head = ListNode(val, self.head)
        self._size += 1

    def append(self, val):
        """末尾に挿入 — O(n)（末尾を探す必要がある）"""
        if not self.head:
            self.head = ListNode(val)
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = ListNode(val)
        self._size += 1

    def delete(self, val):
        """値で削除 — O(n)"""
        dummy = ListNode(0, self.head)
        prev, current = dummy, self.head
        while current:
            if current.val == val:
                prev.next = current.next
                self._size -= 1
                self.head = dummy.next
                return True
            prev, current = current, current.next
        return False

    def find(self, val) -> bool:
        """検索 — O(n)"""
        current = self.head
        while current:
            if current.val == val:
                return True
            current = current.next
        return False

配列 vs 連結リスト

操作	配列	連結リスト
インデックスアクセス	O(1)	O(n)
先頭に挿入	O(n)	O(1)
中間に挿入（位置がわかっている場合）	O(n)	O(1)
末尾に挿入	O(1) 償却	O(n) / O(1)※
メモリ	連続 → キャッシュ効率◎	散在 → キャッシュ効率×
追加メモリ	なし	ポインタ分のオーバーヘッド

※ 双方向リストで末尾ポインタを持つ場合

実務での使い分け：ほとんどのケースで配列（動的配列）が優位。連結リストが活きるのは「先頭・中間への頻繁な挿入・削除」があり「ランダムアクセスが不要」な場面。LRU キャッシュ（ハッシュマップ + 双方向リスト）が典型例。

双方向連結リスト（Doubly Linked List）

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

class DoublyLinkedList:
    def __init__(self):
        self.head = DListNode()  # ダミーヘッド
        self.tail = DListNode()  # ダミーテール
        self.head.next = self.tail
        self.tail.prev = self.head

    def push_front(self, val) -> DListNode:
        """先頭に挿入 — O(1)"""
        node = DListNode(val, self.head, self.head.next)
        self.head.next.prev = node
        self.head.next = node
        return node

    def push_back(self, val) -> DListNode:
        """末尾に挿入 — O(1)"""
        node = DListNode(val, self.tail.prev, self.tail)
        self.tail.prev.next = node
        self.tail.prev = node
        return node

    def remove(self, node: DListNode):
        """ノードを削除（ポインタがある場合）— O(1)"""
        node.prev.next = node.next
        node.next.prev = node.prev

    def move_to_front(self, node: DListNode):
        """ノードを先頭に移動 — O(1)（LRU キャッシュで使う）"""
        self.remove(node)
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

スタック（Stack）：LIFO

Last In, First Out。最後に入れたものが最初に出てくる。

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

    def push(self, val):    # O(1)
        self._data.append(val)

    def pop(self):           # O(1)
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._data.pop()

    def peek(self):          # O(1)
        return self._data[-1]

    def is_empty(self) -> bool:
        return len(self._data) == 0

スタックの応用：括弧の対応チェック

def is_valid_parentheses(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()

    return len(stack) == 0

# "({[]})" → True
# "({[}])" → False

単調スタック（Monotonic Stack）

「各要素の右にある最初の大きい値」を O(n) で求める強力なテクニック。

def next_greater_element(nums: list[int]) -> list[int]:
    """各要素について、右にある最初の自分より大きい要素を返す"""
    result = [-1] * len(nums)
    stack = []  # インデックスを保持（値は単調減少）

    for i, num in enumerate(nums):
        # スタック上の「自分より小さい要素」の答えは自分
        while stack and nums[stack[-1]] < num:
            idx = stack.pop()
            result[idx] = num
        stack.append(i)

    return result

# [2, 1, 2, 4, 3] → [4, 2, 4, -1, -1]

キュー（Queue）：FIFO

First In, First Out。最初に入れたものが最初に出てくる。

from collections import deque

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

    def enqueue(self, val):   # O(1)
        self._data.append(val)

    def dequeue(self):         # O(1)
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self._data.popleft()  # deque なら O(1)

    def peek(self):
        return self._data[0]

    def is_empty(self) -> bool:
        return len(self._data) == 0

なぜ list ではなく deque を使うか：list.pop(0) は O(n)（全要素のシフト）。deque.popleft() は O(1)（双方向連結リストベース）。

BFS にはキュー

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()  # FIFO → 幅優先
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

DFS にはスタック（または再帰）

def dfs(graph, start):
    visited = {start}
    stack = [start]

    while stack:
        node = stack.pop()  # LIFO → 深さ優先
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)

まとめ

データ構造	挿入	削除	アクセス	主な用途
単方向リスト	O(1) 先頭	O(n)	O(n)	メモリ効率が必要な挿入リスト
双方向リスト	O(1) 両端	O(1)※	O(n)	LRU キャッシュ、エディタのカーソル
スタック	O(1)	O(1)	O(1) top	括弧チェック、DFS、式の評価、undo
キュー	O(1)	O(1)	O(1) front	BFS、タスクキュー、バッファ

※ ノードのポインタがある場合