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)) # 删除得到的节点