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