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:
A = []
n = int(raw_input())
stack = []
for i in range(n):
	A.append(raw_input())

for i in A:
	if "insert" in i:
		try:
		    stack.insert(0, int(i[7:]))
		except:
			pass
	elif "delete " in i and len(stack) > 0:
		try:
		    stack.remove(int(i[7:]))
		except:
			pass
	elif "deleteFirst" in i and len(stack) > 0:
		stack.pop(0)
	elif "deleteLast" in i and len(stack) > 0:
		stack.pop()
if len(stack) > 0:
    print " ".join(map(str, stack))

Submission status: Time Limit Exceeded

Solution code:

n = int(raw_input())
stack = []
for i in range(n):
	i = raw_input()
	if "insert" in i:
		try:
		    stack.insert(0, int(i[7:]))
		except:
			pass
	elif "delete " in i and len(stack) > 0:
		try:
		    stack.remove(int(i[7:]))
		except:
			pass
	elif "deleteFirst" in i and len(stack) > 0:
		stack.pop(0)
	elif "deleteLast" in i and len(stack) > 0:
		stack.pop()
if len(stack) > 0:
    print " ".join(map(str, stack))

Submission status: Time Limit Exceeded

Solution code:

n = int(raw_input())
stack = []
for i in range(n):
	i = raw_input()
	if "insert" in i:
		try:
		    stack.insert(0, int(i[7:]))
		except:
			pass
	elif "delete " in i:
		try:
		    stack.remove(int(i[7:]))
		except:
			pass
	elif "deleteFirst" in i:
		stack.pop(0)
	elif "deleteLast" in i:
		stack.pop()
if len(stack) > 0:
    print " ".join(map(str, stack))

Submission status: Time Limit Exceeded

Solution code:

n = int(raw_input())
stack = []
for i in range(n):
	i = raw_input()
	if "insert" in i:
		try:
		    stack.insert(0, int(i[7:]))
		except:
			pass
	elif "delete " in i:
		try:
		    stack.remove(int(i[7:]))
		except:
			pass
	elif "deleteFirst" in i:
		stack.pop(0)
	elif "deleteLast" in i:
		stack.pop()
print " ".join(map(str, stack))

Submission status: Time Limit Exceeded

Solution code:

n = int(raw_input())
stack = []
for i in range(n):
	i = raw_input()
	if "insert" in i:
		stack.insert(0, int(i[7:]))
	elif "delete " in i:
		if int(i[7:]) in stack:
		    stack.remove(int(i[7:]))
	elif "deleteFirst" in i:
		stack.pop(0)
	elif "deleteLast" in i:
		stack.pop()
print " ".join(map(str, stack))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding:utf-8 -*-

class Node(object):
    def __init__(self, data, prev_node, next_node):
        self.data = data
        self.prev_node = prev_node
        self.next_node = next_node

class DoubleList(object):
    head = None
    tail = None

    def insert(self, data):
        new_node = Node(data, None, None)
        if self.head is None:
            self.head = self.tail = new_node
        else:
            new_node.next_node = self.head
            new_node.prev_node = None
            self.head.prev_node = new_node
            self.head = new_node

    def delete(self, data_value):
        current_node = self.head
        while current_node is not None:
            if current_node.data == data_value:
                if current_node.prev_node is not None and current_node.next_node is not None:
                    current_node.prev_node.next_node = current_node.next_node
                    current_node.next_node.prev_node = current_node.prev_node
                    break
                elif current_node.prev_node is None:
                    self.head = current_node.next_node
                    current_node.next_node.prev_node = None
                    break
                elif current_node.next_node is None:
                    self.tail = current_node.prev_node
                    current_node.prev_node.next_node = None
                    break
            current_node = current_node.next_node

    def deleteFirst(self):
        if self.head.next_node is not None:
            self.head.next_node.prev_node = None
            self.head = self.head.next_node
        else:
            self.head = self.tail = None

    def deleteLast(self):
        if self.tail.prev_node is not None:
            self.tail.prev_node.next_node = None
            self.tail = self.tail.prev_node
        else:
            self.head = self.tail = None

    def show(self):
        current_node = self.head
        data = ""
        while current_node is not None:
            data += current_node.data+" "
            current_node = current_node.next_node
        print data[:-1]

