データ構造

データ構造#

データ構造と計算量#

なぜデータ構造を学ぶのか？ → 一つの実用的な理由は、計算量を大幅に削減できる場合があるから

例

  • listは検索（"hoge" in List）するとき\(O(n)\)（線形探索）

  • setは検索するとき\(O(1)\)

  • listでsortすると、要素数の分だけ計算量かかる

  • heapq（ヒープキュー、優先度つきキュー）で保持すると、最小値や最大値しか取り出せないが、頻繁に最小値や最大値を参照するときはlistで保持して毎回sortするより効率がいい（ABC141D - Powerful Discount Tickets）

参考

スタック#

スタック（stack） はデータの中で最後に入ったものが最初に取り出される 後入れ先出し（Last In First Out: LIFO） のデータ構造

操作：

  • push(x): スタックに要素xを追加する

  • pop(): スタックの最後の要素を取り出す

class Stack:

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

    def push(self, x):
        self.data.append(x)

    def pop(self):
        return self.data.pop(-1)


s = Stack()
s.push(1)
s.push(2)
s.pop()

2

キュー#

キュー（Queue） はデータの中で最初に入ったものが最初に取り出される、 先入れ先出し（First In First Out: FIFO） のデータ構造

操作：

  • enqueue(x): キューの末尾に要素xを追加する

  • dequeue(): キューの先頭から要素を取り出す

from queue import Queue

q = Queue()
q.put(1)
q.put(2)
q.get()

1

連結リスト#

連結リスト（Linked List） は、各要素（ノード）がデータと次の要素への参照（ポインタ）を持つデータ構造

配列と異なり、メモリ上に連続して配置される必要がない

特徴：

  • 要素の挿入・削除が\(O(1)\)で可能（位置がわかっている場合）

  • 任意の位置へのアクセスは\(O(n)\)（先頭から順にたどる必要がある）

  • メモリの動的な割り当てが可能

操作：

  • insert(x): リストに要素xを挿入する

  • delete(x): リストから要素xを削除する

  • search(x): リストから要素xを検索する

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


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

    def insert(self, data):
        """先頭に要素を挿入"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def delete(self, data):
        """指定した値を持つ最初のノードを削除"""
        if self.head is None:
            return

        # 先頭ノードが削除対象の場合
        if self.head.data == data:
            self.head = self.head.next
            return

        # 削除対象のノードを探す
        current = self.head
        while current.next is not None:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

    def search(self, data):
        """指定した値を持つノードを検索"""
        current = self.head
        while current is not None:
            if current.data == data:
                return True
            current = current.next
        return False

    def display(self):
        """リストの全要素を表示"""
        elements = []
        current = self.head
        while current is not None:
            elements.append(current.data)
            current = current.next
        return elements

# 使用例
ll = LinkedList()
ll.insert(3)
ll.insert(2)
ll.insert(1)
print("リスト:", ll.display())
print("2を検索:", ll.search(2))
ll.delete(2)
print("2を削除後:", ll.display())

リスト: [1, 2, 3]
2を検索: True
2を削除後: [1, 3]
NOTE: Pythonのlistは動的配列

そのためlist[i]での参照は\(O(1)\)で速く、挿入・削除が遅い

特性

Python list

連結リスト

メモリ配置

連続

非連続

lst[i] の計算量

O(1)

O(n)

末尾 append

平均 O(1)（償却）

O(1)

途中挿入・削除

O(n)（シフトが必要）

O(1)（参照があれば）

キャッシュ効率

良い

悪い
Contents