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:
class Deque:
    class Node:  # ??????????????????
        def __init__(self, x, y=None, z=None):
            self.key = x
            self.next = y
            self.prev = z

        def search(self, x):  # listSearch??¨???????????????????????????????????????
            if(self.key == x or self.key is None):
                return self
            else:
                return self.prev.search(x)

        def delete(self):
            self.prev.next = self.next
            self.next.prev = self.prev

    def __init__(self):
        self.size = 0
        self.head = Deque.Node(None)
        self.tail = Deque.Node(None, self.head, None)
        self.head.prev = self.tail

    # insert x:??£??????????????????????????????x?????????????´???????????¶????
    def insert(self, x):
        p = Deque.Node(x, self.head, self.head.prev)
        self.head.prev.next = p
        self.head.prev = p
        self.size += 1

    # deleteFirst:??£????????????????????????????´???????????????????
    def deleteFirst(self):
        if self.size == 0:
            raise IndexError
        self.head.prev.delete()
        self.size -= 1

    # deleteLast:??£???????????????????°????????´???????????????????
    def deleteLast(self):
        if self.size == 0:
            raise IndexError
        self.tail.next.delete()
        self.size -= 1

    # ???????????????????????¢?´¢
    def listSearch(self, x):
        return self.head.prev.search(x)

    # ??¢?´¢?????\????£?
    def listSearch2(self, x):
        node = self.tail.next
        while(node.key is not None):
            if(node.key == x):
                return node
            else:
                node = node.next

    # delete:x???????????????????´??????????????????°?????¢?´¢????????¨
    def delete(self, x):
        if self.size == 0:
            raise IndexError
        node = self.listSearch(x)
        if(node.key is not None):
            node.delete()
        self.size -= 1

    # ??????
    def printList(self):
        ret = []
        node = self.head.prev
        while node.key is not None:
            ret.append(str(node.key))
            node = node.prev
        print(" ".join(ret))


n = int(input())
d = Deque()
for i in range(n):
    i = input().split()
    if i[0] == "insert":
        x = int(i[1])
        d.insert(x)
    if i[0] == "delete":
        x = int(i[1])
        d.delete(x)
    if i[0] == "deleteFirst":
        d.deleteFirst()
    if i[0] == "deleteLast":
        d.deleteLast()
d.printList()

Submission status: Time Limit Exceeded

Solution code:
#ALDS1_3-C Elementary data structures - Doubly Linked List
n=int(input())
cmds={"insert":lambda cmd: L.insert(0,cmd[1]),
      "delete":lambda cmd: L.remove(cmd[1]) if (cmd[1] in L) else "none",
      "deleteFirst":lambda cmd: L.pop(0),
      "deleteLast": lambda cmd: L.pop()
     }
L=[]
for i in range(n):
    cmd=input().split()
    cmds[cmd[0]](cmd)
s=""
for i in L:
    s+=i+" "
print(s[:-1])

Submission status: Time Limit Exceeded

Solution code:
import sys


class Deque:
    class Node:  # ??????????????????
        def __init__(self, x, y=None, z=None):
            self.key = x
            self.next = y
            self.prev = z

        def delete(self):
            self.prev.next = self.next
            self.next.prev = self.prev

    def __init__(self):
        self.size = 0
        self.head = Deque.Node(None)
        self.tail = Deque.Node(None, self.head, None)
        self.head.prev = self.tail

    # insert x:??£??????????????????????????????x?????????????´???????????¶????
    def insert(self, x):
        p = Deque.Node(x, self.head, self.head.prev)
        self.head.prev.next = p
        self.head.prev = p
        self.size += 1

    # deleteFirst:??£????????????????????????????´???????????????????
    def deleteFirst(self):
        if self.size == 0:
            raise IndexError
        self.head.prev.delete()
        self.size -= 1

    # deleteLast:??£???????????????????°????????´???????????????????
    def deleteLast(self):
        if self.size == 0:
            raise IndexError
        self.tail.next.delete()
        self.size -= 1

    # ???????????????????????¢?´¢
    def listSearch(self, x):
        node = self.head.prev
        while(node.key != x and node.key is not None):
            node = node.prev
        return node

    # delete:x???????????????????´??????????????????°?????¢?´¢????????¨
    def delete(self, x):
        if self.size == 0:
            raise IndexError
        node = self.listSearch(x)
        if(node.key is not None):
            node.delete()
        self.size -= 1

    # ??????
    def printList(self):
        ret = []
        node = self.head.prev
        while node.key is not None:
            ret.append(str(node.key))
            node = node.prev
        print(" ".join(ret))