if __name__ == "__main__":
    DL = DoubleList()
    num = int(raw_input())
    for i in range(num):
        line = raw_input()
        if " " in line:
            operation = line.strip().split()[0]
            value = line.strip().split()[1]
        else:
            operation = line.strip()

        if operation == "insert":
            DL.insert(value)
        elif operation == "delete":
            DL.delete(value)
        elif operation == "deleteFirst":
            DL.deleteFirst()
        else:
            DL.deleteLast()

    DL.show()

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
A = []
B = []

def insert(B, x):
    B.insert(0, x)
    return B
def delete(B, x):
    i = 0
    for num in B:
        if num == x:
            B.pop(i)
            break
        i += 1
    return B
def deleteFirst(B):
    B.pop(0)
    return B
def deleteLast(B):
    B.pop()
    return B
operation = {'insert':insert, 'delete':delete, 'deleteFirst':deleteFirst, 'deleteLast':deleteLast}

for i in range(N):
    a = raw_input().split()
    if len(a) == 2:
        A.append([a[0], int(a[1])])
    else:
        A.append([a[0]])


for item in A:
    if len(item) == 2:
        command, num = item
        B = operation[command](B, int(num))
    else:
        command = item[0]
        B = operation[command](B)

B_str = map(str, B)
print ' '.join(B_str)

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
A = []
B = []
def insert(B, x):
    B.append(x)
    return B
def delete(B, x):
    i = 1
    for num in reversed(B):
        if num == x:
            B.pop(-i)
            break
        i += 1
    return B
def deleteFirst(B):
    B.pop()
    return B
def deleteLast(B):
    B.pop(0)
    return B
operation = {'insert':insert, 'delete':delete, 'deleteFirst':deleteFirst, 'deleteLast':deleteLast}

for i in range(N):
    a = raw_input().split()
    if len(a) == 2:
        A.append([a[0], int(a[1])])
    else:
        A.append([a[0]])


for item in A:
    if len(item) == 2:
        command, num = item
        B = operation[command](B, int(num))
    else:
        command = item[0]
        B = operation[command](B)

B.reverse()
B_str = map(str, B)
print ' '.join(B_str)

Submission status: Time Limit Exceeded

Solution code:
class D_Linked_List:
    class Node:
        def __init__(self, key, next = None, prev = None):
            self.next = next
            self.prev = prev
            self.key = key

    def __init__(self):
        self.nil = D_Linked_List.Node(None)
        self.nil.next = self.nil
        self.nil.prev = self.nil

    def insert(self, key):
        node_x = D_Linked_List.Node(key, self.nil.next, self.nil)
        self.nil.next.prev = node_x
        self.nil.next = node_x

    def _listSearch(self, key):
        cur_node = self.nil.next
        while (cur_node != self.nil) and (cur_node.key != key):
            cur_node = cur_node.next
        return cur_node

    def _deleteNode(self, node):
        if node == self.nil:
            return None
        node.prev.next = node.next
        node.next.prev = node.prev

    def deleteFirst(self):
        self._deleteNode(self.nil.next)

    def deleteLast(self):
        self._deleteNode(self.nil.prev)

    def deleteKey(self, key):
        node = self._listSearch(key)
        self._deleteNode(node)

    def show_keys(self):
        cur_node = self.nil.next
        keys_str = ''
        while cur_node != self.nil:
            keys_str += '{0} '.format(cur_node.key)
            cur_node = cur_node.next
        print(keys_str.rstrip())


d_ll = D_Linked_List()

n = int(input())

for i in range(n):
    command = input()
    if 'insert' in command:
        x = int(command.split()[1])
        d_ll.insert(x)
    elif 'deleteFirst' in command:
        d_ll.deleteFirst()
    elif 'deleteLast' in command:
        d_ll.deleteLast()
    else:
        x = int(command.split()[1])
        d_ll.deleteKey(x)

d_ll.show_keys()

Submission status: Time Limit Exceeded

Solution code:
class D_Linked_List:
    class Node:
        def __init__(self, key, next = None, prev = None):
            self.next = next
            self.prev = prev
            self.key = key

    def __init__(self):
        self.nil = D_Linked_List.Node(None)
        self.nil.next = self.nil
        self.nil.prev = self.nil

    def insert(self, key):
        node_x = D_Linked_List.Node(key, self.nil.next, self.nil)
        self.nil.next.prev = node_x
        self.nil.next = node_x

    def _listSearch(self, key):
        cur_node = self.nil.next
        while (cur_node != self.nil) and (cur_node.key != key):
            cur_node = cur_node.next
        return cur_node

    def _deleteNode(self, node):
        if node == self.nil:
            return None
        node.prev.next = node.next
        node.next.prev = node.prev

    def deleteFirst(self):
        self._deleteNode(self.nil.next)

    def deleteLast(self):
        self._deleteNode(self.nil.prev)

    def deleteKey(self, key):
        node = self._listSearch(key)
        self._deleteNode(node)

    def show_keys(self):
        cur_node = self.nil.next
        keys_str = ''
        while cur_node != self.nil:
            keys_str += '{0} '.format(cur_node.key)
            cur_node = cur_node.next
        print(keys_str.rstrip())


