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: WA: Presentation Error

Solution code:

import sys
#import numpy as np
import copy

N = int(input())
list = []

for i in range(N):
    # insert, delete, deleteFirst, deleteLast
    line = input().rstrip().split(' ')
    if line[0]=='insert':
        list.append((int)(line[1]))
    elif line[0]=='delete':
        for j in range(len(list)):
            if list[j]==(int)(line[1]):
                list.pop(j)
                break
    elif line[0]=='deleteFirst':
        list.pop(0)
    elif line[0]=='deleteLast':
        list.pop(len(list)-1)

for i in range(len(list)):
    print( (str)(list[i]) + " ", end="")
print()

Submission status: WA: Presentation Error

Solution code:
import sys

class ListElement:
    def __init__(self,num):
        self.num = num
        self.next = self.prev = None

class doubleLinkedList:
    def __init__(self):
        self.list = None
    def insert(self,num):
        temp = ListElement(num)
        temp.next = self.list
        self.list = temp
    def delFirst(self):
        if self.list is None:
            return
        temp = self.list
        self.list = temp.next
        del(temp)
    def recDel(self,List):
        if List.next.next is None:
            temp = List.next
            List.next = None
            temp.prev = None
            del(temp)
            return
        self.recDel(List.next)
    def delLast(self):
        if self.list is None:
            return
        elif self.list.next is None:
            self.delFirst()
            return
        self.recDel(self.list)
    def recList(self,List,num):
        if List is None:
            return
        elif List.next is not None and List.next.num == num:
            temp = List.next
            List.next = temp.next
            temp.prev = temp.next = None
            del(temp)
            return
        self.recList(List.next,num)
    def delete(self,num):
        if self.list is None:
            return
        elif self.list.num == num:
            self.delFirst()
            return
        self.recList(self.list,num)
    def recPrint(self,List):
        if List is None:
            print()
            return
        print(List.num,end=' ')
        self.recPrint(List.next)
    def printList(self):
        self.recPrint(self.list)

l = []
for i in sys.stdin:
    l.append(i.split())

res = doubleLinkedList()
for i in range(1,len(l)):
    if l[i][0] == 'insert':
        res.insert(l[i][1])
    elif l[i][0] == 'delete':
        res.delete(l[i][1])
    elif l[i][0] == 'deleteFirst':
        res.delFirst()
    elif l[i][0] == 'deleteLast':
        res.delLast()
res.printList()

Submission status: WA: Presentation Error

Solution code:
import collections,sys
def s():
 d=collections.deque()
 input()
 for e in sys.stdin:
  if'i'==e[0]:d.appendleft(e[7:])
  else:
   if' '==e[6]:
    m=e[7:]
    if m in d:d.remove(m)
   elif len(e)%2:d.pop()
   else:d.popleft()
 print(*d)
s()

