class d_linked_list: def __init__(self): self.__head=None self.__tail=None self.__size=0 def search(self, item): current = self.__head found = False while current != None and not found: if current.getData() == item: found= True else: current = current.getNext() return found def index(self, item): current = self.__head found = False index = 0 while current != None and not found: if current.getData() == item: found= True else: current = current.getNext() index = index + 1 if not found: index = -1 return index def add(self, item): # adds an item to list at the beginning temp = DLinkedListNode(item, self.head, None) if self.head != None: self.head.setPrevious(temp) else: self.tail=temp self.head = temp self.size += 1 def remove(self, item): # search for the item and remove it # the method assumes the item exists current = self.head previous=None found = False while not found: if current.getData() == item: found = True else: previous = current current = current.getNext() if previous == None: self.head = current.getNext() else: previous.setNext(current.getNext()) if (current.getNext() != None): current.getNext().setPrevious(previous) else: self.tail=previous self.size -= 1 def append(self, item): # adds the item to the end of the list # must traverse the list to the end and add item temp = DLinkedListNode(item, None, None) if (self.head == None): self.head=temp else: self.tail.setNext(temp) temp.setPrevious(self.tail) self.tail=temp self.size +=1 def insert(self, pos, item): temp = d_linked_node(item,None,None) current = self.__head positionCounter = 0 while current != None: if positionCounter == pos: if current.getPrevious() != None: temp.setPrevious(current.getPrevious()) #will point the previous of the node to before item) temp.setNext(current) #will point to the next item current.getPrevious().setNext(temp) #will point the next of the node current.setPrevious(temp) self.__size += 1 else: self.add(item) positionCounter +=1 current = current.getNext() if positionCounter == pos: self.append(item) self.__size += 1 def pop1(self): if(self.get_size() == 0): return None if(self.get_size() == 1): element = self.__head.getData() self.__head = self.__tail = None self.__size = self.__size - 1 return element temp = self.__head while(temp.getNext() != None): temp = temp.getNext() element = temp.getData() temp.getPrevious().setNext(None) self.__tail = temp.getPrevious() self.__size = self.__size - 1 return element def pop(self, pos): current = self.__head counter = 0 found = False if pos == 0: return pop1() while (current != None): if counter == pos: item = current.getData() current.getPrevious().setNext(current.getNext()) if current.getNext() != None: current.getNext().setPrevious(current.getPrevious()) self.__size = self.__size - 1 return item current = current.getNext() counter = counter +1 return None def search_larger(self, item): current = self.__head index = 0 while current != None: if current.getData() > item: return index current = current.getNext() index = index + 1 return None def get_size(self): return self.__size def get_item(self, pos): if pos >= 0: index = 0 current = self.__head while current != None: if index == pos: return current.getData() current = current.getNext() index = index + 1 else: index = -1 current = self.__tail while current != None: if index == pos: return current.getData() current = current.getPrevious() index = index - 1 return None def __str__(self): if(self.get_size() == 0): return "Empty list" current = self.__head nodeList = "" while(current.getNext() != None): nodeList = nodeList + str(current.getData())+" " current = current.getNext() nodeList = nodeList + str(current.getData()) return nodeList

For this exercise you have to use the d linked_list that you created in exercise 1 You have to implement the methods for the class m _sorted list, which when initialized takes a parameter sorted which is true or false. When the parameter is true the list is sorted in ascending order. When the parameter is false t acts as a normal unbounded queue Maybe Sorted List: Methods init_(self, m_sorted) o Initialization of the class with parameter mSorted which is true or false add(self, item) o Adds the item to the correct position if the list is sorted or adds the item to the end of the list if the list is not sorted * pop(self) o Removes and returns the first item in the list if the list is not sorted, or returns and removes the largest number in the list if it is sorted . search(self, item) o Returns a tuple, with the first element being true or false if the item was found in the list or not, and the second element is the index of the of the item if it was found, or if it is not found, if the list is sorted it is the index of the first item that is larger than item, and -1 if the list is unsorted or there is no larger item in the list Maybe Sorted List: Methods o change_sorted(self) Change the list from sorted to unsorted, or raises an exception o with the message "l don't know how to sort a doubly linked list yet" get_size(self) o Returns the size of the list get item(self,pos) o Returns item at pos str (self) . Returns a string that is the elements of the list o For this exercise you have to use the d linked_list that you created in exercise 1 You have to implement the methods for the class m _sorted list, which when initialized takes a parameter sorted which is true or false. When the parameter is true the list is sorted in ascending order. When the parameter is false t acts as a normal unbounded queue Maybe Sorted List: Methods init_(self, m_sorted) o Initialization of the class with parameter mSorted which is true or false add(self, item) o Adds the item to the correct position if the list is sorted or adds the item to the end of the list if the list is not sorted * pop(self) o Removes and returns the first item in the list if the list is not sorted, or returns and removes the largest number in the list if it is sorted . search(self, item) o Returns a tuple, with the first element being true or false if the item was found in the list or not, and the second element is the index of the of the item if it was found, or if it is not found, if the list is sorted it is the index of the first item that is larger than item, and -1 if the list is unsorted or there is no larger item in the list Maybe Sorted List: Methods o change_sorted(self) Change the list from sorted to unsorted, or raises an exception o with the message "l don't know how to sort a doubly linked list yet" get_size(self) o Returns the size of the list get item(self,pos) o Returns item at pos str (self) . Returns a string that is the elements of the list o