import sys

d_ll = D_Linked_List()

for i in sys.stdin:
    if 'insert' in i:
        x = int(i.split()[1])
        d_ll.insert(x)
    elif 'deleteFirst' in i:
        d_ll.deleteFirst()
    elif 'deleteLast' in i:
        d_ll.deleteLast()
    elif 'delete' in i:
        x = int(i.split()[1])
        d_ll.deleteKey(x)
    else:
        pass

d_ll.show_keys()

Submission status: Time Limit Exceeded

Solution code:
class D_Linked_List:
    class Node:
        def __init__(self, key, next = None, prev = None):
            self.next = next
            self.prev = prev
            self.key = key

    def __init__(self):
        self.nil = D_Linked_List.Node(None)
        self.nil.next = self.nil
        self.nil.prev = self.nil

    def insert(self, key):
        node_x = D_Linked_List.Node(key, self.nil.next, self.nil)
        self.nil.next.prev = node_x
        self.nil.next = node_x

    def _listSearch(self, key):
        cur_node = self.nil.next
        while (cur_node != self.nil) and (cur_node.key != key):
            cur_node = cur_node.next
        return cur_node

    def _deleteNode(self, node):
        if node == self.nil:
            return None
        node.prev.next = node.next
        node.next.prev = node.prev

    def deleteFirst(self):
        self._deleteNode(self.nil.next)

    def deleteLast(self):
        self._deleteNode(self.nil.prev)

    def deleteKey(self, key):
        node = self._listSearch(key)
        self._deleteNode(node)

    def show_keys(self):
        cur_node = self.nil.next
        keys = []
        while cur_node != self.nil:
            keys.append(cur_node.key)
            cur_node = cur_node.next
        print(' '.join(map(str, keys)))


import sys

d_ll = D_Linked_List()

commands = list(sys.stdin)

for i in commands:
    if 'insert' in i:
        x = int(i.split()[1])
        d_ll.insert(x)
    elif 'deleteFirst' in i:
        d_ll.deleteFirst()
    elif 'deleteLast' in i:
        d_ll.deleteLast()
    elif 'delete' in i:
        x = int(i.split()[1])
        d_ll.deleteKey(x)
    else:
        pass

d_ll.show_keys()

Submission status: Time Limit Exceeded

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

n = input()
list = []
for i in xrange(n):
    command = raw_input().split()
    if command[0] == "insert":
        list.insert(0, command[1])
    elif command[0] == "delete":
        if command[1] in list:
            list.remove(command[1])
    elif command[0] == "deleteFirst":
        list.pop(0)
    elif command[0] == "deleteLast":
        list.pop()
        
print " ".join(list)

Submission status: Time Limit Exceeded

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

n = input()
class DoubleLinkedList(object):
    def __init__(self):
        self.next = None
        self.prev = None
        self.value = None
        
    def insert(self, value):
        new = DoubleLinkedList()
        new.next = self.next
        new.prev = self
        self.next.prev = new
        self.next = new
        new.value = value
        
    def delete(self):
        next = self.next
        prev = self.prev
        self.next.prev = prev
        self.prev.next = next

head = DoubleLinkedList()
tail = DoubleLinkedList()
head.next = tail
tail.prev = head

for i in xrange(n):
    command = raw_input().split()
    if command[0] == "insert":
        head.insert(int(command[1]))
    elif command[0] == "delete":
        key = int(command[1])
        e = head.next
        while True:
            if e is tail:
                break
            if e.value == key:
                e.delete()
                break
            e = e.next
    elif command[0] == "deleteFirst":
        if not head.next is tail:
            head.next.delete()
    elif command[0] == "deleteLast":  
        if not tail.prev is head:
            tail.prev.delete()
    
e = head.next
while True:
    if e is tail:
        break
    print e.value,
    e = e.next

Submission status: Time Limit Exceeded

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

