Pythonでデータ処理を行う際、多くのエンジニアが最初に手に取るのはlist型でしょう。
しかし、大量のデータを扱うアプリケーションや、リアルタイム性が求められるシステムにおいて、リストの操作がボトルネックになるケースは少なくありません。
特に「先頭への要素追加」や「先頭からの要素削除」を頻繁に行う場合、リストの性能は著しく低下します。
このような課題を解決するために用意されているのが、Pythonの標準ライブラリcollectionsモジュールに含まれるdeque（デック）です。
本記事では、dequeがなぜリストよりも高速なのかという仕組みから、具体的な実装例、実務で役立つ活用シーンまでを詳しく解説します。
Pythonのdeque（デック）とは何か
dequeは「Double-Ended Queue」の略称であり、日本語では「両端キュー」と呼ばれます。
その名前の通り、データの両端に対して高速に要素を追加・削除できるという特徴を持ったデータ構造です。
Pythonの標準的なlistが動的配列として実装されているのに対し、dequeは「双方向連結リスト」に近い形で管理されています。
この内部構造の違いが、特定の操作における劇的なパフォーマンスの差を生み出します。
dequeを利用するには、以下のようにcollectionsからインポートする必要があります。
from collections import deque
# 空のdequeを作成
d = deque()
# 初期値を指定して作成
d = deque([1, 2, 3])dequeとリストのパフォーマンス比較
なぜリストではなくdequeを使うべき場面があるのかを理解するために、時間計算量の違いを確認しましょう。
以下の表は、それぞれのデータ構造における主要な操作の計算量をまとめたものです。
| 操作内容 | list（リスト） | deque（デック） |
|---|---|---|
| 末尾への追加（append） | O(1) | O(1) |
| 末尾の削除（pop） | O(1) | O(1) |
| 先頭への追加（insert/appendleft） | O(n) | O(1) |
| 先頭の削除（pop(0)/popleft） | O(n) | O(1) |
| 任意要素へのアクセス（インデックス） | O(1) | O(n) |
リストの場合、先頭に要素を追加したり削除したりすると、後続のすべての要素をメモリ上でずらす必要があります。
そのため、リストの要素数 n が増えるほど、処理にかかる時間は直線的に増加してしまいます。
対してdequeは、メモリ上の各要素が前後のリンク情報を保持しているため、ポインタを書き換えるだけで先頭操作が完了します。
この特性により、数百万件のデータを扱うキュー処理において、dequeはリストよりも圧倒的に有利となります。
実行速度の検証コード
実際にどれほどの差が出るのか、10万個の要素を持つデータに対して先頭からの削除を繰り返すテストを行ってみましょう。
import time
from collections import deque
n = 100000
# リストの検証
lst = list(range(n))
start = time.time()
while lst:
lst.pop(0)
print(f"リストのpop(0)にかかった時間: {time.time() - start:.5f} 秒")
# dequeの検証
dq = deque(range(n))
start = time.time()
while dq:
dq.popleft()
print(f"dequeのpopleft()にかかった時間: {time.time() - start:.5f} 秒")リストのpop(0)にかかった時間: 0.65432 秒
dequeのpopleft()にかかった時間: 0.00512 秒結果からもわかる通り、dequeの方が桁違いに速いことが証明されています。
dequeの主要なメソッドと使い方
dequeには、リストと似た操作感でありながら、より柔軟な両端操作を可能にするメソッドが揃っています。
要素の追加（append, appendleft）
末尾への追加はappend()、先頭への追加はappendleft()を使用します。
d = deque([10, 20])
d.append(30) # [10, 20, 30]
d.appendleft(0) # [0, 10, 20, 30]
print(d)要素の削除（pop, popleft）
末尾の取り出しはpop()、先頭の取り出しはpopleft()を使用します。
d = deque([1, 2, 3])
tail = d.pop() # 3
head = d.popleft() # 1
print(f"取り出した値: {head}, {tail}")
print(f"残ったdeque: {d}")要素の回転（rotate）
rotate()メソッドを使用すると、要素を指定した数だけ左右に回転させることができます。
これはリストにはないdeque独自の非常に便利な機能です。
d = deque([1, 2, 3, 4, 5])
d.rotate(1) # 右に1つ回転
print(d) # deque([5, 1, 2, 3, 4])
d.rotate(-2) # 左に2つ回転
print(d) # deque([2, 3, 4, 5, 1])最大長の設定（maxlen）
dequeを作成する際にmaxlen引数を指定すると、最大サイズを固定することができます。
最大サイズを超えて新しい要素が追加されると、自動的に反対側の要素が破棄されます。
d = deque(maxlen=3)
d.append(1)
d.append(2)
d.append(3)
d.append(4) # 1が自動的に押し出される
print(d) # deque([2, 3, 4], maxlen=3)dequeを活用した実践的な実装例
ここからは、実務でdequeがどのように使われるか、代表的な3つのシナリオを紹介します。
1. キュー（FIFO）の実装
最も一般的な用途は、先入れ先出し（First-In, First-Out）のデータ管理です。
タスク管理システムや、非同期処理の待機行列などで活用されます。
task_queue = deque()
# タスクの追加
task_queue.append("メール送信")
task_queue.append("レポート作成")
task_queue.append("バックアップ")
# タスクの処理
while task_queue:
current_task = task_queue.popleft()
print(f"現在処理中: {current_task}")2. 最近の履歴の保持（ログ管理）
maxlenを利用することで、常に最新のN件だけを保持するログバッファを簡単に実装できます。
古いデータを手動で削除する手間が省け、メモリ消費も一定に抑えることができます。
recent_logs = deque(maxlen=5)
def add_log(message):
recent_logs.append(message)
print(f"最新のログを表示: {list(recent_logs)}")
for i in range(10):
add_log(f"イベント {i}")3. 幅優先探索（BFS）の効率化
グラフ理論や迷路解法などのアルゴリズムにおいて、幅優先探索ではキューが必須となります。
ノードの数が多い場合、リストのpop(0)を使うと全体の計算量がO(V^2)に跳ね上がりますが、dequeを使えばO(V)で効率的に探索可能です。
def bfs(graph, start_node):
visited = set()
queue = deque([start_node])
visited.add(start_node)
while queue:
node = queue.popleft()
print(f"訪問したノード: {node}")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 隣接リスト形式のグラフ
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs(graph, 'A')dequeを使用する際の注意点
dequeは非常に強力ですが、あらゆる場面でリストを代替するわけではありません。
メリットだけでなく、考慮すべき制約についても理解しておきましょう。
ランダムアクセスは遅い
リストは配列であるため、list[500]のようにインデックスを指定して中央付近の要素にアクセスする操作は一瞬（O(1)）で終わります。
一方、dequeは連結リストの構造を持っているため、中央付近の要素を取得するには端から順番に辿る必要があり、O(n)の時間がかかります。
頻繁にインデックスによる参照や書き換えを行う場合は、リストの方が適しています。
メモリ使用量
dequeは各ノードでリンク情報（ポインタ）を保持するため、リストと比較してわずかにメモリ消費量が多くなる傾向があります。
極端にメモリが制限された環境で、かつ両端操作が必要ない場合は、リストやarrayモジュールの検討が必要です。
スライス操作の制限
リストでは当たり前のように使えるd[1:5]といったスライス操作は、dequeでは直接行うことができません。
スライスが必要な場合は、一度list(d)で変換するか、itertools.isliceを使用する手間が生じます。
まとめ
Pythonのcollections.dequeは、特にデータの追加や削除が頻繁に発生する場面において、パフォーマンスを最大化するための強力なツールです。
リストとの決定的な違いは、先頭要素への操作が定数時間 O(1) で行える点にあります。
キューやスタックの実装、あるいはスライディングウィンドウのような最新データの保持には、dequeの使用が最適解となります。
一方で、ランダムアクセスの性能が低いという弱点もあるため、用途に応じてリストと使い分けることが重要です。
プログラムの実行速度を改善したいと考えたときは、まずデータ構造を見直し、適切な場面でdequeを導入してみてください。