n = int(input())
d = Deque()
for inpt in sys.stdin.read().splitlines():
    i = inpt.split()
    #print(i)
    if i[0] == "insert":
        x = int(i[1])
        d.insert(x)
    if i[0] == "delete":
        x = int(i[1])
        d.delete(x)
    if i[0] == "deleteFirst":
        d.deleteFirst()
    if i[0] == "deleteLast":
        d.deleteLast()
d.printList()

Submission status: Time Limit Exceeded

Solution code:
import sys
res = dict()
dll = [None] * 2000000
left = 0
right = 0
n = int(input())
for inpt in sys.stdin.read().splitlines():
    i = inpt.split()
    if i[0] == "insert":
        x = int(i[1])
        dll[left] = x
        if(x in res):
            res[x].append(left)
        else:
            res[x] = [left]
        left += 1
    if i[0] == "delete":
        x = int(i[1])
        if(x in res):
            ind = max(res[x])
            dll[ind] = None
            res[x].remove(ind)
            if(len(res[x]) == 0):
                del res[x]
            if(ind == (left - 1)):
                left = ind
            if(ind == right):
                right += 1
    if i[0] == "deleteFirst":
        left -= 1
        x = dll[left]
        res[x].remove(left)
        if(len(res[x]) == 0):
            del res[x]
        dll[left] = None
    if i[0] == "deleteLast":
        right += 1
    # print(dll[right:left])
ret = []
for x in dll[right:left]:
    if(x is not None):
        ret.append(str(x))
ret.reverse()
print(" ".join(ret))

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8
from collections import deque
n = int(input())
deque = deque()

for i in range(n):
    inp = list(input().split())
    if inp[0] == 'deleteFirst':
        deque.popleft()
    elif inp[0] == 'deleteLast':
        deque.pop()
    elif inp[0] == 'insert':
        deque.appendleft(inp[1])
    elif inp[0] == 'delete':
        if inp[1] in deque:
            deque.remove(inp[1])

print(*deque)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Jun 21 08:50:28 2017

@author: syaga
"""

COMMAND = ["insert", "delete", "deleteFirst", "deleteLast"]

if __name__ == "__main__":
    n = int(input())
    com = []
    for i in range(n):
        com.append(input().split())
    ans = []
    for i in com:
        if i[0] == COMMAND[0]:
            ans.insert(0, i[1])
        elif i[0] == COMMAND[1]:
            if i[1] in ans:
                ans.remove(i[1])
        elif i[0] == COMMAND[2]:
            ans.pop(0)
        elif i[0] == COMMAND[3]:
            ans.pop()
    print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Jun 21 09:13:28 2017

@author: syaga
"""

COMMAND = ["insert", "delete", "deleteFirst", "deleteLast"]

if __name__ == "__main__":
    n = int(input())
    com = []
    for i in range(n):
        com.append(input().split())
    ans = []
    for i in com:
        if i[0] == COMMAND[0]:
            ans.append(i[1])
        elif i[0] == COMMAND[1]:
            if i[1] in ans:
                ind = len(ans)-1-ans[::-1].index(i[1])
                del ans[ind]
        elif i[0] == COMMAND[2]:
            ans.pop()
        elif i[0] == COMMAND[3]:
            ans.pop(0)
    ans.reverse()
    print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import deque

COMMAND = ("insert", "delete", "deleteFirst", "deleteLast")

if __name__ == "__main__":
    n = int(input())
    com = []
    for i in range(n):
        com.append(input().split())
    ans = deque()
    for i in com:
        if i[0] == COMMAND[0]:
            ans.appendleft(i[1])
        elif i[0] == COMMAND[1]:
            if i[1] in ans:
                ans.remove(i[1])
        elif i[0] == COMMAND[2]:
            ans.popleft()
        elif i[0] == COMMAND[3]:
            ans.pop()
    print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
