Problem:


Doubly Linked List

Your task is to implement a double linked list.

Write a program which performs the following operations:

insert x: insert an element with key x into the front of the list.

delete x: delete the first element which has the key of x from the list. If there is not such element, you need not do anything.

deleteFirst: delete the first element from the list. 

deleteLast: delete the last element from the list. 

Input

The input is given in the following format:

n

command1 

command2 

...

commandn 

In the first line, the number of operations n is given. In the following n lines, the above mentioned operations are given in the following format:

insert x

delete x

deleteFirst 

deleteLast 

Output

Print all the element (key) in the list after the given operations. Two consequtive keys should be separated by a single space.

Constraints

The number of operations ≤ 2,000,000

The number of delete operations ≤ 20

0 ≤ value of a key ≤ 109

The number of elements in the list does not exceed 106

For a delete, deleteFirst or deleteLast operation, there is at least one element in the list.

Sample Input 1

7
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5

Sample Output 1

6 1 2

Sample Input 2

9
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5
deleteFirst
deleteLast

Sample Output 2

1

Template in C
-->


Sample input:
7
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5


Sample output:
6 1 2

Submission status: Time Limit Exceeded

Solution code:
import sys

class Node:
    def __init__(self, num):
        self.prev = None
        self.next_node = None
        self.num = num
    def delete(self):
        if self.prev is not None:
            self.prev.next_node = self.next_node
        if self.next_node is not None:
            self.next_node.prev = self.prev

class LinkedList:
    def __init__(self):
        self.start_node = None
        self.last_node = None
    def add(self, num):
        node = Node(num)
        if self.start_node is None:
            self.start_node = node
            self.last_node = node
        elif self.last_node is None:
            self.last_node = self.start_node
            node.next_node = self.last_node
            self.last_node.prev = node
            self.start_node = node
        else:   
            self.start_node.prev = node
            node.next_node = self.start_node
            self.start_node = node
    def delete(self, num):
        node = self.start_node
        while node is not None:
            if node.num == num:
                if node == self.start_node:
                    self.delete_first()
                elif node == self.last_node:
                    self.delete_last()
                else:
                    node.delete()
                break
            node = node.next_node
    def delete_last(self):
        if self.start_node == self.last_node:
            self.start_node = None
            self.last_node = None
        else:
            node = self.last_node
            self.last_node = self.last_node.prev
            node.delete()
    def delete_first(self):
        if self.start_node == self.last_node:
            self.start_node = None
            self.last_node = None
        else:
            node = self.start_node
            self.start_node = self.start_node.next_node
            node.delete()
    def __str__(self):
        s = []
        node = self.start_node
        while node is not None:
            s.append(node.num)
            node = node.next_node
        return ' '.join(s)

def main():
    linked_list = LinkedList()
    c_num = int(sys.stdin.readline().strip())
    for i in range(0, c_num):
        line = sys.stdin.readline().strip().split(" ")
        op = line[0]
        if op == "insert":
            linked_list.add(line[1])
        if op == "delete":
            linked_list.delete(line[1])
        if op == "deleteFirst":
            linked_list.delete_first()
        if op == "deleteLast":
            linked_list.delete_last()
        #print linked_list
    print str(linked_list)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

class Node:
    def __init__(self, num):
        self.prev = None
        self.next_node = None
        self.num = num
    def delete(self):
        if self.prev is not None:
            self.prev.next_node = self.next_node
        if self.next_node is not None:
            self.next_node.prev = self.prev

class LinkedList:
    def __init__(self):
        self.start_node = None
        self.last_node = None
    def add(self, num):
        node = Node(num)
        if self.start_node is None:
            self.start_node = node
            self.last_node = node
        elif self.last_node is None:
            self.last_node = self.start_node
            node.next_node = self.last_node
            self.last_node.prev = node
            self.start_node = node
        else:   
            self.start_node.prev = node
            node.next_node = self.start_node
            self.start_node = node
    def delete(self, num):
        node = self.start_node
        while node is not None:
            if node.num == num:
                if node == self.start_node:
                    self.delete_first()
                elif node == self.last_node:
                    self.delete_last()
                else:
                    node.delete()
                break
            node = node.next_node
    def delete_last(self):
        if self.start_node == self.last_node:
            self.start_node = None
            self.last_node = None
        else:
            node = self.last_node
            self.last_node = self.last_node.prev
            node.delete()
    def delete_first(self):
        if self.start_node == self.last_node:
            self.start_node = None
            self.last_node = None
        else:
            node = self.start_node
            self.start_node = self.start_node.next_node
            node.delete()
    def __str__(self):
        s = []
        node = self.start_node
        while node is not None:
            s.append(node.num)
            node = node.next_node
        return ' '.join(s)