n = input()
class DoubleLinkedList(object):
    def __init__(self):
        pass
        
    def insert(self, value):
        new = DoubleLinkedList()
        new.next = self.next
        new.prev = self
        self.next.prev = new
        self.next = new
        new.value = value
        
    def delete(self):
        next = self.next
        prev = self.prev
        self.next.prev = prev
        self.prev.next = next

head = DoubleLinkedList()
tail = DoubleLinkedList()
head.next = tail
tail.prev = head

for i in xrange(n):
    command = raw_input().split()
    if command[0] == "insert":
        head.insert(int(command[1]))
    elif command[0] == "delete":
        key = int(command[1])
        e = head.next
        while True:
            if e is tail:
                break
            if e.value == key:
                e.delete()
                break
            e = e.next
    elif command[0] == "deleteFirst":
        if not head.next is tail:
            head.next.delete()
    elif command[0] == "deleteLast":  
        if not tail.prev is head:
            tail.prev.delete()
    
e = head.next
while True:
    if e is tail:
        break
    print e.value,
    e = e.next

Submission status: Time Limit Exceeded

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

n = input()
class DoubleLinkedList(object):
    def __init__(self):
        pass
        
    def insert(self, value):
        new = DoubleLinkedList()
        new.next = self.next
        new.prev = self
        self.next.prev = new
        self.next = new
        new.value = value
        
    def delete(self):
        next = self.next
        prev = self.prev
        self.next.prev = prev
        self.prev.next = next
        self = None

head = DoubleLinkedList()
tail = DoubleLinkedList()
head.next = tail
tail.prev = head

for i in xrange(n):
    command = raw_input().split()
    if command[0] == "insert":
        head.insert(int(command[1]))
    elif command[0] == "delete":
        key = int(command[1])
        e = head.next
        while True:
            if e is tail:
                break
            if e.value == key:
                e.delete()
                break
            e = e.next
    elif command[0] == "deleteFirst":
        if not head.next is tail:
            head.next.delete()
    elif command[0] == "deleteLast":  
        if not tail.prev is head:
            tail.prev.delete()
    
e = head.next
while True:
    if e is tail:
        break
    print e.value,
    e = e.next

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self,v):
        self.next = None
        self.prev = None
        self.data = v

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def __str__(self):
        ret = ''
        n = self.head
        while True:
            if n == None:
                break
            else:
                ret += str(n.data) + ' '
                n = n.next
        return ret[:-1]


    def insert(self,v):
        n = Node(v)
        if self.head == None:
            self.head = n
            self.tail = n
        else:
            n.next = self.head
            n.next.prev = n
            self.head = n

    def delete(self,v):
        n = self.head
        while True:
            if n == None:
                break
            else:
                if n.data == v:
                    if n.next == None:
                        self.tail = n.prev
                    else:
                        n.next.prev = n.prev
                    if n.prev == None:
                        self.head = n.next
                    else:
                        n.prev.next = n.next
                    break
                n = n.next

    def deleteFirst(self):
        if self.head != None:
            self.head = self.head.next
            if self.head != None:
                self.head.prev = None
            else:
                self.tail = None
        else:
            raise


    def deleteLast(self):
        if self.tail != None:
            self.tail = self.tail.prev
            if self.tail != None:
                self.tail.next = None
            else:
                self.head = None
        else:
            raise

n = int(raw_input())
commends = []
for i in range(n):
    commends.append(raw_input())

l = DoublyLinkedList()
for c in commends:
    if c == "deleteFirst":
        l.deleteFirst()
    elif c == "deleteLast":
        l.deleteLast()
    else:
        op,val = c.split(' ')
        val = int(val)
        if op == "insert":
            l.insert(val)
        elif op == "delete":
            l.delete(val)

print l

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self,v):
        self.next = None
        self.prev = None
        self.data = v

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def __str__(self):
        ret = ''
        n = self.head
        while True:
            if n == None:
                break
            else:
                ret += str(n.data) + ' '
                n = n.next
        return ret[:-1]


    def insert(self,v):
        n = Node(v)
        if self.head == None:
            self.head = n
            self.tail = n
        else:
            n.next = self.head
            n.next.prev = n
            self.head = n

    def delete(self,v):
        n = self.head
        while True:
            if n == None:
                break
            else:
                if n.data == v:
                    if n.next == None:
                        self.tail = n.prev
                    else:
                        n.next.prev = n.prev
                    if n.prev == None:
                        self.head = n.next
                    else:
                        n.prev.next = n.next
                    break
                n = n.next

    def deleteFirst(self):
        if self.head != None:
            self.head = self.head.next
            if self.head != None:
                self.head.prev = None
            else:
                self.tail = None
        else:
            raise


    def deleteLast(self):
        if self.tail != None:
            self.tail = self.tail.prev
            if self.tail != None:
                self.tail.next = None
            else:
                self.head = None
        else:
            raise

