ALDS1_3_C_Doubly_Linked_List.py

"""
input:
n // 命令数
command1
command2
...
commandn

limitation:
命令数は 2,000,000 を超えない。
delete 命令の回数は 20 を超えない。
0 ≤ キーの値 ≤ 10^9。
命令の過程でリストの要素数は 106を超えない。
delete, deleteFirst, または deleteLast 命令が与えられるとき、リストには１つ以上の要素が存在する。
"""


class Node():
    def __init__(self, v) -> None:
        self.value = v
        self.next: Node = None
        self.prev: Node = None


class DoubleLinkedList():
    def __init__(self) -> None:
        self.head: Node = None
        self.tail: Node = None
        self.length: int = 0

    # 連結リストの先頭にキー x を持つ要素を継ぎ足す
    def insert(self, x) -> None:
        newNode: Node = Node(x)
        if (self.length == 0):
            self.head = newNode
            self.tail = newNode
        else:
            oldhead = self.head
            self.head = newNode
            newNode.next = oldhead
            oldhead.prev = self.head
        self.length = self.length + 1

    # キー x を持つ最初の要素を連結リストから削除する。そのような要素が存在しない場合は何もしない。
    def delete(self, x) -> None:
        tmp: Node = self.head
        while(tmp.value != x):
            if(tmp.next is None):
                return None
            tmp = tmp.next

        # 要素が存在する場合
        ### 末尾ノードの場合
        if(tmp.next is None):
            tmp.prev.next = None
            self.tail = tmp.prev
        ### 先頭ノードの場合
        elif(tmp.prev is None):
            tmp.next.prev = None
            self.head = tmp.next
        else:
            tmp.prev.next = tmp.next
            tmp.next.prev = tmp.prev
        self.length = self.length - 1

    def deleteFirst(self) -> None:
        if(not self.length):
            return None
        elif(self.length == 1):
            self.head = None
            self.tail = None
        else:
            self.head.next.prev = None
            self.head = self.head.next
        self.length = self.length - 1

    def deleteLast(self) -> None:
        if(not self.length):
            return None
        elif(self.length == 1):
            self.head = None
            self.tail = None
        else:
            self.tail.prev.next = None
            self.tail = self.tail.prev

        self.length = self.length - 1

    def printList(self) -> None:
        tmp: Node = self.head
        vl: list = []
        while(True):
            vl.append(tmp.value)
            if (tmp.next is None):
                break
            tmp = tmp.next
        print(' '.join(map(str, vl)))


N: int = int(input())
ops: list = [input() for _ in range(N)]

dll: DoubleLinkedList = DoubleLinkedList()

for op in ops:
    if op == 'deleteFirst':
        dll.deleteFirst()
    elif op == 'deleteLast':
        dll.deleteLast()
    elif op.startswith('insert'):
        dll.insert(int(op.split()[1]))
    elif op.startswith('delete'):
        dll.delete(int(op.split()[1]))

dll.printList()