class Node:
    Node *prev
    Node *next
    key

class LinkedList:
    Node *sentinel  # 番兵

    # 空のリストとして初期化
    init():
        sentinel ← ノードを生成
        sentinel.next ← sentinel  # 自分自身を指す
        sentinel.prev ← sentinel  # 自分自身を指す

    # dataを挿入
    insert(data):
        # ノードを生成してデータとポインタを設定
        Node *x ← ノードを生成
        x.key ← data # データ本体を設定
        x.next ← sentinel.next
        x.prev ← sentinel
        # 番兵と、元の先頭ノードのポインタを設定
        sentinel.next.prev ← x
        sentinel.next ← x

    # kを持つノードを探す
    listSearch(k):
        Node *cur ← sentinel.next # 番兵の次の要素から辿る
        while cur ≠ sentinel and cur.key ≠ k:
            cur ← cur.next
        return cur

    deleteNode(Node *t):
        if t = sentinel: return # t が番兵の場合は処理しない
        t.prev.next ← t.next
        t.next.prev ← t.prev
        tのメモリを解放

    # kを持つノードを削除する
    deleteKey(k):
        deleteNode(listSearch(k)) # 取得したノードを削除