n=int(raw_input())
lst = []
for _ in range(n):
    cmd = raw_input().split()
    if cmd[0] == "insert":
        lst.insert(0, int(cmd[1]))
    elif cmd[0] == "delete":
        if int(cmd[1]) in lst:
            lst.remove(int(cmd[1]))
    elif cmd[0] == "deleteFirst":
        if len(lst) > 0:
            lst.pop(0)
    elif cmd[0] == "deleteLast":
        if len(lst) > 0:
            lst.pop(-1)

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

Submission status: Time Limit Exceeded

Solution code:
class DLList:
    class Cell:
        def __init__(self, data, pre, nex):
            self.data = data
            self.pre = pre
            self.nex = nex
    
    def __init__(self):
        self.top = DLList.Cell(None, None, None)

    def insert(self, x):
        if self.top.nex == None:
            w = DLList.Cell(x, self.top, self.top)
            self.top.nex = w
            self.top.pre = w
        else:
            w = DLList.Cell(x, self.top, self.top.nex)
            self.top.nex.pre = w
            self.top.nex = w
            
    def delete(self, x):
        w = self.top.nex
        while w != self.top:
            if w.data == x:
                w.pre.nex = w.nex
                w.nex.pre = w.pre
                break
            w = w.nex
            
    def deleteFirst(self):
        w = self.top.nex
        w.pre.nex = w.nex
        w.nex.pre = w.pre
     
    def deleteLast(self):
        w = self.top.pre
        w.pre.nex = w.nex
        w.nex.pre = w.pre 
           
    def pri(self):
        w = self.top.nex
        while w != self.top:
            if w.nex == self.top:
                print(w.data)
                break
            else:
                print(w.data,end=" ")
            w = w.nex

a = DLList()
n = int(input())
for i in range(n):
    s = input().split(" ")
    if s[0] == "insert":
        a.insert(int(s[1]))
    elif s[0] == "delete":
        a.delete(int(s[1]))
    elif s[0] == "deleteLast":
        a.deleteLast()
    elif s[0] == "deleteFirst":
        a.deleteFirst()
a.pri()

Submission status: Time Limit Exceeded

Solution code:
class DLList:
    class Cell:
        def __init__(self, data, pre, nex):
            self.data = data
            self.pre = pre
            self.nex = nex
    
    def __init__(self):
        self.top = DLList.Cell(None,None,None)
        self.top.nex = self.top

    def insert(self, x):
        w = DLList.Cell(x, self.top, self.top.nex)
        self.top.nex.pre = w
        self.top.nex = w
            
    def delete(self, x):
        w = self.top.nex
        while w != self.top:
            if w.data == x:
                w.pre.nex = w.nex
                w.nex.pre = w.pre
                break
            w = w.nex
            
    def deleteFirst(self):
        w = self.top.nex
        w.pre.nex = w.nex
        w.nex.pre = w.pre
     
    def deleteLast(self):
        w = self.top.pre
        w.pre.nex = w.nex
        w.nex.pre = w.pre 
           
    def pri(self):
        w = self.top.nex
        while w != self.top:
            if w.nex == self.top:
                print(w.data)
                break
            else:
                print(w.data,end=" ")
            w = w.nex

a = DLList()
n = int(input())
for i in range(n):
    s = input().split(" ")
    if s[0] == "insert":
        a.insert(int(s[1]))
    elif s[0] == "delete":
        a.delete(int(s[1]))
    elif s[0] == "deleteLast":
        a.deleteLast()
    elif s[0] == "deleteFirst":
        a.deleteFirst()
a.pri()

Submission status: Time Limit Exceeded

Solution code:
import sys

class Node:
    def __init__(self, num):
        self.prev = None
        self.next = None
        self.num = num
    def delete(self):
        if self.prev is not None:
            self.prev.next = self.next
        if self.next is not None:
            self.next.prev = self.prev
        
