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

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

Submission status: Time Limit Exceeded

Solution code:
class Node:
    elm = None
    nxt = None
    prev = None

    def __init__(self, elm=None, prev=None, nxt=None):
        self.elm = elm
        self.prev = prev
        self.nxt = nxt


class MyDLList:
    size = 0
    head = tail = None

    def insert(self, elm):
        if self.is_empty():
            self.head = self.tail = Node(elm)
        else:
            x = Node(elm)
            x.nxt = self.head
            self.head.prev = x
            self.head = x
        self.size += 1

    def list_search(self, x):
        cur = self.head
        while cur != self.tail and cur.elm != x:
            cur = cur.nxt
        if cur.elm != x:
            cur = None
        return cur

    def delete(self, x):
        cur = self.list_search(x)
        if cur:
            if cur == self.head:
                self.delete_first()
            elif cur == self.tail:
                self.delete_last()
            else:
                cur.prev.nxt = cur.nxt
                cur.nxt.prev = cur.prev
            self.size -= 1
            return cur.elm


    def delete_first(self):
        cur = self.head
        if not self.is_empty():
            if self.head != self.tail:
                self.head.nxt.prev = None
                self.head = self.head.nxt
            else:
                self.head = self.tail = None
            self.size -= 1
            return cur.elm

    def delete_last(self):
        cur = self.tail
        if not self.is_empty():
            if self.head != self.tail:
                self.tail.prev.nxt = None
                self.tail = self.tail.prev
            else:
                self.tail = self.head = None
            self.size -= 1
            return cur.elm

    def is_empty(self):
        return self.size == 0

    def __str__(self):
        cur = self.head
        output = ""
        while cur.nxt:
            output += str(cur.elm) + " "
            cur = cur.nxt
        output += str(cur.elm)
        return output


n = int(input())

V = [list(map(str, input().split())) for _ in range(n)]
dl = MyDLList()

for i in V:
    if i[0] == "insert":
        dl.insert(int(i[1]))
    elif i[0] == "delete":
        dl.delete(int(i[1]))
    elif i[0] == "deleteFirst":
        dl.delete_first()
    elif i[0] == "deleteLast":
        dl.delete_last()

print(dl)

Submission status: Time Limit Exceeded

Solution code:
class Node:
    elm = None
    nxt = None
    prev = None

    def __init__(self, elm=None, prev=None, nxt=None):
        self.elm = elm
        self.prev = prev
        self.nxt = nxt


class MyDLList:
    size = 0
    head = tail = None

    def insert(self, elm):
        if self.is_empty():
            self.head = self.tail = Node(elm)
        else:
            x = Node(elm)
            x.nxt = self.head
            self.head.prev = x
            self.head = x
        self.size += 1

    def list_search(self, x):
        cur = self.head
        while cur != self.tail and cur.elm != x:
            cur = cur.nxt
        if cur.elm != x:
            cur = None
        return cur

    def delete(self, x):
        cur = self.list_search(x)
        if cur:
            if cur == self.head:
                self.delete_first()
            elif cur == self.tail:
                self.delete_last()
            else:
                cur.prev.nxt = cur.nxt
                cur.nxt.prev = cur.prev
            self.size -= 1
            return cur.elm

    def delete_first(self):
        cur = self.head
        if not self.is_empty():
            if self.head != self.tail:
                self.head.nxt.prev = None
                self.head = self.head.nxt
            else:
                self.head = self.tail = None
            self.size -= 1
            return cur.elm

    def delete_last(self):
        cur = self.tail
        if not self.is_empty():
            if self.head != self.tail:
                self.tail.prev.nxt = None
                self.tail = self.tail.prev
            else:
                self.tail = self.head = None
            self.size -= 1
            return cur.elm

    def is_empty(self):
        return self.size == 0

    def __str__(self):
        cur = self.head
        output = ""
        while cur.nxt:
            output += str(cur.elm) + " "
            cur = cur.nxt
        output += str(cur.elm)
        return output


n = int(input())

dl = MyDLList()

for i in range(n):
    x = list(map(str, input().split()))
    if x[0] == "insert":
        dl.insert(int(x[1]))
    elif x[0] == "delete":
        dl.delete(int(x[1]))
    elif x[0] == "deleteFirst":
        dl.delete_first()
    elif x[0] == "deleteLast":
        dl.delete_last()

