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:
# -*- coding: utf-8 -*-
    
class Node(object):
    """Node class
    """

    def __init__(self, key=None, previous_node=None, next_node=None):
        """Constructor
        """
        self.key = key
        ''' key '''

        self.previous_node = previous_node
        ''' previous node '''

        self.next_node = next_node
        ''' next node '''

    def copy_from(self, node):
        self.key = node.key
        self.previous_node = node.previous_node
        self.next_node = node.next_node

    def print_on(self, is_performance=False):
        if is_performance:
            print self.key, 
        else:
            print self.previous_node, str(self.key) + " at " + str(self), self.next_node


class DoublyLinkedList(object):
    """Doubly Linked List Class
    """

    def __init__(self, sentinel_key='SENTINEL'):
        """Constructor(make sentinel node)
        """
        self.sentinel_node = Node(key=sentinel_key)
        self.sentinel_node.next_node = self.sentinel_node
        self.sentinel_node.previous_node = self.sentinel_node

    def insert_node(self, key):
        """insert node which has specified key at first position"""
        
        # set new node
        new_node = Node(key=key, previous_node=self.sentinel_node, next_node=self.sentinel_node.next_node) 
        # re-set first_node
        self.sentinel_node.next_node.previous_node = new_node
        # re-set sentinel node
        self.sentinel_node.next_node = new_node

            

    def delete(self, key=None):
        """ delete node which has a key 'key' """
        target_node = self.sentinel_node.next_node
        while target_node is not self.sentinel_node:
            if target_node.key == key:
                target_node.previous_node.next_node = target_node.next_node
                target_node.next_node.previous_node = target_node.previous_node
                break
            else:
                target_node = target_node.next_node
    
    def delete_first(self):
        """ delete first node """
        # delete first node
        self.sentinel_node.next_node = self.sentinel_node.next_node.next_node
        self.sentinel_node.next_node.previous_node = self.sentinel_node

    def delete_last(self):
        """delete last node """
        self.sentinel_node.previous_node = self.sentinel_node.previous_node.previous_node
        self.sentinel_node.previous_node.next_node = self.sentinel_node

    def print_on(self, is_performance=False):
        target_node = self.sentinel_node
        if not is_performance:
            target_node.print_on(is_performance)
        while target_node.next_node is not self.sentinel_node:
            target_node = target_node.next_node
            target_node.print_on(is_performance)
            

def main():
    doubly_linked_list = DoublyLinkedList()

    input_length = int(raw_input())
    counter = 0
    while counter < input_length:
        counter += 1
        input_line = raw_input().strip()
        # print input_line
        if input_line == 'deleteFirst':
            doubly_linked_list.delete_first()
            continue
        elif input_line == 'deleteLast':
            doubly_linked_list.delete_last()
            continue

        input_command = input_line.split(' ')[0].strip()
        input_key = input_line.split(' ')[1].strip()
        if input_command == 'insert':
            doubly_linked_list.insert_node(input_key)
        elif input_command == 'delete':
            doubly_linked_list.delete(input_key)
        else:
            "baka"
    doubly_linked_list.print_on(is_performance=True)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
    
class Node(object):
    """Node class
    """

    def __init__(self, key=None, previous_node=None, next_node=None):
        """Constructor
        """
        self.key = key
        ''' key '''

        self.previous_node = previous_node
        ''' previous node '''

        self.next_node = next_node
        ''' next node '''

    def copy_from(self, node):
        self.key = node.key
        self.previous_node = node.previous_node
        self.next_node = node.next_node

    def print_on(self, is_performance=False):
        if is_performance:
            print self.key, 
        else:
            print self.previous_node, str(self.key) + " at " + str(self), self.next_node


