
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()}")