Submission status: WA: Presentation Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 29 18:31:35 2018
ALDS1-3c simple implementation owing to the feature of python.
@author: maezawa
"""
import sys

def print_array(g):
    ans = str(g[0])
    if len(g) > 1:
        for i in range(1,len(g)):
            ans += ' '+str(g[i]) 
    sys.stdout.write(ans)

a = []
n = int(input())
s_in = sys.stdin.readlines()
for i in range(n):
    s = s_in[i].split()
    #s = input().split()
    #if len(s) == 2:
    #    key = int(s[1])
    com = s[0]
         
    if com == 'insert':
        key = int(s[1])
        a.insert(0, key)
    elif com == 'deleteFirst':
        a.pop(0)
    elif com == 'deleteLast':
        a.pop(-1)
    elif com == 'delete':
        key = int(s[1])
        try:
            a.remove(key)
        except ValueError:
            pass

print_array(a)

Submission status: WA: Presentation Error

Solution code:

n=int(input())
List=[]
command=[]
for i in range(n):
	command=input().split()
	
	#print(command)
	#print(command[0])
	if command[0] == 'insert':
		tmp=int(command[1])
		List.append(tmp)
	elif command[0] == 'delete':
		List.remove(int(command[1]))
	elif command[0] == 'deleteFirst':
		List.pop(0)	
	elif command[0] == 'deleteLast':
		List.pop()

i=len(List)-1
for j in range(len(List)):
	if j is not i-1:
		print(List[i-j],end=" ")
	else:
		print(List[i-j],end="")

Submission status: WA: Presentation Error

Solution code:

n=int(input())
List=[]
command=[]
for i in range(n):
	command=input().split()
	
	#print(command)
	#print(command[0])
	if command[0] == 'insert':
		tmp=int(command[1])
		List.append(tmp)
	elif command[0] == 'delete':
		List.remove(int(command[1]))
	elif command[0] == 'deleteFirst':
		List.pop(0)	
	elif command[0] == 'deleteLast':
		List.pop()

i=len(List)-1
for j in range(len(List)):
	if j is not i-1:
		print(List[i-j],end=" ")
	else:
		print(List[i-j])

Submission status: WA: Presentation Error

Solution code:

n=int(input())
list=[]
ok=0

for i in range(n):
	l=input().split()
	
	if l[0]=="insert":
		list.insert(0,int(l[1]))
		
	elif l[0]=="delete":
		for j in range(len(list)):
			if list[j]==int(l[1]):
				ok=1
		if ok==1:
			list.remove(int(l[1]))
			
	elif l[0]=="deleteFirst":
		del list[0]
		
	elif l[0]=="deleteLast":
		del list[len(list)-1]
	ok=0


for k in range(len(list)):
	print(list[k],end=' ')

Submission status: WA: Presentation Error

Solution code:


n=int(input())
list=[]
ok=0

for i in range(n):
	l=input().split()
	
	if l[0]=="insert":
		list.insert(0,int(l[1]))
		
	elif l[0]=="delete":
		for j in range(len(list)):
			if list[j]==int(l[1]):
				ok=1
		if ok==1:
			list.remove(int(l[1]))
			
	elif l[0]=="deleteFirst":
		del list[0]
		
	elif l[0]=="deleteLast":
		del list[len(list)-1]
	ok=0


for k in range(len(list)):
	if k<len(list)-1:
		print(list[k],end=' ')
	else:
		print(list[k],end='')

Submission status: WA: Presentation Error

Solution code:
n = int(input())
list = []
check = 0

for i in range(n):
	l = input().split()
	if l[0] == "insert":
		list.insert(0,int(l[1]))
	elif l[0] == "delete":
		for j in range(len(list)):
			if list[j] == int(l[1]):
				check = 1
		if check == 1:
			list.remove(int(l[1]))
	elif l[0] == "deleteFirst":
		del list[0]
	elif l[0] == "deleteLast":
		del list[len(list)-1]
	check = 0

for k in range(len(list)):
	if k<len(list)-1:
		print(list[k],end=' ')
	else:
		print(list[k],end='')

Submission status: WA: Presentation Error

Solution code:
n = int(input())
list = []
check = 0

for i in range(n):
	l = input().split()
	if l[0] == "insert":
		list.insert(0,int(l[1]))
	elif l[0] == "delete":
		for j in range(len(list)):
			if list[j] == int(l[1]):
				check = 1
		if check == 1:
			list.remove(int(l[1]))
	elif l[0] == "deleteFirst":
		del list[0]
	elif l[0] == "deleteLast":
		del list[len(list)-1]
	check = 0

for k in range(len(list)):
	if k<len(list)-1:
		print(list[k],end=' ')
	else:
		print(list[k],end='')
print("\n")

Submission status: WA: Presentation Error

Solution code:
n = int(input())
list = []
check = 0

for i in range(n):
	l = input().split()
	if l[0] == "insert":
		list.insert(0,int(l[1]))
	elif l[0] == "delete":
		for j in range(len(list)):
			if list[j] == int(l[1]):
				check = 1
		if check == 1:
			list.remove(int(l[1]))
	elif l[0] == "deleteFirst":
		del list[0]
	elif l[0] == "deleteLast":
		del list[len(list)-1]
	check = 0

for k in range(len(list)):
	if k<len(list)-1:
		print(list[k],end=' ')
	else:
		print(list[k],end='')
print('\n')

Submission status: WA: Presentation Error

Solution code:
n = int(input())
list = []
check = 0

for i in range(n):
	l = input().split()
	if l[0] == "insert":
		list.insert(0,int(l[1]))
	elif l[0] == "delete":
		for j in range(len(list)):
			if list[j] == int(l[1]):
				check = 1
		if check == 1:
			list.remove(int(l[1]))
	elif l[0] == "deleteFirst":
		del list[0]
	elif l[0] == "deleteLast":
		del list[len(list)-1]
	check = 0

for k in range(len(list)):
	if k<len(list)-1:
		print(list[k],end='')
	else:
		print(list[k],end='')

Submission status: WA: Presentation Error

Solution code:

n=int(input())
List=[]
command=[]
for i in range(n):
	command=input().split()
	
	#print(command)
	#print(command[0])
	if command[0] == 'insert':
		tmp=int(command[1])
		List.append(tmp)
	elif command[0] == 'delete':
		List.remove(int(command[1]))
	elif command[0] == 'deleteFirst':
		List.pop(0)	
	elif command[0] == 'deleteLast':
		List.pop()

i=len(List)-1
for j in range(len(List)):
	if j is not i-1:
		print(List[i-j],end=" ")
	else:
		print(*List[i-j])

Submission status: WA: Presentation Error

Solution code:
from collections import deque
def insert():
    a.appendleft(command[1])

def delete():
    try:
        a.remove(command[1])
    except ValueError:
        pass

def deleteFirst():
    a.popleft()

def deleteLast():
    a.pop()

n = int(input())
a = deque([])
for i in range(n):
    command = input().split()
    if command[0] == "insert":
        insert()
    elif command[0] == "delete":
        delete()
    elif command[0] == "deleteFirst":
        deleteFirst()
    else:
        deleteLast()

for e in a:
    print(e, end=" ")
print()

Submission status: WA: Presentation Error

Solution code:
import sys

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

class DoublyLinkedList:
	def __init__(self):
		self.head = None
		self.tail = None
		self.size = 0
	
	def get_size(self):
		return self.size
	
	def is_empty(self):
		return self.size == 0
	
	def appendToHead(self, value):
		node = Node(value)
		if self.head == None and self.tail == None:
			self.head = self.tail = node
		else:
			node.next = self.head
			self.head.prev = node
			self.head = node
		self.size += 1
	
	def removeFirst(self):
		if self.is_empty(): return
		if self.size == 1:
			self.head = self.tail = None
		else:
			next = self.head.next
			next.prev = None
			self.head = next
			if next.next == None:
				self.tail = next
		self.size -= 1		
		
	def removeLast(self):
		if self.is_empty(): return 
		if self.size == 1:
			self.head = self.tail = None
		else:
			prev = self.tail.prev
			prev.next = None
			self.tail = prev
			if prev.prev == None:
				self.head = prev
		self.size -= 1

	def remove(self, value):
		if self.is_empty(): return
		if self.head.value == value:
			self.removeFirst()
		else:
			node = self.head.next
			while node != None:
				if node.value == value:
					prev = node.prev
					next = node.next
					prev.next = next
					if next != None:
						next.prev = prev
					else:
						self.tail = prev
					self.size -= 1
					break
				else:
					node = node.next
		
	def print(self):
			node = self.head
			while node != None:
				sys.stdout.write(str(node.value))
				node = node.next
				if node != None:
					sys.stdout.write(' ')
	
n = int(input())
dll = DoublyLinkedList()
for i in range(n):
	cmd = str(input())
	if cmd == 'deleteFirst':
		dll.removeFirst()
	elif cmd == 'deleteLast':
		dll.removeLast()
	else:
		cmd, value = cmd.split()
		if cmd == 'insert':
			dll.appendToHead(int(value))
		elif cmd == 'delete':
			dll.remove(int(value))
		else:
			print('Unknown command:' + cmd)
	
dll.print()

Submission status: WA: Presentation Error

Solution code:
n = int(input())
xlist = []
for i in range(n):
    command = list(map(str,input().split()))
    if (command[0] == 'insert'):
        x = command[1]
        if (len(xlist) == 0):
            xlist.append(x)
        else:
            xlist.append(x)
            for i in range(1,len(xlist)):
                k = len(xlist) - i 
                j = k-1
                xlist[j], xlist[k] = xlist[k], xlist[j]
    elif (command[0] == 'delete'):
        x = command[1]
        if x in xlist :
            xlist.remove(x)
    elif (command[0] == 'deleteFirst'):
        if (len(xlist) > 0):
            del xlist[0]
    elif (command[0] == 'deleteLast'):
        if (len(xlist) > 0):
            del xlist[-1]
            
for i in range(len(xlist)):
    if (i == len(xlist) - 1):
        print('{}'.format(xlist[i]), end = '')
    else:
        print('{}'.format(xlist[i]), end = ' ')

Submission status: WA: Presentation Error

Solution code:
n = int(input())
xlist = []
for i in range(n):
    command = list(map(str,input().split()))
    if (command[0] == 'insert'):
        x = command[1]
        if (len(xlist) == 0):
            xlist.append(int(x))
        else:
            xlist.append(int(x))
            for i in range(1,len(xlist)):
                k = len(xlist) - i 
                j = k-1
                xlist[j], xlist[k] = xlist[k], xlist[j]
    elif (command[0] == 'delete'):
        x = command[1]
        if int(x) in xlist :
            xlist.remove(int(x))
    elif (command[0] == 'deleteFirst'):
        if (len(xlist) > 0):
            del xlist[0]
    elif (command[0] == 'deleteLast'):
        if (len(xlist) > 0):
            del xlist[-1]
            
for i in range(len(xlist)):
    if (i == len(xlist) - 1):
        print('{}'.format(xlist[i]), end = '')
    else:
        print('{}'.format(xlist[i]), end = ' ')

Submission status: WA: Presentation Error

Solution code:
n = int(input())
xlist = []
for i in range(n):
    command = list(map(str,input().split()))
    if (command[0] == 'insert'):
        x = command[1]
        if (len(xlist) == 0):
            xlist.append(int(x))
        else:
            xlist.append(int(x))
            for i in range(1,len(xlist)):
                k = len(xlist) - i 
                j = k-1
                xlist[j], xlist[k] = xlist[k], xlist[j]
        #print(xlist)
    elif (command[0] == 'delete'):
        x = command[1]
        if (int(x) in xlist) :
            xlist.remove(int(x))
        #print(xlist)
    elif (command[0] == 'deleteFirst'):
        if (len(xlist) > 0):
            del xlist[0]
        #print(xlist)
    elif (command[0] == 'deleteLast'):
        if (len(xlist) > 0):
            del xlist[-1]
        #print(xlist)
nx = len(xlist)
for i in range(nx):
    if ( i == n-1):
        print('{}'.format(xlist[i]), end = '')
    else:
        print('{}'.format(xlist[i]), end = ' ')

Submission status: WA: Presentation Error

Solution code:
n = int(input())
xlist = []
for i in range(n):
    command = list(map(str,input().split()))
    if (command[0] == 'insert'):
        x = command[1]
        if (len(xlist) == 0):
            xlist.append(int(x))
        else:
            xlist.append(int(x))
            for i in range(1,len(xlist)):
                k = len(xlist) - i 
                j = k-1
                xlist[j], xlist[k] = xlist[k], xlist[j]
        #print(xlist)
    elif (command[0] == 'delete'):
        x = command[1]
        if (int(x) in xlist) :
            xlist.remove(int(x))
        #print(xlist)
    elif (command[0] == 'deleteFirst'):
        if (len(xlist) > 0):
            del xlist[0]
        #print(xlist)
    elif (command[0] == 'deleteLast'):
        if (len(xlist) > 0):
            del xlist[-1]
        #print(xlist)
nx = len(xlist)
for i in range(nx):
    if (i == nx-1):
        print('{}'.format(xlist[i]), end = '')
    else:
        print('{}'.format(xlist[i]), end = ' ')

Submission status: WA: Presentation Error

Solution code:
n = int(input())
xlist = []
for i in range(n):
    command = list(map(str,input().split()))
    if (command[0] == 'insert'):
        x = command[1]
        if (len(xlist) == 0):
            xlist.append(int(x))
        else:
            xlist.append(int(x))
            for i in range(1,len(xlist)):
                k = len(xlist) - i 
                j = k-1
                xlist[j], xlist[k] = xlist[k], xlist[j]
        #print(xlist)
    elif (command[0] == 'delete'):
        x = command[1]
        if (int(x) in xlist) :
            xlist.remove(int(x))
        #print(xlist)
    elif (command[0] == 'deleteFirst'):
        if (len(xlist) > 0):
            del xlist[0]
        #print(xlist)
    elif (command[0] == 'deleteLast'):
        if (len(xlist) > 0):
            del xlist[-1]
        #print(xlist)
n = len(xlist)
for i in range(n):
    if (i == n-1):
        print('{}'.format(xlist[i]), end = '')
    else:
        print('{} '.format(xlist[i]), end = '')

Submission status: WA: Presentation Error

Solution code:
from collections import deque
n = int(input())
xdeque = deque()
for i in range(n):
    command = list(map(str,input().split()))
    if (command[0] == 'insert'):
        x = command[1]
        xdeque.appendleft(int(x))
        #print(xlist)
    elif (command[0] == 'delete'):
        x = command[1]
        if (int(x) in xdeque) :
            xdeque.remove(int(x))
        #print(xlist)
    elif (command[0] == 'deleteFirst'):
        xdeque.popleft()
        #print(xlist)
    elif (command[0] == 'deleteLast'):
        xdeque.pop()
        #print(xlist)
print(*xdeque)
print()

Submission status: WA: Presentation Error

Solution code:
import sys

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

    def __init__(self):
        head = Deque.Cell2(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 = Deque.Cell2(x, q, h)
        h.next = p
        q.prev = p
        self.size += 1

    def pop_back(self):
        if self.size == 0: raise IndexError
        h = self.head
        q = h.prev
        p = q.prev
        p.next = h
        h.prev = p
        self.size -= 1
        return q.data

    def pop_front(self):
        if self.size == 0: raise IndexError
        h = self.head
        q = h.next
        p = q.next
        p.prev = h
        h.next = p
        self.size -= 1
        return q.data

    def delete(self,x):
        h=self.head.next
        while h.data!=x:
            h=h.next
            if h==self.head: raise IndexError
        q=h.next
        p=h.prev
        q.prev=p
        p.next=q
        self.size -= 1
        return

    def __str__(self):
        if self.size == 0: return
        buff = ''
        n = self.size
        cp = self.head.next
        while n > 1:
            buff += '%s, ' % cp.data
            cp = cp.next
            n -= 1
        buff += '%s' % cp.data
        return buff
    
A=Deque()
n=int(raw_input())
while n:
    s = (raw_input().split())
    if s[0] == 'insert':
        A.push_front(s[1])
    elif s[0] == 'delete':
        A.delete(s[1])
    elif s[0] == 'deleteFirst':
        A.pop_front()
    elif s[0] == 'deleteLast':
        A.pop_back()
    n -=1
    
print A
print

Submission status: WA: Presentation Error

Solution code:
import sys,gc

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

    def __init__(self):
        head = Deque.Cell2(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 = Deque.Cell2(x, q, h)
        h.next = p
        q.prev = p
        self.size += 1

    def pop_back(self):
        if self.size == 0: raise IndexError
        h = self.head
        q = h.prev
        p = q.prev
        p.next = h
        h.prev = p
        self.size -= 1
        return q.data

    def pop_front(self):
        if self.size == 0: raise IndexError
        h = self.head
        q = h.next
        p = q.next
        p.prev = h
        h.next = p
        self.size -= 1
        return q.data

    def delete(self,x):
        h=self.head.next
        while h.data!=x:
            h=h.next
            if h==self.head: return
        q=h.next
        p=h.prev
        q.prev=p
        p.next=q
        self.size -= 1
        return

    def __str__(self):
        if self.size == 0: return
        buff = ''
        n = self.size
        cp = self.head.next
        while n > 1:
            buff += '%s ' % cp.data
            cp = cp.next
            n -= 1
        buff += '%s' % cp.data
        return buff
    
A=Deque()
n=int(raw_input())
while n:
    s = (raw_input().split())
    if s[0] == 'insert':
        A.push_front(int(s[1]))
    elif s[0] == 'delete':
        A.delete(int(s[1]))
    elif s[0] == 'deleteFirst':
        A.pop_front()
    elif s[0] == 'deleteLast':
        A.pop_back()
    n -=1
    
print A
print

Submission status: WA: Presentation Error

Solution code:
from sys import stdin

n = int(stdin.readline())
q = []
bottom = 0
for i in range(n):
    cmd = stdin.readline()
    if cmd[0] == 'i':
        q.append(cmd[7:])
    elif cmd[6] == ' ':
        try:
            q.pop(~q[::-1].index(cmd[7:]))
        except:
            pass
    elif cmd[6] == 'F':
        q.pop()
    else:
        bottom += 1

print(' '.join(q[bottom:][::-1]))