class DoublyLinkedList(object):
    """Doubly Linked List Class
    """

    def __init__(self, sentinel_key='SENTINEL'):
        """Constructor(make sentinel node)
        """
        self.sentinel_node = Node(key=sentinel_key)
        self.sentinel_node.next_node = self.sentinel_node
        self.sentinel_node.previous_node = self.sentinel_node

    def insert_node(self, key):
        """insert node which has specified key at first position"""
        
        # set new node
        new_node = Node(key=key, previous_node=self.sentinel_node, next_node=self.sentinel_node.next_node) 
        # re-set first_node
        self.sentinel_node.next_node.previous_node = new_node
        # re-set sentinel node
        self.sentinel_node.next_node = new_node

            

    def delete(self, key=None):
        """ delete node which has a key 'key' """
        target_node = self.sentinel_node.next_node
        while target_node is not self.sentinel_node:
            if target_node.key == key:
                target_node.previous_node.next_node = target_node.next_node
                target_node.next_node.previous_node = target_node.previous_node
                break
            else:
                target_node = target_node.next_node
    
    def delete_first(self):
        """ delete first node """
        # delete first node
        self.sentinel_node.next_node = self.sentinel_node.next_node.next_node
        self.sentinel_node.next_node.previous_node = self.sentinel_node

    def delete_last(self):
        """delete last node """
        self.sentinel_node.previous_node = self.sentinel_node.previous_node.previous_node
        self.sentinel_node.previous_node.next_node = self.sentinel_node

    def print_on(self, is_performance=False):
        target_node = self.sentinel_node
        if not is_performance:
            target_node.print_on(is_performance)
        while target_node.next_node is not self.sentinel_node:
            target_node = target_node.next_node
            target_node.print_on(is_performance)
            

def main():
    doubly_linked_list = DoublyLinkedList()

    input_length = int(raw_input())
    counter = 0
    while counter < input_length:
        counter += 1
        input_line = raw_input().strip()
        # print input_line
        if input_line == 'deleteFirst':
            doubly_linked_list.delete_first()
            continue
        elif input_line == 'deleteLast':
            doubly_linked_list.delete_last()
            continue

        input_command = input_line.split(' ')[0].strip()
        input_key = input_line.split(' ')[1].strip()
        if input_command == 'insert':
            doubly_linked_list.insert_node(input_key)
        elif input_command == 'delete':
            pass
            doubly_linked_list.delete(input_key)
        else:
            "baka"
    doubly_linked_list.print_on(is_performance=True)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
    
class Node(object):
    """Node class
    """

    def __init__(self, key=None, previous_node=None, next_node=None):
        """Constructor
        """
        self.key = key
        ''' key '''

        self.previous_node = previous_node
        ''' previous node '''

        self.next_node = next_node
        ''' next node '''

    def copy_from(self, node):
        self.key = node.key
        self.previous_node = node.previous_node
        self.next_node = node.next_node

    def print_on(self, is_performance=False):
        if is_performance:
            pass
            print self.key, 
        else:
            print self.previous_node, str(self.key) + " at " + str(self), self.next_node


class DoublyLinkedList(object):
    """Doubly Linked List Class
    """

    def __init__(self, sentinel_key='SENTINEL'):
        """Constructor(make sentinel node)
        """
        self.sentinel_node = Node(key=sentinel_key)
        self.sentinel_node.next_node = self.sentinel_node
        self.sentinel_node.previous_node = self.sentinel_node

    def insert_node(self, key):
        """insert node which has specified key at first position"""
        
        # set new node
        new_node = Node(key=key, previous_node=self.sentinel_node, next_node=self.sentinel_node.next_node) 
        # re-set first_node
        self.sentinel_node.next_node.previous_node = new_node
        # re-set sentinel node
        self.sentinel_node.next_node = new_node

            
    def delete(self, key=None):
        """ delete node which has a key 'key' """
        target_node = self.sentinel_node.next_node
        while target_node is not self.sentinel_node:
            if target_node.key == key:
                target_node.previous_node.next_node = target_node.next_node
                target_node.next_node.previous_node = target_node.previous_node
                break
            else:
                target_node = target_node.next_node
    
    def delete_first(self):
        """ delete first node """
        # delete first node
        self.sentinel_node.next_node = self.sentinel_node.next_node.next_node
        self.sentinel_node.next_node.previous_node = self.sentinel_node

    def delete_last(self):
        """delete last node """
        self.sentinel_node.previous_node = self.sentinel_node.previous_node.previous_node
        self.sentinel_node.previous_node.next_node = self.sentinel_node

    def print_on(self, is_performance=False):
        target_node = self.sentinel_node
        if not is_performance:
            target_node.print_on(is_performance)
        while target_node.next_node is not self.sentinel_node:
            target_node = target_node.next_node
            target_node.print_on(is_performance)
            

