Requirement
DLinkedList:
Add new operation to DLinkedList called subList with single parameter for Vehicle’s model. The operation should find all the vehicles with that model and return the Vehicle instances as a list object. If no vehicles are found it should return an empty list.
Modify the code in DLinkedList so that no duplicate vehicle objects can be added based on vin value.
Note: you cannot add any new class members. You can only modify existing functions and/or add new functions. When there is an attempt to add a duplicate vehicle, the operation should raise an exception with meaningful message.
Add new operation to DLinkedList called addList with single parameter which is another DLinkedList instance. The operation should attach the parameter’s list to the end of itself. If the parameter’s list is None, the operation should raise an exception with meaningful message.
Analyze in writing, explaining all calculations and final grow rate, time and space complexity of the new operations to include best, average, and worst case
Write test program (TestDLinkedList class) which creates an instance of the DLinkedList and calls all the new operations to demonstrate they work correctly.
Implementation
D_LinkedList.py
class DLinkedList:
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
def __init__(self):
self.front = None
self.rear = None
self.int_length =0
def addFirst(self, new_data):
new_node = DLinkedList.Node(new_data)
new_node.next = self.front
if self.front is not None:
self.front.prev = new_node
self.front = new_node
self.int_length +=1
def addLast(self, new_data):
new_node = DLinkedList.Node(new_data)
new_node.next = None
if self.front is None:
new_node.prev = None
self.front = new_node
return
last = self.front
while(last.next is not None):
last = last.next
last.next = new_node
new_node.prev = last
self.int_length +=1
return
def printNextLine(self, node):
print("\nTraversal in forward direction")
while(node is not None):
print (" % d" %(node.data),)
last = node
node = node.next
def printPrevLine(self,node):
while(node is not None):
last = node
node = node.next
print("\nTraversal in reverse direction")
while(last is not None):
print(" % d" %(last.data),)
last = last.prev
def deleteFirst(self, dele):
if self.front is None or dele is None:
raise ValueError('list is empty')
if self.front == dele:
self.front = dele.next
if dele.next is not None:
dele.next.prev = dele.prev
if dele.prev is not None:
dele.prev.next = dele.next
self.int_length -=1
def deleteLast(self):
if self.front is None:
raise ValueError('list is empty')
if self.front.next is None:
self.front = None
return
n = self.front
while n.next is not None:
n = n.next
n.prev.next = None
self.int_length -=1
def size(self):
return self.int_length
def deleteAll(self):
while(self.int_length > 0):
DLinkedList.deleteFirst(self,self.front)
return NoneQueue Using Linked List
Implementation
queue_using_linkedList.py
#using linked list
class QueueADT:
def __init__(self,min=1):
if min <= 0:
raise ValueError('queue shoud atleast have one member')
self.capacity= min * 2
self.items = []
def isFull(self):
if len(self.items) == self.capacity:
return True
else :
return False
def isEmpty(self):
if len(self.items) == 0:
return True
else:
return False
def enQueue(self,item):
if QueueADT.isFull(self):
raise ValueError('Queue is full')
self.items.append(item)
def deQueue(self):
if QueueADT.isEmpty(self):
raise ValueError('queue is empty')
return self.items.pop()
def size(self):
return len(self.items)
Queue Using raw Array
Implementation
queue_using_rawArray.py
#using raw array
class QueueADT2:
def __init__(self,min):
self.end = 0
self.capacity = 2 * min
self.items = []
def isEmpty(self):
if self.end == 0:
return True
else:
return False
def isFull(self):
if self.end == self.capacity:
return True
else:
return False
def enQueue(self,item):
if QueueADT2.isFull(self):
raise ValueError('queue is already full')
else:
self.items.append(item)
self.end += 1
def deQueue(self):
if QueueADT2.isEmpty(self):
raise ValueError('queue is empty')
else:
self.end -= 1
return self.items.pop()
def size(self):
return self.end
Stack Using Array
Implementation
stack_arrayBased.py
#arraybase
class StackADT:
def __init__(self,mini=1 ):
if mini <= 0:
raise ValueError(' minimum should be atleast 1')
self.capacity = mini*2
self.items = []
def isEmpty(self):
if len(self.items) ==0:
return True
else:
return False
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def isFull(self):
if StackADT.size(self) == self.capacity:
return True
else:
return False
def size(self):
return len(self.items)
Stack Using DLinkedList
Implementation
stack_DLinkedList.py
#DLINKED LIST BASED
class StackADT2:
def __init__(self,min=1):
self.top = 0
self.capacity=2*min
self.items = []
if min <= 0:
raise ValueError('Minimum value should atleast b 1')
def isEmpty(self):
if self.top == 0:
return True
else:
return False
def isFull(self):
if self.top == self.capacity:
return True
else:
return False
def push(self, item):
if StackADT2.isFull(self):
raise ValueError('Stack is full')
else:
self.items.append(item)
self.top +=1
def pop(self):
if StackADT2.isEmpty(self):
raise ValueError('Stack is empty')
else:
self.top -= 1
return self.items.pop()
def size(self):
return self.top
from queue_using_linkedList import QueueADT
from queue_using_rawArray import QueueADT2
from stack_arrayBased import StackADT
from stack_DLinkedList import StackADT2
from D_LinkedList import DLinkedList
print('LINKED-LIST BASED QUEUE')
q = QueueADT(3)
print('initially','\n queue is full :',q.isFull(),'\n queue is empty :',q.isEmpty())
q.enQueue(4)
print('after enqueuing one element','\n queue is full :',q.isFull(),'\n queue is empty :',q.isEmpty())
print('size of queue',q.size())
q.deQueue()
print('after dequeueing single element','\n queue is full :',q.isFull(),'\n queue is empty :',q.isEmpty())
print('size of queue',q.size())
print(60*'#')
print('RAW-ARRAY BASED QUEUE')
q2 = QueueADT2(4)
print('initially','\n queue is full :',q2.isFull(),'\n queue is empty :',q2.isEmpty())
q2.enQueue(4)
print('after enqueuing one element','\n queue is full :',q2.isFull(),'\n queue is empty :',q2.isEmpty())
print('size of queue',q2.size())
q2.deQueue()
print('after dequeueing single element','\n queue is full :',q2.isFull(),'\n queue is empty :',q2.isEmpty())
print('size of queue',q2.size())
print(60*'#')
print('initially')
print('DLINKED-LIST BASED STACK')
s = StackADT(5)
print('initially','\n stack is full :',s.isFull(),'\n stack is empty :',s.isEmpty())
s.push(4)
print('after pushing one element','\n stack is full :',s.isFull(),'\n stack is empty :',s.isEmpty())
print('size of stack',s.size())
s.pop()
print('after poping single element','\n stack is full :',s.isFull(),'\n stack is empty :',s.isEmpty())
print('size of stack',s.size())
print(60*'#')
print('initially')
print('RAW-ARRAY BASED STACK')
s = StackADT(5)
print('initially','\n stack is full :',s.isFull(),'\n stack is empty :',s.isEmpty())
s.push(4)
print('after pushing one element','\n stack is full :',s.isFull(),'\n stack is empty :',s.isEmpty())
print('size of stack',s.size())
s.pop()
print('after poping single element','\n stack is full :',s.isFull(),'\n stack is empty :',s.isEmpty())
print('size of stack',s.size())
print(60*'#')
print('DOUBLY-LINKED-LIST')
dll = DLinkedList()
print('initial size of DLinkedList', dll.size())
dll.addFirst(4),dll.addLast(5)
print('after adding first and last element', 'size of dll is :', dll.size())
print(dll.printNextLine(dll.front))
print( dll.printPrevLine(dll.front))
dll.deleteFirst(dll.front)
print('after deleting first element','size of dll is :', dll.size())
dll.deleteAll()
print('after deleting all elements','size of dll is :', dll.size())I hope it may help to improve your coding skills in python using data structure, If you need other data structure related help then you can contact us, we are providing online services with an discountable prices. Below the contact details so you can send your request directly and get instant help with our highly educated and experienced expert and PHD researchers.
Contact Us!
realcode4you@gmail.com
Commenti