You are given the file LinkedList.py. There are two classes in the file the SLinkedListNode class and the SLinkedList class. Some of the methods in the SLinkedList class have been done in the lectures in the class. Your task is to complete the implementation of the insert method in SLinkedList class. Once you have completed the method, you can use the code in the main function to test the insert method.

class SLinkedListNode: # an instance of this class is a node in a Single Linked List # a node has a reference to data and reference to next def __init__(self,initData,initNext): self.data = initData self.next = initNext def getNext(self): return self.next def getData(self): return self.data def setData(self,newData): self.data = newData def setNext(self,newNext): self.next = newNext class SLinkedList: # an instance of this class is a Single Linked List object # it has reference to the first node in the list def __init__(self): self.head = None self.size = 0 def add(self,item): # adds an item at the start of the list new_node = SLinkedListNode(item,None) new_node.setNext(self.head) self.head = new_node self.size = self.size + 1 def append(self,item): # adds an item at the end of the list new_node = SLinkedListNode(item,None) current = self.head # Start the traversal if self.size == 0: # check if list is empty self.add(item) else: while (current.getNext()!=None):# WHY? current= current.getNext() # traversing the list current.setNext(new_node) self.size = self.size +1

def insert(self,pos,item): # inserts the item at pos # pos should be a positive number of type int assert isinstance(pos,int),'positiom must be of type int' assert pos >= 0,'position must be a valid number in the range' if pos == 0: # insert at the start of list self.add(item) elif pos >= self.size : #insert at end of list self.append(item) else: # insert in the middle of list new_node = SLinkedListNode(item,None) # COMPLETE THE METHOD

def remove(self,item): # remove the node containing the item from the list if self.size == 0: raise Exception('List is Empty') current = self.head previous = None found = False while current != None and not found: if current.getData() == item: found = True else: previous = current current = current.getNext() if not found: raise Exception('Item not in list') else: if previous == None: # the item is in the first node of the list self.head = current.getNext() else: # item is not in the first node previous.setNext(current.getNext()) self.size = self.size -1 def index(self,item): # finds the location of the item in the list if self.size == 0: raise Exception('List is empty') position = 0 found = False current = self.head while current != None and not found: if current.getData() == item: found = True else: current = current.getNext() position = position + 1 if found: return position else: return 'Item not found' def pop(self): # removes the node from the end of the list and returns the item if self.size == 0: raise Exception('List is empty') current = self.head previous = None while current.getNext() != None: previous = current current = current.getNext() if previous == None: self.head = None else: previous.setNext(None) self.size = self.size -1 return current.getData() def __str__(self): # returns a string representation of the list current = self.head string = '' while current != None: string = string + str(current.getData())+'->' current = current.getNext() return string def getSize(self): return self.size def main(): # Testing Single Linked List slist = SLinkedList() slist.add(2) slist.add(4) slist.add('A') slist.append(77) slist.append(6) slist.append('Z') print('Original List') print(slist) print() slist.insert(0,'start') print('After inserting the word start at position 0') print(slist) print() slist.insert(7,'end') print('After inserting the word end at position 7') print(slist) print() slist.insert(4,'middle') print('After inserting middle at position 4') print(slist) main()

Here is the output that you should get if the insert method has been implemented correctly.

Original List A->4->2->77->6->Z->

After inserting the word start at position 0 start->A->4->2->77->6->Z->

After inserting the word end at position 7 start->A->4->2->77->6->Z->end->

After inserting middle at position 4 start->A->4->2->middle->77->6->Z->end->