3.1 データ操作: 挿入、削除、検索
挿入 (Insert):
データ構造に新しい要素を追加する操作。挿入はデータ構造の先頭、末尾、または任意の位置で行うことができる。
削除 (Delete):
データ構造から要素を削除する操作。削除は要素の値、インデックス、または位置に基づいて行うことができる。
検索 (Search):
データ構造内の要素を見つける操作。検索は値や他の基準に基づいて行うことができる。
操作の例:
- 配列: 挿入と削除は要素のシフトを必要とし、時間がかかることがある —
O(n)。 - 連結リスト: ノードの位置がわかっていれば、挿入と削除は
O(1)で行える。 - ハッシュテーブル: 検索、挿入、削除は通常、平均的な場合で
O(1)で行われる。 - 木構造: 平衡木では検索、挿入、削除は
O(log n)で行われる場合がある。
3.2 基本的な概念: 配列、リスト、スタック、キュー
配列
配列 — 同じ型の要素のシーケンスで、インデックスによってアクセスできる。
操作の複雑さ: インデックスによるアクセス — O(1)、挿入と削除 — O(n)。
例: 配列の作成、要素の変更、結果の表示
# 数値の配列を作成
arr = [1, 2, 3, 4, 5]
# インデックス2の要素を変更（インデックスは0から始まるので3番目の要素）
arr[2] = 10
# 変更後の配列を表示
print(arr) # 出力: [1, 2, 10, 4, 5]
# 配列の末尾に新しい要素を追加
arr.append(6)
print(arr) # 出力: [1, 2, 10, 4, 5, 6]
# インデックスで要素を削除
del arr[1]
print(arr) # 出力: [1, 10, 4, 5, 6]
リスト
リスト — 次の要素（単方向連結リスト）または次と前の要素（双方向連結リスト）への参照を持つ要素のコレクション。
操作の複雑さ: 位置がわかっている場合の挿入と削除 — O(1)、検索 — O(n)。
例: 単純な単方向連結リストの作成とその走査
# リストノードの構造を定義
class Node:
def __init__(self, data):
self.data = data
self.next = None
# 単方向連結リストを作成
node1 = Node("101")
node2 = Node("102")
node3 = Node("103")
# ノードを連結
node1.next = node2
node2.next = node3
# リストの開始を設定
list_head = node1
# リストを走査してデータを表示
current = list_head
while current:
print(current.data)
current = current.next
# 出力:
# 101
# 102
# 103
スタック (Stack)
スタック — LIFO (Last In, First Out) の原則を持つ要素のコレクション: 最後に追加された要素が最初に取り出される。
操作の複雑さ: 挿入 (push) と削除 (pop) — O(1)。
例: カッコのバランスを検証するためのスタックの実装と使用
def is_balanced(expression):
stack = []
opening = "({["
closing = ")}]"
pairs = {")": "(", "}": "{", "]": "["}
for char in expression:
if char in opening:
stack.append(char)
elif char in closing:
if not stack or stack.pop() != pairs[char]:
return False
return len(stack) == 0
# さまざまな式を検証
print(is_balanced("({[]})")) # 出力: True
print(is_balanced("([)]")) # 出力: False
print(is_balanced("((")) # 出力: False
キュー (Queue)
キュー — FIFO (First In, First Out) の原則を持つ要素のコレクション: 最初に追加された要素が最初に取り出される。
操作の複雑さ: 挿入 (enqueue) と削除 (dequeue) — O(1)。
例: タスク処理のシミュレーションのためのキューの実装と使用
from collections import deque
class TaskQueue:
def __init__(self):
self.queue = deque()
def add_task(self, task):
self.queue.append(task)
print(f"タスク '{task}' がキューに追加されました")
def process_task(self):
if self.queue:
task = self.queue.popleft()
print(f"タスクを処理中: '{task}'")
else:
print("キューは空です")
def display_queue(self):
print("現在のタスクキュー:", list(self.queue))
# タスクキューの作成と使用
task_queue = TaskQueue()
task_queue.add_task("メール送信")
task_queue.add_task("データベースの更新")
task_queue.add_task("レポートの作成")
task_queue.display_queue()
task_queue.process_task()
task_queue.process_task()
task_queue.display_queue()
# 出力:
# タスク 'メール送信' がキューに追加されました
# タスク 'データベースの更新' がキューに追加されました
# タスク 'レポートの作成' がキューに追加されました
# 現在のタスクキュー: ['メール送信', 'データベースの更新', 'レポートの作成']
# タスクを処理中: 'メール送信'
# タスクを処理中: 'データベースの更新'
# 現在のタスクキュー: ['レポートの作成']
3.3 データ構造の異なるタイプの違い
以下は異なるタイプのデータ構造の主な違いです:
配列:
- アクセス: インデックスによる高速アクセス —
O(1)。 - サイズ変更: 固定サイズ、拡張には全要素のコピーが必要 —
O(n)。 - 適する場面: 要素へのランダムアクセスが必要で、データサイズが予め分かっている場合。
連結リスト:
- アクセス: インデックスによるアクセスが遅い —
O(n)。 - サイズ変更: 簡単にサイズ変更可能、挿入と削除は
O(1)。 - 適する場面: 要素の頻繁な追加と削除が必要な場合。
スタック:
- 動作原則:
LIFO。 - 操作: 挿入と削除は一方の端でのみ行われる —
O(1)。 - 適する場面: タスクの逆順実行や関数呼び出しの管理に。
キュー:
- 動作原則:
FIFO。 - 操作: 挿入と削除は異なる端で行われる —
O(1)。 - 適する場面: タスクの到着順での管理。
3.4 各種データ構造の応用
実際での各種データ構造の応用例:
配列
曜日や年の月など、固定長のデータを格納する。
例: 曜日を扱うための配列の使用
# 曜日の配列を作成
days = ["月曜日", "火曜日", "水曜日", "木曜日", "金曜日", "土曜日", "日曜日"]
# インデックスで曜日を取得（例：3番目の曜日）
print(days[2]) # 出力: 水曜日
# 曜日の名前を変更
days[0] = "月曜日 (週の始まり)"
print(days[0]) # 出力: 月曜日 (週の始まり)
# すべての曜日を列挙
for day in days:
print(day)
# 出力:
# 月曜日 (週の始まり)
# 火曜日
# 水曜日
# 木曜日
# 金曜日
# 土曜日
# 日曜日
連結リスト
コレクションの中央から要素を追加または削除できる動的コレクションの実装。
例: ToDoリストを格納するための連結リストの実装と使用
class TodoItem:
def __init__(self, task):
self.task = task
self.next = None
class TodoList:
def __init__(self):
self.head = None
def add_task(self, task):
new_item = TodoItem(task)
if not self.head:
self.head = new_item
else:
current = self.head
while current.next:
current = current.next
current.next = new_item
def display_tasks(self):
current = self.head
if not current:
print("ToDoリストは空です")
else:
while current:
print(f"- {current.task}")
current = current.next
# ToDoリストの作成と使用
todo = TodoList()
todo.add_task("食料品を買う")
todo.add_task("お母さんに電話する")
todo.add_task("プレゼンテーションを準備する")
print("私のToDoリスト:")
todo.display_tasks()
# 出力:
# 私のToDoリスト:
# - 食料品を買う
# - お母さんに電話する
# - プレゼンテーションを準備する
スタック
タスクの逆順実行、例えば再帰での関数呼び出し、操作の元に戻す (undo) など。
例: スタックを使って文字列を逆にする
def reverse_string(s):
stack = []
# 各文字をスタックに追加
for char in s:
stack.append(char)
reversed_s = ''
# スタックから文字を取り出し、逆の文字列を形成
while stack:
reversed_s += stack.pop()
return reversed_s
# 使用例
original = "Hello, World!"
reversed_str = reverse_string(original)
print(f"元の文字列: {original}")
print(f"逆になった文字列: {reversed_str}")
# 出力:
# 元の文字列: Hello, World!
# 逆になった文字列: !dlroW ,olleH
キュー
タスクを到着順に管理、例えばプリンターのジョブ、顧客サービスの順番待ちなど。
例: 印刷ジョブのシミュレーションのためのキュー
from collections import deque
class PrinterQueue:
def __init__(self):
self.queue = deque()
def add_document(self, document):
self.queue.append(document)
print(f"ドキュメント '{document}' が印刷キューに追加されました")
def print_document(self):
if self.queue:
document = self.queue.popleft()
print(f"ドキュメントを印刷中: '{document}'")
else:
print("印刷キューは空です")
def display_queue(self):
print("現在の印刷キュー:", list(self.queue))
# 印刷キューの作成と使用
printer = PrinterQueue()
printer.add_document("レポート")
printer.add_document("プレゼンテーション")
printer.add_document("契約書")
printer.display_queue()
printer.print_document()
printer.print_document()
printer.display_queue()
# 出力:
# ドキュメント 'レポート' が印刷キューに追加されました
# ドキュメント 'プレゼンテーション' が印刷キューに追加されました
# ドキュメント '契約書' が印刷キューに追加されました
# 現在の印刷キュー: ['レポート', 'プレゼンテーション', '契約書']
# ドキュメントを印刷中: 'レポート'
# ドキュメントを印刷中: 'プレゼンテーション'
# 現在の印刷キュー: ['契約書']
この例では、印刷キューの単純なシミュレーションを作成しました。ドキュメントはキューの末尾に追加され、到着順に印刷されることで、FIFO (First In, First Out) の原則を示しています。
GO TO FULL VERSION