class LinkedList:
    def __init__(self):
        self.node_list = []
    def add(self, num):
        node = Node(num)
        if len(self.node_list) != 0:
            node.prev = self.node_list[-1]
            self.node_list[-1].next = node
        self.node_list.append(node)
    def delete(self, num):
        for (i, node) in enumerate(reversed(self.node_list)):
            if node.num == num:
                node.delete()
                self.node_list.pop(len(self.node_list) - i - 1)
                break
    def delete_last(self):
        self.node_list[0].delete()
        self.node_list.pop(0)
    def delete_first(self):
        self.node_list[-1].delete()
        self.node_list.pop()
    def __str__(self):
        s = ""
        for n in reversed(self.node_list):
            s += str(n.num) + " "
        s = s.strip()
        return 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(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 str(linked_list)
    
if __name__ == "__main__":
    main()

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.node_list = []
    def add(self, num):
        node = Node(num)
        if len(self.node_list) != 0:
            node.prev = self.node_list[-1]
            self.node_list[-1].next_node = node
        self.node_list.append(node)
    def delete(self, num):
        for (i, node) in enumerate(reversed(self.node_list)):
            if node.num == num:
                node.delete()
                self.node_list.pop(len(self.node_list) - i - 1)
                break
    def delete_last(self):
        self.node_list[0].delete()
        self.node_list.pop(0)
    def delete_first(self):
        self.node_list[-1].delete()
        self.node_list.pop()
    def __str__(self):
        s = ""
        for n in reversed(self.node_list):
            s += str(n.num) + " "
        s = s.strip()
        return s
'''

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(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(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:
import sys

def main():
    linked_list = []
    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.insert(0, int(line[1]))
        if op == "delete":
            for (i, num) in enumerate(linked_list):
                if int(line[1]) == num:
                    linked_list.pop(i)
                    break
        if op == "deleteFirst":
            linked_list.pop(0)
        if op == "deleteLast":
            linked_list.pop()
    s = ""
    for i in linked_list:
        s += str(i) + " "
    print s.strip()
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

class Node(object):
    def __init__(self, num, prv = None, nxt = None):
        self.num = num
        self.prv = prv
        self.nxt = nxt

class DoublyLinkedList(object):
    def __init__(self):
        self.start = self.last = None

    def insert(self, num):
        new_elem = Node(num)

        if self.start is None:
            self.start = self.last = new_elem
        else:
            new_elem.nxt = self.start
            self.start.prv = new_elem
            self.start = new_elem

    def delete_num(self, target):
        it = self.start
        while it is not None:
            if it.num == target:
                if it.prv is None and it.nxt is None:
                    self.start = self.last = None
                else:
                    if it.prv is not None:
                        it.prv.nxt = it.nxt
                    else:
                        self.start = self.start.nxt

                    if it.nxt is not None:
                        it.nxt.prv = it.prv
                    else:
                        self.last = self.last.prv
                break
            it = it.nxt

    def delete_start(self):
        if self.start is self.last:
            self.start = self.last = None
        else:
            self.start.nxt.prv = None
            self.start = self.start.nxt

    def delete_last(self):
        if self.start is self.last:
            self.start = self.last = None
        else:
            self.last.prv.nxt = None
            self.last = self.last.prv

    def get_content(self):
        ret = []
        it = self.start

        while it is not None:
            ret.append(it.num)
            it = it.nxt

        return ' '.join(ret)

    def get_rcontent(self):
        ret = []
        it = self.last

        while it is not None:
            ret.append(it.num)
            it = it.prv

        return ' '.join(ret)

def _main():
    n = int(input())

    lst = DoublyLinkedList()
    
    for _ in range(n):
        cmd = input().split()
        if cmd[0] == 'insert':
            lst.insert(cmd[1])
        elif cmd[0] == 'delete':
            lst.delete_num(cmd[1])
        elif cmd[0] == 'deleteFirst':
            lst.delete_start()
        elif cmd[0] == 'deleteLast':
            lst.delete_last()

    print(lst.get_content())

if __name__ == '__main__':
    _main()

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 += str(node.num) + " "
            node = node.next_node
        return s.strip()

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(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:
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):
        a = []
        node = self.start_node
        while node is not None:
            a.append(str(node.num))
            node = node.next_node

        return ' '.join(a)

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(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:
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 += node.num + " "
            node = node.next_node
        return s.strip()

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()