def main():
    linked_list = LinkedList()
    c_num = int(stdin.readline().strip())
    for i in range(0, c_num):
        line = stdin.readline().strip().split(" ")
        op = line[0]
        if op == "insert":
            linked_list.add(line[1])
        if op == "delete":
            linked_list.delete(line[1])
        if op == "deleteFirst":
            linked_list.delete_first()
        if op == "deleteLast":
            linked_list.delete_last()
        #print linked_list
    print str(linked_list)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

l = []

n = int(sys.stdin.readline().strip())

def delete(lst,x):
	if x in lst:
		lst.remove(x)

def deleteFirst(lst):
	lst.pop(0)

def deleteLast(lst):
	lst.pop(len(lst)-1)


for i in range(n):
	c = sys.stdin.readline().strip().split(" ")
	if c[0]=="insert":
		l.insert(0,int(c[1]))
	elif c[0]=="delete":
		delete(l,int(c[1]))
	elif c[0]=="deleteFirst":
		deleteFirst(l)
	elif c[0]=="deleteLast":
		deleteLast(l)

for a in l:
	print(a),

Submission status: Time Limit Exceeded

Solution code:
import sys

l = []

n = int(sys.stdin.readline().strip())

def delete(lst,x):
	if x in lst:
		lst.remove(x)

def deleteFirst(lst):
	lst.pop(0)

def deleteLast(lst):
	lst.pop()


for i in range(n):
	c = sys.stdin.readline().strip().split(" ")
	if c[0]=="insert":
		l.insert(0,int(c[1]))
	elif c[0]=="delete":
		delete(l,int(c[1]))
	elif c[0]=="deleteFirst":
		deleteFirst(l)
	elif c[0]=="deleteLast":
		deleteLast(l)

for a in l:
	print(a),

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
array = []
for i in range(n):
    cmd, *key = input().split()
    if type(key) == list:
        for i in key:
            key = i
    if cmd == "insert":
        array.insert(0, key)
    elif cmd == "delete":
        if key in array:
            array.remove(key)
    elif cmd == "deleteFirst":
        del array[0]
    else:
        array.pop()