print(dl)

Submission status: Time Limit Exceeded

Solution code:
class Node:
    elm = None
    nxt = None
    prev = None

    def __init__(self, elm=None, prev=None, nxt=None):
        self.elm = elm
        self.prev = prev
        self.nxt = nxt


class MyDLList:
    size = 0
    head = tail = None

    def insert(self, elm):
        if self.is_empty():
            self.head = self.tail = Node(elm)
        else:
            x = Node(elm)
            x.nxt = self.head
            self.head.prev = x
            self.head = x
        self.size += 1

    def list_search(self, x):
        cur = self.head
        if cur != self.tail:
            i = 1
            while i < self.size and cur.elm != x:
                cur = cur.nxt
                i += 1
        if cur.elm != x:
            cur = None
        return cur

    def delete(self, x):
        cur = self.list_search(x)
        if cur:
            if cur == self.head:
                self.delete_first()
            elif cur == self.tail:
                self.delete_last()
            else:
                cur.prev.nxt = cur.nxt
                cur.nxt.prev = cur.prev
                self.size -= 1
            return cur.elm

    def delete_first(self):
        cur = self.head
        if self.size != 1:
            self.head.nxt.prev = None
            self.head = self.head.nxt
        else:
            self.head = self.tail = None
        self.size -= 1
        return cur.elm

    def delete_last(self):
        cur = self.tail

        if self.size != 1:
            self.tail.prev.nxt = None
            self.tail = self.tail.prev
        else:
            self.tail = self.head = None
        self.size -= 1
        return cur.elm

    def is_empty(self):
        return self.size == 0

    def __str__(self):
        cur = self.head
        output = ""
        i = 1
        while i < self.size:
            output += str(cur.elm) + " "
            cur = cur.nxt
            i += 1
        output += str(cur.elm)
        return output


n = int(input())

dl = MyDLList()

for i in range(n):
    x = list(map(str, input().split()))
    if x[0] == "insert":
        dl.insert(int(x[1]))
    elif x[0] == "delete":
        dl.delete(int(x[1]))
    elif x[0] == "deleteFirst":
        dl.delete_first()
    elif x[0] == "deleteLast":
        dl.delete_last()

print(dl)

Submission status: Time Limit Exceeded

Solution code:
class Node:
    elm = None
    nxt = None
    prev = None

    def __init__(self, elm=None, prev=None, nxt=None):
        self.elm = elm
        self.prev = prev
        self.nxt = nxt


class MyDLList:
    size = 0
    head = tail = None
    dic = dict()

    def insert(self, elm):
        if self.is_empty():
            self.dic[elm] = [Node(elm)]
            self.head = self.tail = self.dic[elm][0]
        elif self.dic.get(elm):
            self.dic[elm].append(Node(elm))
            self.dic[elm][-1].nxt = self.head
            self.head.prev = self.dic[elm][-1]
            self.head = self.dic[elm][-1]
        else:
            self.dic[elm] = [Node(elm)]
            self.dic[elm][0].nxt = self.head
            self.head.prev = self.dic[elm][0]
            self.head = self.dic[elm][0]
        self.size += 1

    # def list_search(self, elm):
    #     # cur = self.head
    #     # if cur != self.tail:
    #     #     i = 1
    #     #     while i < self.size and cur.elm != x:
    #     #         cur = cur.nxt
    #     #         i += 1
    #     # if cur.elm != x:
    #     #     cur = None
    #     return self.dic.get(elm)

    def delete(self, elm):
        cur = self.dic.get(elm)
        if cur:
            if cur[-1] == self.head:
                self.delete_first()
            elif cur[-1] == self.tail:
                self.delete_last()
            else:
                deleted = cur.pop(-1)
                deleted.prev.nxt = deleted.nxt
                deleted.nxt.prev = deleted.prev
                self.size -= 1
                return deleted.elm

    def delete_first(self):
        # ????§???§?????°????????¨??????????????????????´???????????????¨???????????????
        cur = self.head
        if self.size != 1:
            self.dic[self.head.elm].remove(self.head)
            self.head.nxt.prev = None
            self.head = self.head.nxt
        else:
            self.dic.clear()
            self.head = self.tail = None

        self.size -= 1
        return cur.elm

    def delete_last(self):
        # ????§???§?????°????????¨??????????????????????´???????????????¨???????????????
        cur = self.tail
        if self.size != 1:
            self.dic[self.tail.elm].remove(self.tail)
            self.tail.prev.nxt = None
            self.tail = self.tail.prev
        else:
            self.dic.clear()
            self.tail = self.head = None
        self.size -= 1
        return cur.elm

    def is_empty(self):
        return self.size == 0

    def __str__(self):
        cur = self.head
        output = ""
        i = 1
        while i < self.size:
            output += str(cur.elm) + " "
            cur = cur.nxt
            i += 1
        output += str(cur.elm)
        return output


n = int(input())

dl = MyDLList()

for i in range(n):
    x = list(map(str, input().split()))
    if x[0] == "insert":
        dl.insert(int(x[1]))
    elif x[0] == "delete":
        dl.delete(int(x[1]))
    elif x[0] == "deleteFirst":
        dl.delete_first()
    elif x[0] == "deleteLast":
        dl.delete_last()

print(dl)

Submission status: Time Limit Exceeded

Solution code:
class Node:
    elm = None
    nxt = None
    prev = None

    def __init__(self, elm=None, prev=None, nxt=None):
        self.elm = elm
        self.prev = prev
        self.nxt = nxt


class MyDLList:
    size = 0
    head = tail = None
    dic = dict()

    def insert(self, elm):
        if self.is_empty():
            self.dic[elm] = [Node(elm)]
            self.head = self.tail = self.dic[elm][0]
        elif self.dic.get(elm):
            self.dic[elm].append(Node(elm))
            self.dic[elm][-1].nxt = self.head
            self.head.prev = self.dic[elm][-1]
            self.head = self.dic[elm][-1]
        else:
            self.dic[elm] = [Node(elm)]
            self.dic[elm][0].nxt = self.head
            self.head.prev = self.dic[elm][0]
            self.head = self.dic[elm][0]
        self.size += 1

    # def list_search(self, elm):
    #     # cur = self.head
    #     # if cur != self.tail:
    #     #     i = 1
    #     #     while i < self.size and cur.elm != x:
    #     #         cur = cur.nxt
    #     #         i += 1
    #     # if cur.elm != x:
    #     #     cur = None
    #     return self.dic.get(elm)

    def delete(self, elm):
        cur = self.dic.get(elm)
        if cur:
            if cur[-1] == self.head:
                self.delete_first()
            elif cur[-1] == self.tail:
                self.delete_last()
            else:
                deleted = cur.pop(-1)
                deleted.prev.nxt = deleted.nxt
                deleted.nxt.prev = deleted.prev
                self.size -= 1
                return deleted.elm

    def delete_first(self):
        # ????§???§?????°????????¨??????????????????????´???????????????¨???????????????
        cur = self.head
        if self.size != 1:
            self.dic[self.head.elm].pop(-1)
            self.head.nxt.prev = None
            self.head = self.head.nxt
        else:
            self.dic.clear()
            self.head = self.tail = None

        self.size -= 1
        return cur.elm

    def delete_last(self):
        # ????§???§?????°????????¨??????????????????????´???????????????¨???????????????
        cur = self.tail
        if self.size != 1:
            self.dic[self.tail.elm].pop(0)
            self.tail.prev.nxt = None
            self.tail = self.tail.prev
        else:
            self.dic.clear()
            self.tail = self.head = None
        self.size -= 1
        return cur.elm

    def is_empty(self):
        return self.size == 0

    def __str__(self):
        cur = self.head
        output = ""
        i = 1
        while i < self.size:
            output += str(cur.elm) + " "
            cur = cur.nxt
            i += 1
        output += str(cur.elm)
        return output


n = int(input())

dl = MyDLList()

for i in range(n):
    x = list(map(str, input().split()))
    if x[0] == "insert":
        dl.insert(int(x[1]))
    elif x[0] == "delete":
        dl.delete(int(x[1]))
    elif x[0] == "deleteFirst":
        dl.delete_first()
    elif x[0] == "deleteLast":
        dl.delete_last()

print(dl)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
q = deque()
for i in range(n):
    x = list(map(str, input().split()))
    if x[0] == "insert":
        q.appendleft(x[1])
    elif x[0] == "delete":
        try:
            q.remove(x[1])
        except ValueError:
            pass
    elif x[0] == "deleteFirst":
        q.popleft()
    elif x[0] == "deleteLast":
        q.pop()

print(" ".join(q))

Submission status: Time Limit Exceeded

Solution code:
class Node:
	elm = None
	next = None
	prev = None

class MyList:
	head = tail = None

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

	def delete(self, x):
		n = self.head
		while n and n.elm!=x:
			n = n.next
		self.__delete_node(n)

	def deleteFirst(self):
		self.__delete_node(self.head)

	def deleteLast(self):
		self.__delete_node(self.tail)

	def __delete_node(self, n):
		if n == None: 
			return
		if n == self.head:
			self.head = n.next
		if n == self.tail:
			self.tail = n.prev
		if n.prev:
			n.prev.next = n.next
		if n.next:
			n.next.prev = n.prev

	def __traverse(self):
		n = self.head
		while n:
			yield n.elm
			n = n.next

	def __str__(self):
		return " ".join([str(s) for s in self.__traverse()])

myList = MyList()
n = int(raw_input())
for _ in xrange(n):
	line = raw_input()
	if line[0]=='i':
		myList.insert(int(line[7:]))
	elif line[6]=='F':
		myList.deleteFirst()
	elif line[6]=='L':
		myList.deleteLast()
	else:
		myList.delete(int(line[7:]))
print myList

Submission status: Time Limit Exceeded

Solution code:
class Node:
	elm = None
	next = None
	prev = None

class MyQueue:
	head = tail = None

	def enq(self, x):
		n = Node()
		n.elm = x
		if self.head == None:
			self.head = self.tail = n
		else:
			self.tail.next = n
			n.prev = self.tail
			self.tail = n

	def deq(self):
		if self.head == None:
			return None
		x = self.head.elm
		self.head = self.head.next
		if self.head: 
			self.head.prev = None
		else:
			self.tail = None
		return x

	def pop(self):
		if self.tail == None:
			return None
		x = self.tail.elm
		self.tail = self.tail.prev
		if self.tail: 
			self.tail.next = None
		else:
			self.head = None
		return x

class MyList:
	head = tail = None
	lookup = {}

	def insert(self, x):
		n = Node()
		n.elm = x
		if self.head == None:
			self.head = self.tail = n
		else:
			n.next = self.head
			self.head.prev = n
			self.head = n
		if not x in self.lookup:
			self.lookup[x] = MyQueue()
		self.lookup[x].enq(n)

	def delete(self, x):
		n = self.lookup[x].pop()
		self.__delete_node(n)

	def deleteFirst(self):
		self.lookup[self.head.elm].pop()
		self.__delete_node(self.head)

	def deleteLast(self):
		self.lookup[self.tail.elm].deq()
		self.__delete_node(self.tail)

	def __delete_node(self, n):
		if n == None: 
			return
		if n == self.head:
			self.head = n.next
		if n == self.tail:
			self.tail = n.prev
		if n.prev:
			n.prev.next = n.next
		if n.next:
			n.next.prev = n.prev

	def __traverse(self):
		n = self.head
		while n:
			yield n.elm
			n = n.next

	def __str__(self):
		return " ".join([str(s) for s in self.__traverse()])

myList = MyList()
n = int(raw_input())
for _ in xrange(n):
	line = raw_input()
	if line[0]=='i':
		myList.insert(int(line[7:]))
	elif line[6]=='F':
		myList.deleteFirst()
	elif line[6]=='L':
		myList.deleteLast()
	else:
		myList.delete(int(line[7:]))
print myList

Submission status: Time Limit Exceeded

Solution code:
class Node:
	elm = None
	next = None
	prev = None

class MyList:
	head = tail = None

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

	def delete(self, x):
		n = self.head
		while n and n.elm != x:
			n = n.next
		self.__delete_node(n)

	def deleteFirst(self):
		self.__delete_node(self.head)

	def deleteLast(self):
		self.__delete_node(self.tail)

	def __delete_node(self, n):
		if n == None: 
			return
		if n == self.head:
			self.head = n.next
		if n == self.tail:
			self.tail = n.prev
		if n.prev:
			n.prev.next = n.next
		if n.next:
			n.next.prev = n.prev

	def __traverse(self):
		n = self.head
		while n:
			yield n.elm
			n = n.next

	def __str__(self):
		return " ".join([s for s in self.__traverse()])

myList = MyList()
n = int(raw_input())
for _ in xrange(n):
	line = raw_input()
	if line[0]=='i':
		myList.insert(line[7:])
	elif line[6]=='F':
		myList.deleteFirst()
	elif line[6]=='L':
		myList.deleteLast()
	else:
		myList.delete(line[7:])
print myList

Submission status: Time Limit Exceeded

Solution code:
class Node:
	elm = None
	next = None
	prev = None

class MyList:
	head = tail = None

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

	def delete(self, x):
		n = self.head
		while n and n.elm != x:
			n = n.next
		if n: 
			self.__delete_node(n)

	def deleteFirst(self):
		self.__delete_node(self.head)

	def deleteLast(self):
		self.__delete_node(self.tail)

	def __delete_node(self, n):
		if n == self.head:
			self.head = n.next
		if n == self.tail:
			self.tail = n.prev
		if n.prev:
			n.prev.next = n.next
		if n.next:
			n.next.prev = n.prev

	def __traverse(self):
		n = self.head
		while n:
			yield n.elm
			n = n.next

	def print_all(self):
		for s in self.__traverse():
			print s,

	def __str__(self):
		return " ".join([s for s in self.__traverse()])

myList = MyList()
n = int(raw_input())
for _ in xrange(n):
	line = raw_input()
	if line[0]=='i':
		myList.insert(line[7:])
	elif line[6]=='F':
		myList.deleteFirst()
	elif line[6]=='L':
		myList.deleteLast()
	else:
		myList.delete(line[7:])
#print myList
myList.print_all()

Submission status: Time Limit Exceeded

Solution code:
class Node:
	elm = None
	next = None
	prev = None

class MyList:
	head = tail = None

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

	def delete(self, x):
		n = self.head
		while n and n.elm != x:
			n = n.next
		if n: 
			self.__delete_node(n)

	def deleteFirst(self):
		self.__delete_node(self.head)

	def deleteLast(self):
		self.__delete_node(self.tail)

	def __delete_node(self, n):
		if n == self.head:
			self.head = n.next
		if n == self.tail:
			self.tail = n.prev
		if n.prev:
			n.prev.next = n.next
		if n.next:
			n.next.prev = n.prev

	def __traverse(self):
		n = self.head
		while n:
			yield n.elm
			n = n.next

	def print_all(self):
		n = self.head
		while n:
			print n.elm,
			n = n.next

	def __str__(self):
		return " ".join([s for s in self.__traverse()])

myList = MyList()
n = int(raw_input())
for _ in xrange(n):
	line = raw_input()
	if line[0]=='i':
		myList.insert(line[7:])
	elif line[6]=='F':
		myList.deleteFirst()
	elif line[6]=='L':
		myList.deleteLast()
	else:
		myList.delete(line[7:])
#print myList
myList.print_all()

Submission status: Time Limit Exceeded

Solution code:
class Node:
	elm = None
	next = None
	prev = None

class MyList:
	head = tail = None
	lookup = {}

	def insert(self, x):
		n = Node()
		n.elm = x
		if self.head == None:
			self.head = self.tail = n
		else:
			n.next = self.head
			self.head.prev = n
			self.head = n
		self.lookup[x] = n

	def delete(self, x):
		if x in self.lookup:
			n = self.lookup[x]
			del self.lookup[x]
		else:
			n = self.head
			while n and n.elm != x:
				n = n.next
		if n: 
			self.__delete_node(n)

	def deleteFirst(self):
		x = self.head.elm
		if x in self.lookup:
			del self.lookup[x] 
		self.__delete_node(self.head)

	def deleteLast(self):
		x = self.tail.elm
		if x in self.lookup and self.tail == self.lookup[x]:
			del self.lookup[x]
		self.__delete_node(self.tail)

	def __delete_node(self, n):
		if n == self.head:
			self.head = n.next
		if n == self.tail:
			self.tail = n.prev
		if n.prev:
			n.prev.next = n.next
		if n.next:
			n.next.prev = n.prev

	def print_all(self):
		n = self.head
		while n:
			print n.elm,
			n = n.next

myList = MyList()
n = int(raw_input())
for _ in xrange(n):
	line = raw_input()
	if line[0]=='i':
		myList.insert(line[7:])
	elif line[6]=='F':
		myList.deleteFirst()
	elif line[6]=='L':
		myList.deleteLast()
	else:
		myList.delete(line[7:])
myList.print_all()

Submission status: Time Limit Exceeded

Solution code:
class MyDLList:
    head = tail = None
    size = 0

    def append_left(self, elm):
        if self.is_empty():
            self.head = self.tail = [elm, None, None]
            # elm, prev, next
        else:
            cur = [elm, None, self.head]
            self.head[1] = cur
            self.head = cur
        self.size += 1

    def is_empty(self):
        return self.size == 0

    def list_search(self, elm):
        cur = self.head
        i = 1
        while i < self.size and cur[0] != elm:
            cur = cur[2]
            i += 1
        if cur[0] != elm:
            cur = None
        return cur

    def delete(self, elm):
        cur = self.list_search(elm)
        if cur:
            if cur == self.head:
                deleted = self.delete_first()
            elif cur == self.tail:
                deleted = self.delete_last()
            else:
                deleted = cur[0]
                cur[1][2] = cur[2]
                cur[2][1] = cur[1]
                self.size -= 1
        else:
            deleted = None
        return deleted

    def delete_first(self):
        cur = self.head
        if self.size == 1:
            self.head = self.tail = None
        else:
            self.head[2][1] = None
            self.head = self.head[2]
        self.size -= 1
        return cur[0]

    def delete_last(self):
        cur = self.tail
        if self.size == 1:
            self.head = self.tail = None
        else: 
            self.tail[1][2] = None
            self.tail = self.tail[1]
        self.size -= 1
        return cur[0]

    def __str__(self):
        cur = self.head
        result = ""
        while cur != self.tail:
            result += cur[0] + " "
            cur = cur[2]
        result += cur[0]
        return result

n = int(input())

dl = MyDLList()


for i in range(n):
    x = list(map(str, input().split()))
    if x[0] == "insert":
        dl.append_left(x[1])
    elif x[0] == "delete":
        dl.delete(x[1])
    elif x[0] == "deleteFirst":
        dl.delete_first()
    elif x[0] == "deleteLast":
        dl.delete_last()

print(dl)

Submission status: Time Limit Exceeded

Solution code:
import sys


class mydeque:
    class cell:
        def __init__(self,x,y = None,z = None):
            self.data = x
            self.next = y
            self.prev = z

    def __init__(self):
        head = mydeque.cell(None)
        head.next = head
        head.prev = head
        self.size = 0
        self.head = head

    def push_front(self,x):
        h = self.head
        q = h.next
        p = mydeque.cell(x,q,h)
        h.next = p
        q.prev = p
        self.size += 1

    def push_back(self,x):
        h = self.head
        p = h.prev
        q = mydeque.cell(x,h,p)
        h.prev = q
        p.next = q
        self.size += 1

    def delete_top(self):
        h = self.head
        top = h.next
        nexttop = top.next
        h.next = nexttop
        nexttop.prev = h
        self.size -= 1

    def delete_last(self):
        h = self.head
        last = h.prev
        prevlast = last.prev
        h.prev = prevlast
        prevlast.next = h
        self.size -= 1

    def delete_find(self,target):
        h = self.head
        now_data = h.next
        while now_data != self.head:
            if now_data.data == target:
                next_now = now_data.next
                prev_now = now_data.prev
                next_now.prev = prev_now
                prev_now.next = next_now
                self.size -= 1
                break
            now_data = now_data.next

    def allprint(self):
        h = self.head.next
        for i in range(self.size):
            if i == self.size - 1:
                print(h.data)
            else:
                print(h.data, end=" ")
                h = h.next

# with open("input.txt","r") as f:
queue = int(input())
length = 0
myd = mydeque()
for q in range(queue):
    command = [n for n in input().strip("\n").split(' ')]
    if command[0] == "insert":
        myd.push_front(command[1])
    elif command[0] == "delete":
        myd.delete_find(command[1])
    elif command[0] == "deleteFirst":
        myd.delete_top()
    else:
        myd.delete_last()
myd.allprint()