题解 | 【模板】链表

class Node:
    def __init__(self,val=None):
        self.val=val
        self.pre=None
        self.next=None

#双向链表+字典
n=int(input())
dummy=Node()
tail=Node()
dummy.next=tail
tail.pre=dummy
d={} #记录数值x对应的结点,用列表存储，可能有多个值为x的结点
for i in range(n):
    op=input().split()
    if op[0]=='insert':
        num1, num2=op[1],op[2]
        if num1 in d.keys(): #假设说链表中存在这个值
            p=d[num1][-1]
        else:
            p=tail
        #插入到p.pre和p之间
        node=Node(num2)
        node.next=p 
        p.pre.next=node
        node.pre=p.pre
        p.pre=node 
        #插入之后需要维护一下字典
        if num2 not in d.keys():
            d[num2]=[node] #新建一个list
        else:
            d[num2].append(node) #加到list末尾

    elif op[0]=='delete':
        num=op[1]
        if num in d.keys():#存在的时候才需要执行删除操作，并维护字典
            node=d[num][-1]
            node.pre.next=node.next
            node.next.pre=node.pre
            del node
            #维护字典
            if len(d[num])>1:
                d[num].pop()
            else:
                del d[num]
cur=dummy.next
if not cur.val:
    print('NULL')
else:
    while cur!=tail:
        print(cur.val,end=' ')
        cur=cur.next