Continuing with the LinkedList class implementation, define the add_sorted() method which can be used to keep the elements in a linked list in a sorted order (for example, numerical order, or lexicographic order). If all elements are added to the list using the add_sorted() method, then the elements in the linked list will be in increasing order.

class LinkedList:

def __init__(self, head = None): self.head = head

def add(self, item): new_node = Node(item) new_node.set_next(self.head) self.head = new_node

def is_empty(self): if self.head == None: return True else: return False def size(self): count = 0 node = self.head while node != None: count += 1 node = node.get_next() return count def search(self, value): node = self.head while node != None: if node.get_data() == value: return True else: node = node.get_next() return False def remove(self, item): if self.head is not None: if self.head.get_data() == item: self.head = self.head.get_next() else: temp = self.head while temp is not None and temp.get_next() is not None: if temp.get_next().get_data() == item: temp.set_next(temp.get_next().get_next()) temp = temp.get_next() def __str__(self): lst = [] temp = self.head while temp != None: lst.append(str(temp.get_data())) temp = temp.get_next() return "(" + ', '.join(lst) + ")"

def remove_from_tail(self): if self.head is None: return None elif self.head.get_next() is None: result = self.head self.head = self.head.get_next() return result else: temp = self.head while temp.get_next().get_next() is not None: temp = temp.get_next() result = temp.get_next() temp.set_next(temp.get_next().get_next()) return result

For example, executing the following code with the completed class:

fruit = LinkedList() fruit.add_sorted('banana') fruit.add_sorted('cherry') fruit.add_sorted('apple')

results the linked list as shown in the diagram below:

NOTE: You can assume the Node class is provided to you and you do not need to define the Node class. Submit your entire LinkedList class

For example:

Test	Result
fruit = LinkedList() fruit.add_sorted('banana') fruit.add_sorted('cherry') fruit.add_sorted('apple') print(fruit)	(apple, banana, cherry)
my_list = LinkedList() my_list.add_sorted('add') my_list.add_sorted('cat') my_list.add_sorted('bit') print(my_list)	(add, bit, cat)