for i in range(len(array)):
    if i == len(array) - 1:
        print(array[i])
    else:
        print(array[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
def linked_list(array, com, key):
    if com == "insert":
        array.insert(0, key)
    elif com == "delete":
        if key in array:
            array.remove(key)
    elif com == "deleteFirst":
        if len(array):
            del array[0]
    else:
        if len(array):
            array.pop()

    return array

n = int(input())
array = []
for i in range(n):
    com, *key = input().split()
    if key != []:
        key = int(key[0])
    linked_list(array, com, key)

l = len(array)
for i in range(l):
    if i == l - 1:
        print(array[i])
    else:
        print(array[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

class Node:
    def __init__(self, num):
        self.prev = None
        self.next_node = None
        self.num = num
    def delete(self):
        if self.prev is not None:
            self.prev.next_node = self.next_node
        if self.next_node is not None:
            self.next_node.prev = self.prev

class LinkedList:
    def __init__(self):
        self.start_node = None
        self.last_node = None
    def add(self, num):
        node = Node(num)
        if self.start_node is None:
            self.start_node = node
            self.last_node = node
        elif self.last_node is None:
            self.last_node = self.start_node
            node.next_node = self.last_node
            self.last_node.prev = node
            self.start_node = node
        else:   
            self.start_node.prev = node
            node.next_node = self.start_node
            self.start_node = node
    def delete(self, num):
        node = self.start_node
        while node is not None:
            if node.num == num:
                if node == self.start_node:
                    self.delete_first()
                elif node == self.last_node:
                    self.delete_last()
                else:
                    node.delete()
                break
            node = node.next_node
    def delete_last(self):
        if self.start_node == self.last_node:
            self.start_node = None
            self.last_node = None
        else:
            node = self.last_node
            self.last_node = self.last_node.prev
            node.delete()
    def delete_first(self):
        if self.start_node == self.last_node:
            self.start_node = None
            self.last_node = None
        else:
            node = self.start_node
            self.start_node = self.start_node.next_node
            node.delete()
    def __str__(self):
        s = ""
        node = self.start_node
        while node is not None:
            s += str(node.num) + " "
            node = node.next_node
        return s.strip()

def main():
    linked_list = LinkedList()
    c_num = int(stdin.readline().strip())
    for i in xrange(0, c_num):
        line = stdin.readline().strip().split(" ")
        op = line[0]
        if op == "insert":
            linked_list.add(int(line[1]))
        if op == "delete":
            linked_list.delete(int(line[1]))
        if op == "deleteFirst":
            linked_list.delete_first()
        if op == "deleteLast":
            linked_list.delete_last()
        #print linked_list
    print str(linked_list)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

class Node:
    def __init__(self, num):
        self.prev = None
        self.next_node = None
        self.num = num
    def delete(self):
        if self.prev is not None:
            self.prev.next_node = self.next_node
        if self.next_node is not None:
            self.next_node.prev = self.prev

class LinkedList:
    def __init__(self):
        self.start_node = None
        self.last_node = None
    def add(self, num):
        node = Node(num)
        if self.start_node is None:
            self.start_node = node
            self.last_node = node
        elif self.last_node is None:
            self.last_node = self.start_node
            node.next_node = self.last_node
            self.last_node.prev = node
            self.start_node = node
        else:   
            self.start_node.prev = node
            node.next_node = self.start_node
            self.start_node = node
    def delete(self, num):
        node = self.start_node
        while node is not None:
            if node.num == num:
                if node == self.start_node:
                    self.delete_first()
                elif node == self.last_node:
                    self.delete_last()
                else:
                    node.delete()
                break
            node = node.next_node
    def delete_last(self):
        if self.start_node == self.last_node:
            self.start_node = None
            self.last_node = None
        else:
            node = self.last_node
            self.last_node = self.last_node.prev
            node.delete()
    def delete_first(self):
        if self.start_node == self.last_node:
            self.start_node = None
            self.last_node = None
        else:
            node = self.start_node
            self.start_node = self.start_node.next_node
            node.delete()
    def __str__(self):
        s = ""
        node = self.start_node
        while node is not None:
            s += str(node.num) + " "
            node = node.next_node
        return s.strip()

def main():
    linked_list = LinkedList()
    c_num = int(stdin.readline().strip())
    for i in range(0, c_num):
        line = stdin.readline().strip().split(" ")
        op = line[0]
        if op == "insert":
            linked_list.add(int(line[1]))
        if op == "delete":
            linked_list.delete(int(line[1]))
        if op == "deleteFirst":
            linked_list.delete_first()
        if op == "deleteLast":
            linked_list.delete_last()
        #print linked_list
    print(str(linked_list))
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
???????????£????????????
??\?????????????????????????????????????????£???????????????????£??????????????????????

insert x: ??£?????????????????????????????? x ?????????????´?????¶?????¶???????
delete x: ?????? x ??????????????????????´??????£????????????????????????????????????????????????????´?????????¨???????????´????????????????????????
deleteFirst?????????????????????????´???????????????????
deleteLast: ????????????????°????????´???????????????????
"""

class Dlist:
    MAX = 1000000
    
    def __init__(self):
        """ ????????????????????? """
        self.si = 0
        self.ei = 0
        self.cnt = 0
        self.data = [0 for r in range(Dlist.MAX)]

    def insert(self,x):
        """ ??£?????????????????????????????? x ?????????????´?????¶?????¶???? """
        self.si -= 1
        if self.si < 0:
            self.si = Dlist.MAX - 1
        self.data[self.si] = x
        self.cnt += 1

    def delete(self,x):
        """ ?????? x ??????????????????????´??????£????????????????????????????????????????????????????´?????????¨???????????´????????????????????????"""
        if self.cnt > 0:
            hit = False
            for i in range(self.cnt):
                pi = self.si + i
                if pi >= Dlist.MAX:
                    pi -= Dlist.MAX
                if self.data[pi] == x:
                    hit = True
                    break
            if hit == True:
                for j in range(i, self.cnt):
                    pi = self.si + j
                    if pi >= Dlist.MAX:
                        pi -= Dlist.MAX
                    ni = pi + 1
                    if ni >= Dlist.MAX:
                        ni -= Dlist.MAX
                    self.data[pi] = self.data[ni]
                self.ei -= 1
                if self.ei < 0 :
                    self.ei = Dlist.MAX - 1
                self.cnt -= 1
            
    def deleteFirst(self):
        """ ?????????????????????????´???????????????? """
        if self.cnt > 0:
            self.data[self.si] = 0
            self.si += 1
            if self.si >= Dlist.MAX:
                self.si = 0
            self.cnt -= 1

    def deleteLast(self):
        """ ????????????????°????????´???????????????????"""
        if self.cnt > 0:
            self.ei -= 1
            if self.ei < 0 :
                self.ei = Dlist.MAX - 1
            self.data[self.ei] = 0
            self.cnt -= 1

    def getList(self):
        return self.data[self.si:self.ei]

# ?????????
num = int(input().strip())
dl = Dlist()

for i in range(num):
    cmd = list(input().strip().split())
    if cmd[0] == "insert":
        dl.insert(cmd[1])
    elif cmd[0] == "delete":
        dl.delete(cmd[1])
    elif cmd[0] == "deleteFirst":
        dl.deleteFirst()
    elif cmd[0] == "deleteLast":
        dl.deleteLast()

#   print()
#    print(cmd)
#    print("si={} ei={} cnt={}".format(dl.si, dl.ei, dl.cnt))
#    print(dl.data)

print(" ".join(map(str,dl.getList())))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
???????????£????????????
??\?????????????????????????????????????????£???????????????????£??????????????????????

insert x: ??£?????????????????????????????? x ?????????????´?????¶?????¶???????
delete x: ?????? x ??????????????????????´??????£????????????????????????????????????????????????????´?????????¨???????????´????????????????????????
deleteFirst?????????????????????????´???????????????????
deleteLast: ????????????????°????????´???????????????????
"""

# ?????????
num = int(input().strip())
dl = []

for i in range(num):
    cmd = list(input().strip().split())
    if cmd[0] == "insert":
        dl.insert(0,cmd[1])
    elif cmd[0] == "delete":
        try:
            dl.remove(cmd[1])
        except ValueError:
            i = 1
    elif cmd[0] == "deleteFirst":
        dl.pop(0)
    elif cmd[0] == "deleteLast":
        dl.pop()

print(" ".join(map(str,dl)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
???????????£????????????
??\?????????????????????????????????????????£???????????????????£??????????????????????

insert x: ??£?????????????????????????????? x ?????????????´?????¶?????¶???????
delete x: ?????? x ??????????????????????´??????£????????????????????????????????????????????????????´?????????¨???????????´????????????????????????
deleteFirst?????????????????????????´???????????????????
deleteLast: ????????????????°????????´???????????????????
"""
from collections import deque
# ?????????
num = int(input().strip())
dl = deque([])

for i in range(num):
    cmd = list(input().strip().split())
    if cmd[0] == "insert":
        dl.appendleft(str(cmd[1]))
    elif cmd[0] == "delete":
        try:
            dl.remove(str(cmd[1]))
        except ValueError:
            i = 1
    elif cmd[0] == "deleteFirst":
        dl.popleft()
    elif cmd[0] == "deleteLast":
        dl.pop()

print(" ".join(map(str,dl)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
???????????£????????????
??\?????????????????????????????????????????£???????????????????£??????????????????????

insert x: ??£?????????????????????????????? x ?????????????´?????¶?????¶???????
delete x: ?????? x ??????????????????????´??????£????????????????????????????????????????????????????´?????????¨???????????´????????????????????????
deleteFirst?????????????????????????´???????????????????
deleteLast: ????????????????°????????´???????????????????
"""
class DListItem:
    NoValue = -1

    def __init__(self,idx,value):
        """ ????????????????????? """
        self.prev = DListItem.NoValue
        self.next = DListItem.NoValue
        self.value = value


class Dlist:
    MAX = 1000000
    
    def __init__(self):
        """ ????????????????????? """
        self.si = -1
        self.ei = -1
        self.pos = -1
        self.uniqid = 0
        self.cnt = 0
        self.items = {}

    def __iter__(self):
        """ ????????¬?????? """
        if self.cnt != 0:
            self.pos = self.si
        else:
            self.pos = -1

        return self

    def __next__(self):
        """ ?¬???????????????? """
        if self.cnt == 0: # ???????????????
            raise StopIteration()
        elif self.items[self.pos].next == DListItem.NoValue: # ?¬??????????
            raise StopIteration()
        else:
            self.pos = self.items[self.pos].next
        return self.items[self.pos]

 
    def insert(self,x):
        """ ??£?????????????????????????????? x ?????????????´?????¶?????¶???? """

        if self.cnt == Dlist.MAX: # ??????????????????
            return -1

        t = DListItem(self.uniqid, x)

        if self.cnt == 0: # ?????????????´?
            self.ei = self.uniqid
        else:
            s = self.items[self.si]
            s.prev = self.uniqid
            t.next = self.si
        self.items[self.uniqid] = t
        self.si = self.uniqid
        self.uniqid += 1
        self.cnt += 1
        return t
    
    def delete(self,x):
        """ ?????? x ??????????????????????´??????£????????????????????????????????????????????????????´?????????¨???????????´????????????????????????"""

        if self.cnt > 0:
            hit = False
            i = self.si
            while hit == False:
                if i == DListItem.NoValue:
                    break
                if self.items[i].value == x:
                    hit = True
                    if i == self.si:
                        self.deleteFirst() # ?????????????´??????????
                    elif i == self.ei:
                        self.deleteLast() # ????°????????´??????????
                    else:
                        n = self.items[i].next
                        p = self.items[i].prev
                        self.items[n].prev = p
                        self.items[p].next = n
                        del self.items[i]
                        self.cnt -= 1
                else:
                    i = self.items[i].next

    def deleteFirst(self):
        """ ?????????????????????????´???????????????? """
        if self.cnt > 0:
            n = self.items[self.si].next
            if n != DListItem.NoValue:
                self.items[n].prev = DListItem.NoValue
            del self.items[self.si]
            self.si = n
            self.cnt -= 1
            if self.cnt < 1:
                self.ei = DListItem.NoValue

    def deleteLast(self):
        """ ????????????????°????????´???????????????????"""
        if self.cnt > 0:
            p = self.items[self.ei].prev
            if p != DListItem.NoValue:
                self.items[p].next = DListItem.NoValue
            del self.items[self.ei]
            self.ei = p
            self.cnt -= 1
            if self.cnt < 1:
                self.si = DListItem.NoValue

    def getList(self):
        a = []
        if self.cnt > 0:
            i = self.si
            while i != DListItem.NoValue:
                a.append(self.items[i].value)
                i = self.items[i].next
        return a

    def debugList(self):
        a = []
        if self.cnt > 0:
            i = self.si
            while i != DListItem.NoValue:
                a.append("{} => {}".format(i,self.items[i].value))
                i = self.items[i].next
        return a

# ?????????
num = int(input().strip())
dl = Dlist()

for i in range(num):
    cmd = list(input().strip().split())
    if cmd[0] == "insert":
        dl.insert(cmd[1])
    elif cmd[0] == "delete":
        dl.delete(cmd[1])
    elif cmd[0] == "deleteFirst":
        dl.deleteFirst()
    elif cmd[0] == "deleteLast":
        dl.deleteLast()

#    print()
#    print(cmd)
#    print("si={} ei={} cnt={}".format(dl.si, dl.ei, dl.cnt))
#    print(dl.debugList())

print(" ".join(map(str,dl.getList())))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
???????????£????????????
??\?????????????????????????????????????????£???????????????????£??????????????????????

insert x: ??£?????????????????????????????? x ?????????????´?????¶?????¶???????
delete x: ?????? x ??????????????????????´??????£????????????????????????????????????????????????????´?????????¨???????????´????????????????????????
deleteFirst?????????????????????????´???????????????????
deleteLast: ????????????????°????????´???????????????????
"""
class DListItem:
    """ ??????????????¢?????????????????? """
    NoValue = -1

    def __init__(self,idx,value):
        """ ????????????????????? """
        self.prev = DListItem.NoValue
        self.next = DListItem.NoValue
        self.index = idx
        self.value = value

class Dlist:
    """ ??????????????????????????? """
    MAX = 1000000

    def __init__(self):
        """ ????????????????????? """
        self.si = -1
        self.ei = -1
        self.pos = -1
        self.uniqid = 0
        self.cnt = 0
        self.items = []

    def __iter__(self):
        """ ????????¬?????? """
        self.pos = self.si
        return self

    def __next__(self):
        """ ?¬???????????????? """
        if self.cnt == 0: # ???????????????
            raise StopIteration()
        elif self.items[self.pos].next == DListItem.NoValue: # ?¬??????????
            raise StopIteration()
        else:
            self.pos = self.items[self.pos].next
        return self.items[self.pos]

 
    def insert(self,x):
        """ ??£?????????????????????????????? x ?????????????´?????¶?????¶???? """

        if self.cnt == Dlist.MAX: # ??????????????????
            return -1

        t = DListItem(self.uniqid, x)

        if self.cnt == 0: # ?????????????´?
            self.ei = self.uniqid
        else:
            s = self.items[self.si]
            s.prev = self.uniqid
            t.next = self.si
        self.items.append(t)
        self.si = self.uniqid
        self.uniqid += 1
        self.cnt += 1
        return t
    
    def delete(self,x):
        """ ?????? x ??????????????????????´??????£????????????????????????????????????????????????????´?????????¨???????????´????????????????????????"""

        if self.cnt > 0:
            hit = False
            i = self.si
            while hit == False:
                if i == DListItem.NoValue:
                    break
                if self.items[i].value == x:
                    hit = True
                    if i == self.si:
                        self.deleteFirst() # ?????????????´??????????
                    elif i == self.ei:
                        self.deleteLast() # ????°????????´??????????
                    else:
                        n = self.items[i].next
                        p = self.items[i].prev
                        self.items[n].prev = p
                        self.items[p].next = n
                        self.items[i].value = DListItem.NoValue
                        self.cnt -= 1
                else:
                    i = self.items[i].next

    def deleteFirst(self):
        """ ?????????????????????????´???????????????? """
        if self.cnt > 0:
            n = self.items[self.si].next
            if n != DListItem.NoValue:
                self.items[n].prev = DListItem.NoValue
            self.items[self.si] = DListItem.NoValue
            self.si = n
            self.cnt -= 1
            if self.cnt < 1:
                self.ei = DListItem.NoValue

    def deleteLast(self):
        """ ????????????????°????????´???????????????????"""
        if self.cnt > 0:
            p = self.items[self.ei].prev
            if p != DListItem.NoValue:
                self.items[p].next = DListItem.NoValue
            self.items[self.ei] = DListItem.NoValue
            self.ei = p
            self.cnt -= 1
            if self.cnt < 1:
                self.si = DListItem.NoValue

    def getList(self):
        a = []
        if self.cnt > 0:
            i = self.si
            while i != DListItem.NoValue:
                a.append(self.items[i].value)
                i = self.items[i].next
        return a

    def debugList(self):
        a = []
        if self.cnt > 0:
            i = self.si
            while i != DListItem.NoValue:
                a.append("{} => {}".format(i,self.items[i].value))
                i = self.items[i].next
        return a

# ?????????
num = int(input().strip())
dl = Dlist()

for i in range(num):
    cmd = list(input().strip().split())
    if cmd[0] == "insert":
        dl.insert(cmd[1])
    elif cmd[0] == "delete":
        dl.delete(cmd[1])
    elif cmd[0] == "deleteFirst":
        dl.deleteFirst()
    elif cmd[0] == "deleteLast":
        dl.deleteLast()

#    print()
#    print(cmd)
#    print("si={} ei={} cnt={}".format(dl.si, dl.ei, dl.cnt))
#    print(dl.debugList())

print(" ".join(map(str, dl.getList())))