Python Assignment Help on Complexity Analysis

• 4th Feb, 2022
• 16:30 PM

class ListNode:
    def __init__(self, data):
        self.data = data
        self.next = None
    
    def __repr__(self):
        return self

class LinkedList:
    def __init__(self, newhead = None):
        self.head = newhead
        self.tail = None
        self.size = 0
    
    def getHead(self):
        return self.head
    
    def getTail(self):
        return self.tail
    
    def setHead(self, newhead):
        self.head = newhead
    
    def setTail(self, newtail):
        self.tail = newtail
    
    def __repr__(self):
        node = self.head
        nodes = []
        while node is not None:
            nodes.append(node.data)
            node = node.next
        nodes.append("None")
        return " -> ".join(map(str, nodes))
    
    # Add an item to the list
    # Time Complexity - O(1) or constant
    # because here we add the new item to the tail and we have a pointer 
    # pointing to the tail
    def addItem(self, data):
        node = ListNode(data)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.size += 1
    
    # Remove an item from the list
    # Time Complexity - O(n) or linear
    # because here we traverse the whole list to find the item to be removed
    def removeItem(self, data):
        prehead = ListNode(-1)
        prehead.next = self.head
        cur = prehead
        while cur.next is not None:
            if cur.next.data == data:
                cur.next = cur.next.next
            else:
                cur = cur.next
        self.head = prehead.next
        self.tail = cur
        self.size -= 1
    
    # Size of the list - Slow version
    # Time Complexity - O(n) or linear
    # because here we traverse the whole list and count the number of nodes
    def sizeSlow(self):
        size = 0
        cur = self.head
        while cur is not None:
            cur = cur.next
            size += 1
        return size
    
    # Size of the list - Fast version
    # Time Complexity - O(1) or constant 
    # because we keep size as a global variable and increment while inserting 
    # and decrement while removing
    def sizeFast(self):
        return self.size
    
    # Check if an item is in the list
    # Time Complexity - O(n) or linear 
    # because we have to check each and every node
    def isPresent(self, data):
        cur = self.head
        while cur is not None:
            if cur.data == data:
                print(f"Item '{data}' is present in the Linked List.")
                return
            cur = cur.next
        print(f"Item '{data}' is not present in the Linked List.")

if __name__ == '__main__':
    llist = LinkedList()
    nums = [77, 56, 49, 62, 69]
    for num in nums:
        llist.addItem(num)
        print(f"Inserting {num} | Resultant LinkedList: {llist.__repr__()} | Head of LinkedList: {llist.head.data} | Tail of LinkedList: {llist.tail.data} | Size of LinkedList: {llist.sizeFast()}")
    num = 62
    llist.removeItem(num)
    print(f"Removing {num} | Resultant LinkedList: {llist.__repr__()} | Head of LinkedList: {llist.head.data} | Tail of LinkedList: {llist.tail.data} | Size of LinkedList: {llist.sizeSlow()}")
    num = 69
    llist.removeItem(num)
    print(f"Removing {num} | Resultant LinkedList: {llist.__repr__()} | Head of LinkedList: {llist.head.data} | Tail of LinkedList: {llist.tail.data} | Size of LinkedList: {llist.sizeSlow()}")