def main():
    doubly_linked_list = DoublyLinkedList()

    input_length = int(raw_input())
    counter = 0
    while counter < input_length:
        counter += 1
        input_line = raw_input().strip()
        # print input_line
        if input_line == 'deleteFirst':
            doubly_linked_list.delete_first()
            continue
        elif input_line == 'deleteLast':
            doubly_linked_list.delete_last()
            continue

        input_command = input_line.split(' ')[0].strip()
        input_key = input_line.split(' ')[1].strip()
        if input_command == 'insert':
            doubly_linked_list.insert_node(input_key)
        elif input_command == 'delete':
            pass
            doubly_linked_list.delete(input_key)
    doubly_linked_list.print_on(is_performance=True)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

class Node(object):
    """Node class
    """

    def __init__(self, key=None, previous_node=None, next_node=None):
        """Constructor
        """
        self.key = key
        ''' key '''

        self.previous_node = previous_node
        ''' previous node '''

        self.next_node = next_node
        ''' next node '''

    def copy_from(self, node):
        self.key = node.key
        self.previous_node = node.previous_node
        self.next_node = node.next_node

    def print_on(self, is_performance=False):
        if is_performance:
            pass
            print self.key, 
        else:
            print self.previous_node, str(self.key) + " at " + str(self), self.next_node


class DoublyLinkedList(object):
    """Doubly Linked List Class
    """

    def __init__(self, sentinel_key='SENTINEL'):
        """Constructor(make sentinel node)
        """
        self.sentinel_node = Node(key=sentinel_key)
        self.sentinel_node.next_node = self.sentinel_node
        self.sentinel_node.previous_node = self.sentinel_node

    def insert_node(self, key):
        """insert node which has specified key at first position"""
        
        # set new node
        new_node = Node(key=key, previous_node=self.sentinel_node, next_node=self.sentinel_node.next_node) 
        # re-set first_node
        self.sentinel_node.next_node.previous_node = new_node
        # re-set sentinel node
        self.sentinel_node.next_node = new_node

            
    def delete(self, key=None):
        """ delete node which has a key 'key' """
        target_node = self.sentinel_node.next_node
        while target_node is not self.sentinel_node:
            if target_node.key == key:
                target_node.previous_node.next_node = target_node.next_node
                target_node.next_node.previous_node = target_node.previous_node
                break
            else:
                target_node = target_node.next_node
    
    def delete_first(self):
        """ delete first node """
        # delete first node
        self.sentinel_node.next_node = self.sentinel_node.next_node.next_node
        self.sentinel_node.next_node.previous_node = self.sentinel_node

    def delete_last(self):
        """delete last node """
        self.sentinel_node.previous_node = self.sentinel_node.previous_node.previous_node
        self.sentinel_node.previous_node.next_node = self.sentinel_node

    def print_on(self, is_performance=False):
        target_node = self.sentinel_node
        if not is_performance:
            target_node.print_on(is_performance)
        while target_node.next_node is not self.sentinel_node:
            target_node = target_node.next_node
            target_node.print_on(is_performance)
            

def main():
    doubly_linked_list = DoublyLinkedList()

    input_length = int(raw_input())
    counter = 0
    while counter < input_length:
        counter += 1
        input_line = raw_input()
        identifier = input_line[6]
        if identifier is 'F':
            doubly_linked_list.delete_first()
            continue
        elif identifier is 'L':
            doubly_linked_list.delete_last()
            continue

        input_command, input_key = input_line.split(' ')
        if input_command == 'insert':
            doubly_linked_list.insert_node(input_key)
        #elif input_command == 'delete':
        else:
            doubly_linked_list.delete(input_key)
    doubly_linked_list.print_on(is_performance=True)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

class Node(object):
    """Node class
    """

    def __init__(self, key=None, previous_node=None, next_node=None):
        """Constructor
        """
        self.key = key
        ''' key '''

        self.previous_node = previous_node
        ''' previous node '''

        self.next_node = next_node
        ''' next node '''

    def copy_from(self, node):
        self.key = node.key
        self.previous_node = node.previous_node
        self.next_node = node.next_node

    def print_on(self):
        print self.key, 


