効率的なデータ構造の実装と操作の技術解説
双方向連結リストは、各ノードが前後のノードへの参照を持つデータ構造です。この実装では効率的な挿入・削除操作を提供します。
class Node:
__slots__ = ("value", "prev", "next")
def __init__(self, value: int):
self.value: int = value
self.prev: Optional["Node"] = None
self.next: Optional["Node"] = None
class DoublyLinkedList:
def __init__(self) -> None:
self.head: Optional[Node] = None
self.tail: Optional[Node] = None
self.length: int = 0各ノードは前後のノードへの双方向リンクを持ちます
リストの末尾に新しい要素を追加する操作です。tailポインタを利用してO(1)の時間で実行できます。
def append(self, value: int) -> None:
"""末尾に追加"""
node = Node(value)
if self.head is None:
self.head = self.tail = node
else:
assert self.tail is not None
self.tail.next = node
node.prev = self.tail
self.tail = node
self.length += 1append(40)を実行すると...
指定された位置に新しい要素を挿入する操作です。1-basedのインデックスを使用します。
def insert_at(self, pos: int, value: int) -> None:
"""1-based位置 pos に挿入"""
if pos < 1 or pos > self.length + 1:
raise ValueError("Invalid position for insert")
if pos == self.length + 1:
self.append(value)
return
node = Node(value)
if pos == 1:
assert self.head is not None
node.next = self.head
self.head.prev = node
self.head = node
else:
cur = self.head
for _ in range(pos - 1):
assert cur is not None
cur = cur.next
assert cur is not None
prev_node = cur.prev
if prev_node:
prev_node.next = node
node.prev = prev_node
node.next = cur
cur.prev = node
if pos == 1:
self.head = node
self.length += 1insert_at(2, 15)を実行すると...
指定された位置の要素を削除し、前後のノードを適切に接続する操作です。
def erase_at(self, pos: int) -> None:
"""1-based位置 pos を削除"""
if pos < 1 or pos > self.length:
raise ValueError("Invalid position for erase")
cur = self.head
for _ in range(pos - 1):
assert cur is not None
cur = cur.next
assert cur is not None
if cur.prev:
cur.prev.next = cur.next
else:
self.head = cur.next
if cur.next:
cur.next.prev = cur.prev
else:
self.tail = cur.prev
self.length -= 1erase_at(2)を実行すると...
各操作の時間計算量と空間計算量を比較分析します。
| 操作 | 時間計算量 | 空間計算量 | 備考 |
|---|---|---|---|
| append | O(1) | O(1) | tailポインタにより高速実行 |
| insert_at | O(n) | O(1) | 位置まで線形探索が必要 |
| erase_at | O(n) | O(1) | 削除位置まで線形探索が必要 |
| to_list | O(n) | O(n) | 全要素を配列にコピー |
入力から出力まで全体的な処理の流れを解説します。
def process_list(N: int, Q: int, A: List[int], queries: List[List[int]]) -> List[int]:
dll = DoublyLinkedList()
# 初期配列でリストを構築
for v in A:
dll.append(v)
# クエリを順次処理
for q in queries:
if q[0] == 1: # 挿入操作
_, P, X = q
dll.insert_at(P, X)
elif q[0] == 2: # 削除操作
_, P = q
dll.erase_at(P)
else:
raise ValueError("Invalid query type")
return dll.to_list()