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

self.tail = None
self.size = 0

def getTail(self):
return self.tail

def setTail(self, newtail):
self.tail = newtail

def __repr__(self):
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
node = ListNode(data)
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):
while cur.next is not None:
if cur.next.data == data:
cur.next = cur.next.next
else:
cur = cur.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
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):
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__':