class DoublyLinkedList(object):
    """Doubly Linked List Class
    """

    def __init__(self, sentinel_key='SENTINEL'):
        """Constructor(make sentinel node)
        """
        self.sentinel_node = Node(key=sentinel_key)
        self.sentinel_node.next_node = self.sentinel_node
        self.sentinel_node.previous_node = self.sentinel_node

    def insert_node(self, key):
        """insert node which has specified key at first position"""
        
        # set new node
        new_node = Node(key=key, previous_node=self.sentinel_node, next_node=self.sentinel_node.next_node) 
        # re-set first_node
        self.sentinel_node.next_node.previous_node = new_node
        # re-set sentinel node
        self.sentinel_node.next_node = new_node

            
    def delete(self, key=None):
        """ delete node which has a key 'key' """
        target_node = self.sentinel_node.next_node
        while target_node is not self.sentinel_node:
            if target_node.key == key:
                target_node.previous_node.next_node = target_node.next_node
                target_node.next_node.previous_node = target_node.previous_node
                break
            else:
                target_node = target_node.next_node
    
    def delete_first(self):
        """ delete first node """
        # delete first node
        self.sentinel_node.next_node = self.sentinel_node.next_node.next_node
        self.sentinel_node.next_node.previous_node = self.sentinel_node

    def delete_last(self):
        """delete last node """
        self.sentinel_node.previous_node = self.sentinel_node.previous_node.previous_node
        self.sentinel_node.previous_node.next_node = self.sentinel_node

    def print_on(self):
        target_node = self.sentinel_node
        while target_node.next_node is not self.sentinel_node:
            target_node = target_node.next_node
            target_node.print_on()
            

def main():
    doubly_linked_list = DoublyLinkedList()

    input_length = int(raw_input())
    counter = 0
    while counter < input_length:
        counter += 1
        input_line = raw_input()
        if input_line[0] == 'i':
            doubly_linked_list.insert_node(input_line[7:])
        elif input_line[6] == 'F':
            doubly_linked_list.delete_first()
        elif input_line[6] == 'L':
            doubly_linked_list.delete_last()
        else:
            doubly_linked_list.delete(input_line[7:])

    doubly_linked_list.print_on()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

class Node(object):
    """Node class
    """

    def __init__(self, key=None, previous_node=None, next_node=None):
        """Constructor
        """
        self.key = key
        ''' key '''

        self.previous_node = previous_node
        ''' previous node '''

        self.next_node = next_node
        ''' next node '''

    def copy_from(self, node):
        self.key = node.key
        self.previous_node = node.previous_node
        self.next_node = node.next_node

    def print_on(self):
        print self.key, 


class DoublyLinkedList(object):
    """Doubly Linked List Class
    """

    def __init__(self, sentinel_key=-1):
        """Constructor(make sentinel node)
        """
        self.sentinel_node = Node(key=sentinel_key)
        self.sentinel_node.next_node = self.sentinel_node
        self.sentinel_node.previous_node = self.sentinel_node

    def insert_node(self, key):
        """insert node which has specified key at first position"""
        
        # set new node
        new_node = Node(key=key, previous_node=self.sentinel_node, next_node=self.sentinel_node.next_node) 
        # re-set first_node
        self.sentinel_node.next_node.previous_node = new_node
        # re-set sentinel node
        self.sentinel_node.next_node = new_node

            
    def delete(self, key=None):
        """ delete node which has a key 'key' """
        target_node = self.sentinel_node.next_node
        while target_node.key is not -1:
            if target_node.key == key:
                target_node.previous_node.next_node = target_node.next_node
                target_node.next_node.previous_node = target_node.previous_node
                break
            else:
                target_node = target_node.next_node
    
    def delete_first(self):
        """ delete first node """
        # delete first node
        self.sentinel_node.next_node = self.sentinel_node.next_node.next_node
        self.sentinel_node.next_node.previous_node = self.sentinel_node

    def delete_last(self):
        """delete last node """
        self.sentinel_node.previous_node = self.sentinel_node.previous_node.previous_node
        self.sentinel_node.previous_node.next_node = self.sentinel_node

    def print_on(self):
        target_node = self.sentinel_node
        while target_node.next_node is not self.sentinel_node:
            target_node = target_node.next_node
            target_node.print_on()
            

