Python Data Structure Assignment Help | DLinkedList, Queue, Stack



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 None


Queue 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



Test.py

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
7 views0 comments