Linked List Operations

単方向連結リストの挿入・削除操作の技術解析

アルゴリズム概要

このプログラムは単方向連結リスト（Singly Linked List）を用いて、効率的な挿入・削除操作を実現します。

O(N)
初期リスト構築
O(M)
各クエリ処理
O(N)
空間計算量

データ構造設計

ListNode Class Definition 
class ListNode:
    """単方向リストのノード（軽量化のため __slots__ を使用）"""
    __slots__ = ('val', 'next')

    def __init__(self, val: int) -> None:
        self.val: int = val
        self.next: Optional['ListNode'] = None
メモリ最適化: __slots__を使用することで、各ノードのメモリ使用量を約50%削減

INSERT操作の解析

INSERT操作の視覚的デモンストレーション
操作を選択してください
INSERT Operation Implementation 
if t == 1:
    # INSERT P X
    if len(parts) != 3:
        raise ValueError("INSERT query must have 3 parts")
    try:
        P = int(parts[1]); X = int(parts[2])
    except Exception:
        raise TypeError("P and X must be integers")

    new_node = ListNode(X)
    if P == 1:
        # insert at head
        new_node.next = head
        head = new_node
        if tail is None:
            tail = new_node
    else:
        # traverse to (P-1)th node (1-based)
        prev = head
        for _i in range(1, P - 1):
            prev = prev.next

        # now prev is the (P-1)-th node
        new_node.next = prev.next
        prev.next = new_node
        if new_node.next is None:
            tail = new_node

ERASE操作の解析

ERASE操作の視覚的デモンストレーション
操作を選択してください
ERASE Operation Implementation 
elif t == 2:
    # ERASE P
    if len(parts) != 2:
        raise ValueError("ERASE query must have 2 parts")
    try:
        P = int(parts[1])
    except Exception:
        raise TypeError("P must be integer")

    if head is None:
        raise ValueError("attempt to ERASE from empty list")

    if P == 1:
        # remove head
        head = head.next
        if head is None:
            tail = None
    else:
        prev = head
        for _i in range(1, P - 1):
            prev = prev.next

        # prev is (P-1)-th node, prev.next is P-th node
        prev.next = prev.next.next
        if prev.next is None:
            tail = prev

パフォーマンス分析

時間計算量の詳細分析:
  • 先頭挿入/削除: O(1) - ポインタの更新のみ
  • 中間位置操作: O(P) - 指定位置まで走査が必要
  • 末尾操作: tailポインタにより効率化
50%
メモリ削減効果
O(1)
最良時間計算量
O(N)
最悪時間計算量

完全な実装例

実際の処理例: 初期リスト [1, 2, 3] に対する操作シーケンス
Complete solve() Function 
def solve(input_str: str) -> str:
    """
    入力を受け取り、クエリを処理して結果を返す。
    """
    if not isinstance(input_str, str):
        raise TypeError("input_str must be a string")

    lines = input_str.rstrip('\n').split('\n')
    if len(lines) == 0:
        raise ValueError("empty input")

    # ヘッダ行解析
    header = lines[0].strip().split()
    N = int(header[0]); Q = int(header[1])

    # 初期リスト構築（末尾追加）
    head: Optional[ListNode] = None
    tail: Optional[ListNode] = None
    idx_line = 1

    for i in range(N):
        v = int(lines[idx_line].strip())
        idx_line += 1
        node = ListNode(v)
        if head is None:
            head = tail = node
        else:
            tail.next = node
            tail = node

    # クエリ処理
    for _ in range(Q):
        parts = lines[idx_line].strip().split()
        idx_line += 1
        t = int(parts[0])

        # INSERT/ERASE処理（上記コード参照）
        # ...

    # 出力作成
    out_lines = []
    node = head
    while node is not None:
        out_lines.append(str(node.val))
        node = node.next

    return "\n".join(out_lines) + "\n" if out_lines else ""