n = int(raw_input())
commends = []

l = DoublyLinkedList()
for i in range(n):
    c = raw_input()
    if c == "deleteFirst":
        l.deleteFirst()
    elif c == "deleteLast":
        l.deleteLast()
    else:
        op,val = c.split(' ')
        val = int(val)
        if op == "insert":
            l.insert(val)
        elif op == "delete":
            l.delete(val)

print l

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self,v):
        self.next = None
        self.prev = None
        self.data = v

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def __str__(self):
        ret = ''
        n = self.head
        while True:
            if n == None:
                break
            else:
                ret += str(n.data) + ' '
                n = n.next
        return ret[:-1]


    def insert(self,v):
        n = Node(v)
        if self.head == None:
            self.head = n
            self.tail = n
        else:
            n.next = self.head
            n.next.prev = n
            self.head = n

    def delete(self,v):
        n = self.head
        while True:
            if n == None:
                break
            else:
                if n.data == v:
                    if n.next == None:
                        self.tail = n.prev
                    else:
                        n.next.prev = n.prev
                    if n.prev == None:
                        self.head = n.next
                    else:
                        n.prev.next = n.next
                    break
                n = n.next

    def deleteFirst(self):
        if self.head != None:
            self.head = self.head.next
            if self.head != None:
                self.head.prev = None
            else:
                self.tail = None
        else:
            raise


    def deleteLast(self):
        if self.tail != None:
            self.tail = self.tail.prev
            if self.tail != None:
                self.tail.next = None
            else:
                self.head = None
        else:
            raise

n = int(raw_input())

l = DoublyLinkedList()
for i in range(n):
    c = raw_input()
    if c == "deleteFirst":
        l.deleteFirst()
    elif c == "deleteLast":
        l.deleteLast()
    else:
        op,val = c.split(' ')
        val = int(val)
        if op == "insert":
            l.insert(val)
        elif op == "delete":
            l.delete(val)

print l

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self,v):
        self.next = None
        self.prev = None
        self.data = v

class DoublyLinkedList:
    def __init__(self):
        self.nil = Node(None)
        self.nil.next = self.nil
        self.nil.prev = self.nil

    def __str__(self):
        ret = ''
        n = self.nil.next
        while True:
            if n.data == None:
                break
            else:
                ret += str(n.data) + ' '
                n = n.next
        return ret[:-1]


    def insert(self,v):
        n = Node(v)
        if self.nil.next.data == None:
            self.nil.next = n
            self.nil.prev = n
            n.next = self.nil
            n.prev = self.nil
        else:
            n.next = self.nil.next
            n.prev = self.nil
            n.next.prev = n
            self.nil.next = n

    def delete(self,v):
        n = self.nil.next
        while True:
            if n.data == None:
                break
            else:
                if n.data == v:
                    if n.next.data == None:
                        self.nil.prev = n.prev
                    else:
                        n.next.prev = n.prev
                    if n.prev == None:
                        self.nil.next = n.next
                    else:
                        n.prev.next = n.next
                    break
                n = n.next

    def deleteFirst(self):
        if self.nil.next.data != None:
            self.nil.next = self.nil.next.next
            if self.nil.next.data != None:
                self.nil.next.prev = self.nil
            else:
                self.nil.prev = self.nil
        else:
            raise


    def deleteLast(self):
        if self.nil.prev.data != None:
            self.nil.prev = self.nil.prev.prev
            if self.nil.prev.data != None:
                self.nil.prev.next = self.nil
            else:
                self.nil.next = self.nil
        else:
            raise

n = int(raw_input())

l = DoublyLinkedList()
for i in range(n):
    c = raw_input()
    if c == "deleteFirst":
        l.deleteFirst()
    elif c == "deleteLast":
        l.deleteLast()
    else:
        op,val = c.split(' ')
        val = int(val)
        if op == "insert":
            l.insert(val)
        elif op == "delete":
            l.delete(val)

print l

Submission status: Time Limit Exceeded