def main():
    doubly_linked_list = DoublyLinkedList()

    input_length = int(raw_input())
    counter = 0
    while counter < input_length:
        counter += 1
        input_line = raw_input()
        if input_line[0] == 'i':
            doubly_linked_list.insert_node(input_line[7:])
        elif input_line[6] == 'F':
            doubly_linked_list.delete_first()
        elif input_line[6] == 'L':
            doubly_linked_list.delete_last()
        else:
            doubly_linked_list.delete(input_line[7:])

    doubly_linked_list.print_on()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

class Node(object):
    """Node class
    """

    def __init__(self, key=None, previous_node=None, next_node=None):
        """Constructor
        """
        self.key = key
        ''' key '''

        self.previous_node = previous_node
        ''' previous node '''

        self.next_node = next_node
        ''' next node '''

    def copy_from(self, node):
        self.key = node.key
        self.previous_node = node.previous_node
        self.next_node = node.next_node

    def print_on(self):
        print self.key, 


class DoublyLinkedList(object):
    """Doubly Linked List Class
    """

    def __init__(self, sentinel_key=-1):
        """Constructor(make sentinel node)
        """
        self.sentinel_node = Node(key=sentinel_key)
        self.sentinel_node.next_node = self.sentinel_node
        self.sentinel_node.previous_node = self.sentinel_node

    def insert_node(self, key):
        """insert node which has specified key at first position"""
        
        new_node = Node(key=key, previous_node=self.sentinel_node, next_node=self.sentinel_node.next_node) 
        self.sentinel_node.next_node.previous_node = new_node
        self.sentinel_node.next_node = new_node
              
    def delete_first(self):
        """ delete first node """
        if self.sentinel_node.next_node.key != -1:
            self.sentinel_node.next_node = self.sentinel_node.next_node.next_node
            self.sentinel_node.next_node.previous_node = self.sentinel_node

    def delete_last(self):
        """delete last node """
        if self.sentinel_node.next_node.key != -1:
            self.sentinel_node.previous_node = self.sentinel_node.previous_node.previous_node
            self.sentinel_node.previous_node.next_node = self.sentinel_node
 
    def delete(self, key=None):
        """ delete node which has a key 'key' """
        target_node = self.sentinel_node.next_node
        while target_node.key is not -1:
            if target_node.key == key:
                target_node.previous_node.next_node = target_node.next_node
                target_node.next_node.previous_node = target_node.previous_node
                break
            else:
                target_node = target_node.next_node
 
    def print_on(self):
        target_node = self.sentinel_node
        while target_node.next_node is not self.sentinel_node:
            target_node = target_node.next_node
            target_node.print_on()
            

def main():
    doubly_linked_list = DoublyLinkedList()

    input_length = int(raw_input())
    counter = 0
    while counter < input_length:
        counter += 1
        input_line = raw_input()
        if input_line[0] == 'i':
            doubly_linked_list.insert_node(input_line[7:])
        elif input_line[6] == 'F':
            doubly_linked_list.delete_first()
        elif input_line[6] == 'L':
            doubly_linked_list.delete_last()
        else:
            doubly_linked_list.delete(input_line[7:])

    doubly_linked_list.print_on()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

class Node(object):
    """Node class
    """

    def __init__(self, key=None, previous_node=None, next_node=None):
        """Constructor
        """
        self.key = key
        ''' key '''

        self.previous_node = previous_node
        ''' previous node '''

        self.next_node = next_node
        ''' next node '''

    def copy_from(self, node):
        self.key = node.key
        self.previous_node = node.previous_node
        self.next_node = node.next_node

    def print_on(self):
        print self.key, 


class DoublyLinkedList(object):
    """Doubly Linked List Class
    """

    def __init__(self, sentinel_key=-1):
        """Constructor(make sentinel node)
        """
        self.sentinel_node = Node(key=sentinel_key)
        self.sentinel_node.next_node = self.sentinel_node
        self.sentinel_node.previous_node = self.sentinel_node

    def insert_node(self, key):
        """insert node which has specified key at first position"""
        
        new_node = Node(key=key, previous_node=self.sentinel_node, next_node=self.sentinel_node.next_node) 
        self.sentinel_node.next_node.previous_node = new_node
        self.sentinel_node.next_node = new_node
              
    def delete_first(self):
        """ delete first node """
        if self.sentinel_node.next_node.key != -1:
            self.sentinel_node.next_node = self.sentinel_node.next_node.next_node
            self.sentinel_node.next_node.previous_node = self.sentinel_node

    def delete_last(self):
        """delete last node """
        if self.sentinel_node.next_node.key != -1:
            self.sentinel_node.previous_node = self.sentinel_node.previous_node.previous_node
            self.sentinel_node.previous_node.next_node = self.sentinel_node
 
    def delete(self, key=None):
        """ delete node which has a key 'key' """
        target_node = self.sentinel_node.next_node
        while target_node.key is not -1:
            if target_node.key == key:
                target_node.previous_node.next_node = target_node.next_node
                target_node.next_node.previous_node = target_node.previous_node
                break
            target_node = target_node.next_node
 
    def print_on(self):
        target_node = self.sentinel_node
        while target_node.next_node is not self.sentinel_node:
            target_node = target_node.next_node
            target_node.print_on()
            

def main():
    doubly_linked_list = DoublyLinkedList()

    input_length = int(raw_input())
    counter = 0
    while counter < input_length:
        counter += 1
        input_line = raw_input()
        if input_line[0] == 'i':
            doubly_linked_list.insert_node(input_line[7:])
        elif input_line[6] == 'F':
            doubly_linked_list.delete_first()
        elif input_line[6] == 'L':
            doubly_linked_list.delete_last()
        else:
            doubly_linked_list.delete(input_line[7:])

    doubly_linked_list.print_on()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

class Node(object):
    """Node class
    """

    def __init__(self, key=None, previous_node=None, next_node=None):
        """Constructor
        """
        self.key = key
        ''' key '''

        self.previous_node = previous_node
        ''' previous node '''

        self.next_node = next_node
        ''' next node '''

    def copy_from(self, node):
        self.key = node.key
        self.previous_node = node.previous_node
        self.next_node = node.next_node

    def print_on(self):
        print self.key, 


class DoublyLinkedList(object):
    """Doubly Linked List Class
    """

    def __init__(self, sentinel_key=-1):
        """Constructor(make sentinel node)
        """
        self.sentinel_node = Node(key=sentinel_key)
        self.sentinel_node.next_node = self.sentinel_node
        self.sentinel_node.previous_node = self.sentinel_node

    def insert_node(self, key):
        """insert node which has specified key at first position"""
        new_node = Node(key=key, previous_node=self.sentinel_node, next_node=self.sentinel_node.next_node) 
        self.sentinel_node.next_node.previous_node = new_node
        self.sentinel_node.next_node = new_node


    def delete_first(self):
        """ delete first node """
        if self.sentinel_node.next_node.key != -1:
            self.sentinel_node.next_node = self.sentinel_node.next_node.next_node
            self.sentinel_node.next_node.previous_node = self.sentinel_node

    def delete_last(self):
        """delete last node """
        if self.sentinel_node.next_node.key != -1:
            self.sentinel_node.previous_node = self.sentinel_node.previous_node.previous_node
            self.sentinel_node.previous_node.next_node = self.sentinel_node
 
    def delete(self, key=None):
        """ delete node which has a key 'key' """
        target_node = self.sentinel_node.next_node
        while target_node.key is not self.sentinel_node:
            if target_node.key == key:
                target_node.previous_node.next_node = target_node.next_node
                target_node.next_node.previous_node = target_node.previous_node
                break
            target_node = target_node.next_node
 
    def print_on(self):
        target_node = self.sentinel_node
        while target_node.next_node is not self.sentinel_node:
            target_node = target_node.next_node
            target_node.print_on()
            

def main():
    doubly_linked_list = DoublyLinkedList()

    input_length = int(raw_input())
    counter = 0
    while counter < input_length:
        counter += 1
        input_line = raw_input()
        if input_line[0] == 'i':
            doubly_linked_list.insert_node(input_line[7:])
        elif input_line[6] == 'F':
            doubly_linked_list.delete_first()
        elif input_line[6] == 'L':
            doubly_linked_list.delete_last()
        else:
            doubly_linked_list.delete(input_line[7:])

    doubly_linked_list.print_on()


if __name__ == '__main__':
    main()