Question

Problem Description: Using Python write a Singly‐Linked List (with only the Head pointer) that supports the following operations: 1. Adding an element at the middle of the list. 2. Removing the middle element of the list (and return the data). 3. Adding an element at a given index. 4. Removing an element at a given index (and return the data). For #1 and #2, ignore the operations if the length of the list is an even number. For #3, if there is already an element at the specified index, it (and everything coming before it) should be shifted left. if the specified index is beyond the existing list, then add the new element at the end of the list. For #4, ignore the operation if there is no item at the specified index. For each of these operations, design appropriate test cases for exhaustively testing the operation, and show the contents of the list before and after executing each test by grouping test case inputoutputs for a given operation to ensure readability.

Note: You have to use the linked list skeleton code provided with this document as a starter code for your solution. You CANNOT use any of the other methods (such as addBefore(), removeAfter(), search(), etc.)

class Node:
"""Node class for a linked list"""
  
def __init__(self, item=None):
"""constructor for the Node class"""
self._item = item
self._next = None
  
def __str__(self):
return str(self._item)
  

class SLL_H:
  
def __init__(self):
self._head = None
  
def __str__(self):
"""overloaded function for converting the linked list to a string"""

str_rep = ""
curr = self._head
  
str_rep +="Head-> "

while(curr):
str_rep +=str(curr._item)
str_rep +=" -> "
curr = curr._next
str_rep +="None"
  
return str_rep

Answer 1

'''
Python version : 2.7
Python program to create and implement a single linked list with only head pointer
'''

class Node:
   """Node class for a linked list"""
  
   def __init__(self, item=None):
       """constructor for the Node class"""
       self._item = item
       self._next = None

   def __str__(self):
       return str(self._item)
      
class SLL_H:
  
   def __init__(self):
       self._head = None
      
   def __str__(self):
       """overloaded function for converting the linked list to a string"""
       str_rep = ""
       curr = self._head
      
       str_rep +="Head-> "
      
       while(curr):
           str_rep +=str(curr._item)
           str_rep +=" -> "
           curr = curr._next
       str_rep +="None"
       return str_rep

   def _length(self):
       """ helper function to return the length of the list """
       length = 0
       curr = self._head
      
       while curr != None:
           length += 1
           curr = curr._next
          
       return length  
  
   def add_at_middle(self,item):
       """ function to insert the item at the middle of the list """
       length = self._length()
       # if length of the list if even, ignore the operation  
       if length%2 != 0:
           node = Node(item)
          
           curr = self._head
           prev = None
           idx = 0
           mid = int(length/2) # get the index of the middle
          
           # get the current middle element
           while(idx < mid):
               prev = curr
               curr = curr._next
               idx += 1
           # insert at middle  
           prev._next = node
           node._next = curr  
  
   def remove_at_middle(self):
       """ function to remove and return the item at the middle"""
       length = self._length()
       # if length of the list is even , ignore the operation and return None  
       if length%2 != 0:
          
           curr = self._head
           prev = None
           idx = 0
           mid = int(length/2) # get the index of the middle
          
           # loop to get the middle element
           while(idx < mid):
               prev = curr
               curr = curr._next
               idx += 1
           # remove middle element
           item = curr._item  
           if prev != None:
               prev._next = curr._next
           else:
               self._head = self._head._next
          
           return item
          
       return None

   def add_at_index(self, item, index):
       """ function to insert the item at the given index"""
       node = Node(item)
      
       length = self._length()
       # check if index is within the bounds of the list  
       if index >= 0 and index < length:
          
           idx = 0
           curr = self._head
           prev = None
          
           # get the current element at index
           while(idx < index):
               prev = curr
               curr = curr._next
               idx += 1
          
           if prev != None:
               prev._next = node
               node._next = curr
           else:
               node._next = self._head
               self._head = node
          
       else:
           # if index is beyond the bounds of the list, then insert at the end
           if length == 0:
               self._head = node
           else:
               curr = self._head
              
               while curr._next != None:
                   curr = curr._next
                  
               curr._next = node
      
   def remove_at_index(self, index):
       """ function to remove and return the item at the index """  
       length = self._length()
      
       # if index is within the bounds , remove the element
       if index >=0 and index < length:
          
           idx = 0
           prev = None
           curr = self._head
          
           # get the current item at the index
           while idx < index:
              
               prev = curr
               curr = curr._next
               idx += 1
          
           item = curr._item
           # remove the item
           if prev == None:
               self._head = self._head._next
           else:
               prev._next = curr._next
              
           return item
       return None

# function to test the operations of single linked list      
def main():
          
   sll = SLL_H()      
   sll.add_at_index(3,0)
   print('List : ')
   print(sll)
   sll.add_at_index(15,4)
   print('List after inserting at index 4: ')
   print(sll)
   sll.add_at_middle(4)
   print('List after inserting in middle : ')
   print(sll)
   sll.add_at_index(4,1)
   print('List after inserting at index: ')
   print(sll)
   sll.add_at_middle(5)
   print('List after inserting at middle: ')
   print(sll)
   print('Middle element : '+str(sll.remove_at_middle()))
   print('List after remove middle: ')
   print(sll)
   print('Element at index 2 : '+str(sll.remove_at_index(2)))
   print('List : ')
   print(sll)
   print('Element at middle :' +str(sll.remove_at_middle()))
   print('List : ')
   print(sll)
   print('Element at index 4 : '+str(sll.remove_at_index(4)))
   print('List : ')
   print(sll)
   print('Element at middle : '+str(sll.remove_at_middle()))
   print('List : ')
   print(sll)

#call the main function  
main()  
              
#end of program          

Code Screenshot:

Output: