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: Runtime Error

Solution code:
n = int(input())
command = [input().split() for i in range(n)]
ans = []
for i in range(n):
    if command[i][0] == "insert":
        ans.insert(0, command[i][1])
    elif command[i][0] == "delete":
        ans.remove(command[i][1])
    elif command[i][0] == "deleteFirst":
        ans.pop(0)
    else:
        ans.pop()

print (' '.join(ans))

Submission status: Runtime Error

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

n = int(sys.stdin.readline())
command = [sys.stdin.readline() for i in range(n)]
ans = []
for i in range(n):
    if command[i][0] == "insert":
        ans.insert(0, command[i][1])
    elif command[i][0] == "delete":
        ans.remove(command[i][1])
    elif command[i][0] == "deleteFirst":
        ans.pop(0)
    else:
        ans.pop()

print (' '.join(ans))

Submission status: Runtime Error

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

n = int(input())
command = []
command = [ input().split() for i in range(n)]
ans = []

for i in range(n):
    if command[i][0] == "insert":
        ans.insert(0, command[i][1])
    elif command[i][0] == "delete":
        ans.remove(command[i][1])
    elif command[i][0] == "deleteFirst":
        ans.pop(0)
    else:
        ans.pop()

print (' '.join(ans))

Submission status: Runtime Error

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

n = int(input())
ans = []

for i in range(n):
    command = input().split()
    if command[0] == "insert":
        ans.insert(0, command[1])
    elif command[0] == "delete":
        ans.remove(command[1])
    elif command[0] == "deleteFirst":
        ans.pop(0)
    else:
        ans.pop()

print (' '.join(ans))

Submission status: Runtime Error

Solution code:
from collections import deque

def insert(x, dll):
    dll.appendleft(x)

def delete(x, dll):
    dll.remove(x)

def deleteFirst(dll):
    dll.popleft()

def deleteLast(dll):
    dll.pop()

n = int(input())
command1 = {"insert": insert, "delete": delete}
command2 = {"deleteFirst": deleteFirst, "deleteLast": deleteLast}
dll = deque()
for i in range(n):
    input_line = [str(s) for s in input().split()]
    if(input_line[0] in command1):
        command1[input_line[0]](int(input_line[1]), dll)
    else:
        command2[input_line[0]](dll)
print(*dll)

Submission status: Runtime Error

Solution code:
from collections import deque

f = open("input.txt")
n = int(f.readline())
dll = deque()

for i in range(n):
    input_line = [str(s) for s in f.readline().split()]
    if input_line[0] == "insert":
        dll.appendleft(int(input_line[1]))
    elif input_line[0] == "delete":
        try:
            dll.remove(int(input_line[1]))
        except ValueError:
            pass
    elif input_line[0] == "deleteFirst":
        dll.popleft()
    else:
        dll.pop()
print(*dll)

Submission status: Runtime Error

Solution code:
from collections import deque
n = int(input())
dll = deque()

for i in range(n):
    input_line = [str(s) for s in input().split()]
    if input_line[0] == "insert":
        dll.appendleft(int(input_line[1]))
    elif input_line[0] == "delete":
        dll.remove(int(input_line[1]))
    elif input_line[0] == "deleteFirst":
        dll.popleft()
    else:
        dll.pop()
print(*dll)

Submission status: Runtime Error

Solution code:
from functools import reduce
from collections import deque


def operate(dq, op):
    if op[0] == 'i':
        dq.appendleft(int(op[7:]))
    else:
        k = op[6]
        if k == 'F':
            dq.popleft()
        elif k == 'L':
            dq.pop()
        else:
            dq.remove(int(op[7:]))
    return dq


n = int(input())
print(*reduce(operate, [input() for _ in range(n)], deque()))

Submission status: Runtime Error

Solution code:
n = int(input())

l_l = list()
for i in range(n):
    cmd_l = input().split()
    cmd = cmd_l[0]

    if cmd == "insert":
        l_l.insert(0, cmd_l[1])
    elif cmd == "delete":
        l_l.remove(cmd_l[1])
    elif cmd == "deleteFirst":
        del l_l[0]
    elif cmd == "deleteLast":
        del l_l[-1]

print(' '.join(l_l))

Submission status: Runtime Error

Solution code:
from collections import deque

dq = deque()
n = int(input())
for _ in range(n):
    cmd = input().split()
    if cmd[0] == "insert":
        dq.appendleft(cmd[1])
    elif cmd[0] == "delete":
        dq.remove(cmd[1])
    elif cmd[0] == "deleteFirst":
        dq.popleft()
    else:
        dq.pop()
print(*dq)

Submission status: Runtime Error

Solution code:
n = int(input())
lists = []

for i in range(n):
    inputs = input().split()
    commandName = inputs[0]

    if len(inputs) == 1:
        if commandName == 'deleteFirst':
            lists.pop(0)
        elif commandName == 'deleteLast':
            lists.pop(-1)
    else:
        num = inputs[1]

        if commandName == 'insert':
            lists = [num] + lists
        elif commandName == 'delete':
            lists.remove(num)

print(' '.join(lists))

Submission status: Runtime Error

Solution code:
class DoublyLinkedList:
    def __init__(self):
        self.first = Node(-1)
        self.first.setNext(Node(-1))

    def insert(self, value):
        newNode = Node(value)
        newNode.setNext(self.first.getNext())
        newNode.setPrev(self.first)
        self.first.getNext().setPrev(newNode)
        self.first.setNext(newNode)

    def delete(self, value):
        self.first.delete(value)

    def deleteFirst(self):
        if self.first.getNext().getValue() != -1:
            self.first.setNext(self.first.getNext().getNext())

    def deleteLast(self):
        self.first.deleteLast()

    def printAll(self):
        if self.first.getNext().getValue() != -1:
            self.first.getNext().printAll()

class Node:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

    def getValue(self):
        return self.value

    def setValue(self, value):
        self.value = value

    def getNext(self):
        return self.next

    def setNext(self, next):
        self.next = next

    def getPrev(self):
        return self.prev

    def setPrev(self, prev):
        self.prev = prev

    def delete(self, value):
        if self.next.getValue() == value:
            self.next = self.next.getNext()
            self.next.setPrev(self)
        else:
            self.next.delete(value)

    def deleteLast(self):
        if self.next.value == -1:
            self.prev.setNext(self.next)
            self.next.setPrev(self.prev)
        else:
            self.next.deleteLast()

    def printAll(self):
        if self.next.getValue() != -1:
            print self.value,
            self.next.printAll()
        else:
            print self.value

if __name__ == "__main__":
    dll = DoublyLinkedList()

    N = input()
    for i in range(N):
        raw = raw_input().split()
        com = raw[0]
        value = int(raw[1])
        if com == "insert":
            dll.insert(value)
        elif com == "delete":
            dll.delete(value)
        elif com == "deleteFirst":
            dll.deleteFirst()
        else:
            dll.deleteLast()
    dll.printAll()

Submission status: Runtime Error

Solution code:
class DoublyLinkedList:
    def __init__(self):
        self.first = Node(-1)
        self.first.setNext(Node(-1))

    def insert(self, value):
        newNode = Node(value)
        newNode.setNext(self.first.getNext())
        newNode.setPrev(self.first)
        self.first.getNext().setPrev(newNode)
        self.first.setNext(newNode)

    def delete(self, value):
        self.first.delete(value)

    def deleteFirst(self):
        if self.first.getNext().getValue() != -1:
            self.first.setNext(self.first.getNext().getNext())

    def deleteLast(self):
        self.first.deleteLast()

    def printAll(self):
        if self.first.getNext().getValue() != -1:
            self.first.getNext().printAll()

class Node:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

    def getValue(self):
        return self.value

    def setValue(self, value):
        self.value = value

    def getNext(self):
        return self.next

    def setNext(self, next):
        self.next = next

    def getPrev(self):
        return self.prev

    def setPrev(self, prev):
        self.prev = prev

    def delete(self, value):
        if self.next.getValue() == value:
            self.next = self.next.getNext()
            self.next.setPrev(self)
        else:
            self.next.delete(value)

    def deleteLast(self):
        if self.next.value == -1:
            self.prev.setNext(self.next)
            self.next.setPrev(self.prev)
        else:
            self.next.deleteLast()

    def printAll(self):
        if self.next.getValue() != -1:
            print self.value,
            self.next.printAll()
        else:
            print self.value

if __name__ == "__main__":
    dll = DoublyLinkedList()

    N = input()
    for i in range(N):
        raw = raw_input().split()
        com = raw[0]
        if len(raw) > 1:
            value = int(raw[1])
        if com == "insert":
            dll.insert(value)
        elif com == "delete":
            dll.delete(value)
        elif com == "deleteFirst":
            dll.deleteFirst()
        else:
            dll.deleteLast()
    dll.printAll()

Submission status: Runtime Error

Solution code:
A = []
n = input()

for i in range(n):
    command = [0, 0]
    temp = raw_input().split()
    command[0] = temp[0]
    command[1] = int(temp[1])

    if command[0] == "insert":
        A.insert(0, command[1])
    elif command[0] == "delete":
        A.remove(command[1])
    elif command[0] == "deleteFirst":
        A.pop(0)
    elif command[0] == "deleteLast":
        A.pop()

print A

Submission status: Runtime Error

Solution code:
A = []
n = input()

for i in range(n):
    command = [0, 0]
    temp = raw_input().split()
    command[0] = temp[0]
    command[1] = int(temp[1])

    if command[0] == "insert":
        A.insert(0, command[1])
    elif command[0] == "delete":
        A.remove(command[1])
    elif command[0] == "deleteFirst":
        A.pop(0)
    elif command[0] == "deleteLast":
        A.pop()

for i in range(len(A)):
    print A[i],

Submission status: Runtime Error

Solution code:
A = []
n = input()

for i in range(n):
    command = [0, 0]
    temp = raw_input().split()
    command[0] = temp[0]
    command[1] = int(temp[1])

    if command[0] == 'insert':
        A.insert(0, command[1])
    elif command[0] == 'delete':
        A.remove(command[1])
    elif command[0] == 'deleteFirst':
        A.pop(0)
    elif command[0] == 'deleteLast':
        A.pop()

for i in range(len(A)):
    print A[i],

Submission status: Runtime Error

Solution code:
A = []
n = input()

for i in range(n):
    command = raw_input().split()

    if command[0] == 'insert':
        A.insert(0, command[1])
    elif command[0] == 'delete':
        A.remove(command[1])
    elif command[0] == 'deleteFirst':
        A.pop(0)
    elif command[0] == 'deleteLast':
        A.pop()

for i in range(len(A)):
    print A[i],

Submission status: Runtime Error

Solution code:
A=[]
fp =0
bp =0
cmd = raw_input()
n=int(raw_input())
while n: 
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif cmd[6] == 'F':
        A.pop()
        fp -=1
    elif cmd[6] == 'L':
        bp +=1
    n -=1
 
for e in A[bp:fp+1][::-1]:
    print int(e),

Submission status: Runtime Error

Solution code:
A=[]
fp =0
bp =0
cmd = raw_input()
n=int(raw_input())
while n: 
    if cmd[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif cmd[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif cmd[6] == 'F':
        A.pop()
        fp -=1
    elif cmd[6] == 'L':
        bp +=1
    n -=1
 
for e in A[bp:fp+1][::-1]:
    print int(e),

Submission status: Runtime Error

Solution code:
A=[]
fp =0
bp =0
cmd = raw_input()
n=int(raw_input())
while n: 
    if cmd[0] == 'i':
        A.append(int(cmd[7:]))
        fp += 1
    elif cmd[6] == ' ':
        try:
            i = A[::-1].index(int(cmd[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif cmd[6] == 'F':
        A.pop()
        fp -=1
    elif cmd[6] == 'L':
        bp +=1
    n -=1
 
for e in A[bp:fp+1][::-1]:
    print int(e),

Submission status: Runtime Error

Solution code:
class DoublyLinkedList:
    def __init__(self, value = -1):
        self.value = value
        self.prev = self
        self.next = self

    def insert(self, value):
        newNode = DoublyLinkedList(value)
        newNode.next = self.next
        newNode.prev = self
        self.next.prev = newNode
        self.next = newNode

    def delete(self, value):
        nextValue = self.next.value
        if nextValue == value:
            self.next = self.next.next
            self.next.prev = self
        elif nextValue != -1:
            self.next.delete(value)

    def deleteFirst(self):
        if self.next.value != -1:
            self.next = self.next.next
            self.next.prev = self

    def deleteLast(self):
        if self.prev.value != -1:
            self.prev = self.prev.prev
            self.prev.next = self

    def printAll(self):
        if self.next.value != -1:
            if self.value != -1:
                print self.value,
            self.next.printAll()
        else:
            print self.value

if __name__ == "__main__":
    dll = DoublyLinkedList()

    N = input()
    for i in range(N):
        raw = raw_input().split()
        com = raw[0]
        if len(raw) > 1:
            value = int(raw[1])
        if com == "insert":
            dll.insert(value)
        elif com == "delete":
            dll.delete(value)
        elif com == "deleteFirst":
            dll.deleteFirst()
        else:
            dll.deleteLast()
    dll.printAll()

Submission status: Runtime Error

Solution code:
def insert(x,a):
    a.insert(0,x)
    return a
def delete(x,a):
    a.remove(x)
    return a
def deletefirst(a):
    del a[0]
    return a
def deletelast(a):
    del a[-1]
    return a
n=input()
a=[]
for i in xrange(n):
    s=raw_input().split()
    if s[0]=="insert":
        insert(s[1],a)
    elif s[0]=="delete":
        delete(s[1],a)
    elif s[0]=="deleteFirst":
        deletefirst(a)
    else:
        deletelast(a)
print(" ".join(a))

Submission status: Runtime Error

Solution code:
n = int(input())
stack = []
for i in range(n):
    command = list(input().split())
#    print(stack, command)
    if command[0] == 'insert':
        stack = [command[1]] + stack
    elif command[0] == 'delete':
        stack.remove(command[1])
    elif command[0] == 'deleteFirst':
        stack.pop(0)
    elif command[0] == 'deleteLast':
        stack.pop()
print(' '.join(stack))

Submission status: Runtime Error

Solution code:
MAX_N = 2000000


class DoublyLinkedList(object):

    def __init__(self):
        self.list = [Node(0, 0, 0, 0)] * MAX_N
        self.gen_node = node_generator()

        nil = 0
        self.nil_node = self.gen_node(0, nil, nil)
        self.list[nil] = self.nil_node

    def insert(self, x):
        inserted = self.gen_node(x, self.nil_node.p, self.nil_node.next)
        self.list[inserted.p] = inserted

        self.list[self.nil_node.next].prev = inserted.p
        self.nil_node.next = inserted.p

    def _delete_node(self, i):
        self.list[self.list[i].prev].next, self.list[self.list[i].next].prev = self.list[i].next, self.list[i].prev

    def _search_node(self, val):
        cur = self.nil_node.next
        while self.list[cur].p != self.nil_node.p:
            if self.list[cur].val == val:
                return cur
            cur = self.list[self.list[cur].next].p

    def delete(self, x):
        i = self._search_node(x)
        self._delete_node(i)

    def delete_first(self):
        self._delete_node(self.nil_node.next)

    def delete_last(self):
        self._delete_node(self.nil_node.prev)

    def show(self):
        ans = ""
        cur = self.nil_node.next

        while cur != self.nil_node.p:
            ans += self.list[cur].val, " ",
            cur = self.list[cur].next

        print ans.strip()


class Node(object):

    def __init__(self, p, val, prev, _next):
        self.p = p
        self.val = val
        self.prev = prev
        self.next = _next

    def __repr__(self):
        return "p: {}, val: {}, prev: {}, next: {}\n".format(self.p, self.val, self.prev, self.next)


def node_generator():
    p = [-1]

    def _node_generator(val, prev, _next):
        p[0] += 1
        return Node(p[0], val, prev, _next)

    return _node_generator

if __name__ == '__main__':
    n = int(raw_input())
    commands = [raw_input().split() for _ in range(n)]

    d = DoublyLinkedList()

    for command in commands:
        if command[0] == "insert":
            d.insert(int(command[1]))
        elif command[0] == "delete":
            d.delete(int(command[1]))
        elif command[0] == "deleteFirst":
            d.delete_first()
        elif command[0] == "deleteLast":
            d.delete_last()

    d.show()

Submission status: Runtime Error

Solution code:
MAX_N = 200


class DoublyLinkedList(object):

    def __init__(self):
        self.list = [Node(0, 0, 0, 0)] * MAX_N
        self.gen_node = node_generator()

        nil = 0
        self.nil_node = self.gen_node(0, nil, nil)
        self.list[nil] = self.nil_node

    def insert(self, x):
        inserted = self.gen_node(x, self.nil_node.p, self.nil_node.next)
        self.list[inserted.p] = inserted

        self.list[self.nil_node.next].prev = inserted.p
        self.nil_node.next = inserted.p

    def _delete_node(self, i):
        self.list[self.list[i].prev].next, self.list[self.list[i].next].prev = self.list[i].next, self.list[i].prev

    def _search_node(self, val):
        cur = self.nil_node.next
        while self.list[cur].p != self.nil_node.p:
            if self.list[cur].val == val:
                return cur
            cur = self.list[self.list[cur].next].p

    def delete(self, x):
        i = self._search_node(x)
        self._delete_node(i)

    def delete_first(self):
        self._delete_node(self.nil_node.next)

    def delete_last(self):
        self._delete_node(self.nil_node.prev)

    def show(self):
        ans = ""
        cur = self.nil_node.next

        while cur != self.nil_node.p:
            ans += self.list[cur].val, " ",
            cur = self.list[cur].next

        print ans.strip()


class Node(object):

    def __init__(self, p, val, prev, _next):
        self.p = p
        self.val = val
        self.prev = prev
        self.next = _next

    def __repr__(self):
        return "p: {}, val: {}, prev: {}, next: {}\n".format(self.p, self.val, self.prev, self.next)


def node_generator():
    p = [-1]

    def _node_generator(val, prev, _next):
        p[0] += 1
        return Node(p[0], val, prev, _next)

    return _node_generator

if __name__ == '__main__':
    n = int(raw_input())
    commands = [raw_input().split() for _ in range(n)]

    d = DoublyLinkedList()

    for command in commands:
        if command[0] == "insert":
            d.insert(int(command[1]))
        elif command[0] == "delete":
            d.delete(int(command[1]))
        elif command[0] == "deleteFirst":
            d.delete_first()
        elif command[0] == "deleteLast":
            d.delete_last()

    d.show()

Submission status: Runtime Error

Solution code:
MAX_N = 2000000


class DoublyLinkedList(object):

    def __init__(self):
        self.list = [Node(0, 0, 0, 0)] * MAX_N
        self.gen_node = node_generator()

        nil = 0
        self.nil_node = self.gen_node(0, nil, nil)
        self.list[nil] = self.nil_node

    def insert(self, x):
        inserted = self.gen_node(x, self.nil_node.p, self.nil_node.next)
        self.list[inserted.p] = inserted

        self.list[self.nil_node.next].prev = inserted.p
        self.nil_node.next = inserted.p

    def _delete_node(self, i):
        self.list[self.list[i].prev].next, self.list[self.list[i].next].prev = self.list[i].next, self.list[i].prev

    def _search_node(self, val):
        cur = self.nil_node.next
        while self.list[cur].p != self.nil_node.p:
            if self.list[cur].val == val:
                return cur
            cur = self.list[self.list[cur].next].p

    def delete(self, x):
        i = self._search_node(x)
        self._delete_node(i)

    def delete_first(self):
        self._delete_node(self.nil_node.next)

    def delete_last(self):
        self._delete_node(self.nil_node.prev)

    def show(self):
        ans = ""
        cur = self.nil_node.next

        while cur != self.nil_node.p:
            ans += "{} ".format(self.list[cur].val)
            cur = self.list[cur].next

        print ans.strip()


class Node(object):

    def __init__(self, p, val, prev, _next):
        self.p = p
        self.val = val
        self.prev = prev
        self.next = _next

    def __repr__(self):
        return "p: {}, val: {}, prev: {}, next: {}\n".format(self.p, self.val, self.prev, self.next)


def node_generator():
    p = [-1]

    def _node_generator(val, prev, _next):
        p[0] += 1
        return Node(p[0], val, prev, _next)

    return _node_generator

if __name__ == '__main__':
    n = int(raw_input())
    commands = [raw_input().split() for _ in range(n)]

    d = DoublyLinkedList()

    for command in commands:
        if command[0] == "insert":
            d.insert(int(command[1]))
        elif command[0] == "delete":
            d.delete(int(command[1]))
        elif command[0] == "deleteFirst":
            d.delete_first()
        elif command[0] == "deleteLast":
            d.delete_last()

    d.show()

Submission status: Runtime Error

Solution code:
MAX_N = 20000


class DoublyLinkedList(object):

    def __init__(self):
        self.list = [Node(0, 0, 0, 0)] * MAX_N
        self.gen_node = node_generator()

        nil = 0
        self.nil_node = self.gen_node(0, nil, nil)
        self.list[nil] = self.nil_node

    def insert(self, x):
        inserted = self.gen_node(x, self.nil_node.p, self.nil_node.next)
        self.list[inserted.p] = inserted

        self.list[self.nil_node.next].prev = inserted.p
        self.nil_node.next = inserted.p

    def _delete_node(self, i):
        self.list[self.list[i].prev].next, self.list[self.list[i].next].prev = self.list[i].next, self.list[i].prev

    def _search_node(self, val):
        cur = self.nil_node.next
        while cur != self.nil_node.p:
            if self.list[cur].val == val:
                return cur
            cur = self.list[self.list[cur].next].p

    def delete(self, x):
        i = self._search_node(x)
        if i is not None:
            self._delete_node(i)

    def delete_first(self):
        self._delete_node(self.nil_node.next)

    def delete_last(self):
        self._delete_node(self.nil_node.prev)

    def show(self):
        ans = ""
        cur = self.nil_node.next

        while cur != self.nil_node.p:
            ans += "{} ".format(self.list[cur].val)
            cur = self.list[cur].next

        print ans.strip()


class Node(object):

    def __init__(self, p, val, prev, _next):
        self.p = p
        self.val = val
        self.prev = prev
        self.next = _next

    def __repr__(self):
        return "p: {}, val: {}, prev: {}, next: {}\n".format(self.p, self.val, self.prev, self.next)


def node_generator():
    p = [-1]

    def _node_generator(val, prev, _next):
        p[0] += 1
        return Node(p[0], val, prev, _next)

    return _node_generator

if __name__ == '__main__':
    n = int(raw_input())
    commands = [raw_input().split() for _ in range(n)]

    d = DoublyLinkedList()

    for command in commands:
        if command[0] == "insert":
            d.insert(int(command[1]))
        elif command[0] == "delete":
            d.delete(int(command[1]))
        elif command[0] == "deleteFirst":
            d.delete_first()
        elif command[0] == "deleteLast":
            d.delete_last()

    d.show()

Submission status: Runtime Error

Solution code:
MAX_N = 100000


class DoublyLinkedList(object):

    def __init__(self):
        self.list = [Node(0, 0, 0, 0)] * MAX_N
        self.gen_node = node_generator()

        nil = 0
        self.nil_node = self.gen_node(0, nil, nil)
        self.list[nil] = self.nil_node

    def insert(self, x):
        inserted = self.gen_node(x, self.nil_node.p, self.nil_node.next)
        self.list[inserted.p] = inserted

        self.list[self.nil_node.next].prev = inserted.p
        self.nil_node.next = inserted.p

    def _delete_node(self, i):
        self.list[self.list[i].prev].next, self.list[self.list[i].next].prev = self.list[i].next, self.list[i].prev

    def _search_node(self, val):
        cur = self.nil_node.next
        while cur != self.nil_node.p:
            if self.list[cur].val == val:
                return cur
            cur = self.list[self.list[cur].next].p

    def delete(self, x):
        i = self._search_node(x)
        if i is not None:
            self._delete_node(i)

    def delete_first(self):
        self._delete_node(self.nil_node.next)

    def delete_last(self):
        self._delete_node(self.nil_node.prev)

    def show(self):
        ans = ""
        cur = self.nil_node.next

        while cur != self.nil_node.p:
            ans += "{} ".format(self.list[cur].val)
            cur = self.list[cur].next

        print ans.strip()


class Node(object):

    def __init__(self, p, val, prev, _next):
        self.p = p
        self.val = val
        self.prev = prev
        self.next = _next

    def __repr__(self):
        return "p: {}, val: {}, prev: {}, next: {}\n".format(self.p, self.val, self.prev, self.next)


def node_generator():
    p = [-1]

    def _node_generator(val, prev, _next):
        p[0] += 1
        return Node(p[0], val, prev, _next)

    return _node_generator

if __name__ == '__main__':
    n = int(raw_input())
    commands = [raw_input().split() for _ in range(n)]

    d = DoublyLinkedList()

    for command in commands:
        if command[0] == "insert":
            d.insert(int(command[1]))
        elif command[0] == "delete":
            d.delete(int(command[1]))
        elif command[0] == "deleteFirst":
            d.delete_first()
        elif command[0] == "deleteLast":
            d.delete_last()

    d.show()

Submission status: Runtime Error

Solution code:
MAX_N = 500000


class DoublyLinkedList(object):

    def __init__(self):
        self.list = [Node(0, 0, 0, 0)] * MAX_N
        self.gen_node = node_generator()

        nil = 0
        self.nil_node = self.gen_node(0, nil, nil)
        self.list[nil] = self.nil_node

    def insert(self, x):
        inserted = self.gen_node(x, self.nil_node.p, self.nil_node.next)
        self.list[inserted.p] = inserted

        self.list[self.nil_node.next].prev = inserted.p
        self.nil_node.next = inserted.p

    def _delete_node(self, i):
        self.list[self.list[i].prev].next, self.list[self.list[i].next].prev = self.list[i].next, self.list[i].prev

    def _search_node(self, val):
        cur = self.nil_node.next
        while cur != self.nil_node.p:
            if self.list[cur].val == val:
                return cur
            cur = self.list[self.list[cur].next].p

    def delete(self, x):
        i = self._search_node(x)
        if i is not None:
            self._delete_node(i)

    def delete_first(self):
        self._delete_node(self.nil_node.next)

    def delete_last(self):
        self._delete_node(self.nil_node.prev)

    def show(self):
        ans = ""
        cur = self.nil_node.next

        while cur != self.nil_node.p:
            ans += "{} ".format(self.list[cur].val)
            cur = self.list[cur].next

        print ans.strip()


class Node(object):

    def __init__(self, p, val, prev, _next):
        self.p = p
        self.val = val
        self.prev = prev
        self.next = _next

    def __repr__(self):
        return "p: {}, val: {}, prev: {}, next: {}\n".format(self.p, self.val, self.prev, self.next)


def node_generator():
    p = [-1]

    def _node_generator(val, prev, _next):
        p[0] += 1
        return Node(p[0], val, prev, _next)

    return _node_generator

if __name__ == '__main__':
    n = int(raw_input())
    commands = [raw_input().split() for _ in range(n)]

    d = DoublyLinkedList()

    for command in commands:
        if command[0] == "insert":
            d.insert(int(command[1]))
        elif command[0] == "delete":
            d.delete(int(command[1]))
        elif command[0] == "deleteFirst":
            d.delete_first()
        elif command[0] == "deleteLast":
            d.delete_last()

    d.show()