Solution code:
class DoublyLinkedList:
    def __init__(self):
        self.nil = self.make_node(None)
        self.nil['next'] = self.nil
        self.nil['prev'] = self.nil

    def make_node(self,v):
        return {'key':v, 'next':None, 'prev':None}

    def __str__(self):
        ret = ''
        n = self.nil['next']
        while True:
            if n['key'] == None:
                break
            else:
                ret += str(n['key']) + ' '
                n = n['next']
        return ret[:-1]


    def insert(self,v):
        n = self.make_node(v)
        n['next'] = self.nil['next']
        self.nil['next']['prev'] = n
        n['prev'] = self.nil
        self.nil['next'] = n

    def delete(self,v):
        self.delete_node(self.list_search(v))

    def delete_node(self,n):
        if n['key'] == None: return
        n['next']['prev'] = n['prev']
        n['prev']['next'] = n['next']

    def list_search(self,v):
        cur = self.nil['next']
        while (cur['key'] != None) and (cur['key'] != v):
            cur = cur['next']
        return cur

    def deleteFirst(self):
        self.delete_node(self.nil['next'])

    def deleteLast(self):
        self.delete_node(self.nil['prev'])

n = int(raw_input())

l = DoublyLinkedList()
for i in range(n):
    c = raw_input()
    if c == "deleteFirst":
        l.deleteFirst()
    elif c == "deleteLast":
        l.deleteLast()
    else:
        op,val = c.split(' ')
        val = int(val)
        if op == "insert":
            l.insert(val)
        elif op == "delete":
            l.delete(val)

print l

Submission status: Time Limit Exceeded

Solution code:
class DoublyLinkedList:
    def __init__(self):
        self.nil = self.make_node(None)
        self.nil['next'] = self.nil
        self.nil['prev'] = self.nil

    def make_node(self,v):
        return {'key':v, 'next':None, 'prev':None}

    def dump(self):
        n = self.nil['next']
        while True:
            if n['key'] == None:
                break
            else:
                print str(n['key']),
                n = n['next']
        print


    def insert(self,v):
        n = self.make_node(v)
        n['next'] = self.nil['next']
        self.nil['next']['prev'] = n
        n['prev'] = self.nil
        self.nil['next'] = n

    def delete(self,v):
        self.delete_node(self.list_search(v))

    def delete_node(self,n):
        if n['key'] == None: return
        n['next']['prev'] = n['prev']
        n['prev']['next'] = n['next']

    def list_search(self,v):
        cur = self.nil['next']
        while (cur['key'] != None) and (cur['key'] != v):
            cur = cur['next']
        return cur

    def deleteFirst(self):
        self.delete_node(self.nil['next'])

    def deleteLast(self):
        self.delete_node(self.nil['prev'])

n = int(raw_input())

l = DoublyLinkedList()
for i in range(n):
    c = raw_input()
    if c == "deleteFirst":
        l.deleteFirst()
    elif c == "deleteLast":
        l.deleteLast()
    else:
        op,val = c.split(' ')
        val = int(val)
        if op == "insert":
            l.insert(val)
        elif op == "delete":
            l.delete(val)

l.dump()

Submission status: Time Limit Exceeded

Solution code:
class DoublyLinkedList:
    def __init__(self):
        self.nil = self.make_node(None)
        self.nil['next'] = self.nil
        self.nil['prev'] = self.nil

    def make_node(self,v):
        return {'key':v, 'next':None, 'prev':None}

    def dump(self):
        n = self.nil['next']
        while True:
            if n['key'] == None:
                break
            else:
                print str(n['key']),
                n = n['next']
        print


    def insert(self,v):
        n = self.make_node(v)
        n['next'] = self.nil['next']
        self.nil['next']['prev'] = n
        n['prev'] = self.nil
        self.nil['next'] = n

    def delete(self,v):
        self.delete_node(self.list_search(v))

    def delete_node(self,n):
        if n['key'] == None: return
        n['next']['prev'] = n['prev']
        n['prev']['next'] = n['next']

    def list_search(self,v):
        cur = self.nil['next']
        while (cur['key'] != None) and (cur['key'] != v):
            cur = cur['next']
        return cur

    def deleteFirst(self):
        self.delete_node(self.nil['next'])

    def deleteLast(self):
        self.delete_node(self.nil['prev'])

n = int(raw_input())
commands = []
for i in range(n):
    commands.append(raw_input())

l = DoublyLinkedList()
for c in commands:
    if c == "deleteFirst":
        l.deleteFirst()
    elif c == "deleteLast":
        l.deleteLast()
    else:
        op,val = c.split(' ')
        val = int(val)
        if op == "insert":
            l.insert(val)
        elif op == "delete":
            l.delete(val)

l.dump()