This exercise asks you to define some functions for manipulating linked structures. You should use the Node and TwoWayNode classes, as defined in this chapter.

Be sure to reuse your solution from Programming Exercise 4.8 as your starter file for the testnode.py file.

In the testnode.py file, complete the following:

Complete the implementation of the insert method that inserts an item into a singly linked structure at a given position.The function expects three arguments:

item, index

position, newItem

linked structure, head

If the position is greater than or equal to the structures length, the function inserts the item at its end.

Searches for the node at position index -1 or the last position

Inserts new node after node at position index -1 or the last position

The function returns the modified linked structure.

An example call of the function, where head is a variable, is either an empty link or refers to the first node of a structure, head = insert(1, data, head).

To test your program run the main() method below in the testnode.py file.

def main(): """Tests modifications.""" head = None head = insert(0, "1", head) print("1:", end = " ") printStructure(head) head = insert(1, "2", head) print("1 2:", end = " ") printStructure(head) head = insert(0, "0", head) print("0 1 2:", end = " ") printStructure(head) head = insert(3, "3", head) print("0 1 2 3:", end = " ") printStructure(head) head = insert(1, "9", head) print("0 9 1 2 3:", end = " ") printStructure(head) if __name__ == "__main__": main()

Your program's output should look like the following:

1: 1 1 2: 1 2 0 1 2: 0 1 2 0 1 2 3: 0 1 2 3 0 9 1 2 3: 0 9 1 2 3 code from previouse question: 

node.py

=================================

class Node(object): def __init__(self, data, next = None): """Instantiates a Node with default next of None"""  self.data = data self.next = next class TwoWayNode(Node): def __init__(self, data, previous = None, next = None): Node.__init__(self, data, next) self.previous = previous 

======================================

testnode.py

======================================

from node import Node def length(head): """Returns the number of items in the linked structure  referred to by head."""  probe = head count = 0 while probe != None: count += 1 probe = probe.next return count def insert(index, newItem, head): """Inserts newItem at position is the linked structure  referred to by head. Returns a reference to the new  structure."""  if index <= 0: # newItem goes at the head  head = Node(newItem, head) else: # Search for node at position index - 1 or the last position  probe = head while index > 1 and probe.next != None: probe = probe.next index -= 1 # Insert new node after node at position index - 1  # or last position  probe.next = Node(newItem, probe.next) return head def pop(index, head): """Removes the item at index from the linked structure  referred to by head and returns the tuple (head, item)  Precondition: 0 <= index < length(head)"""  # check precondition  if index < 0 or index >= length(head): raise IndexError("Invalid Index!") item = None  if index == 0: # remove first node  item = head head = head.next else: # move to node at given index -1 in linked structure  probe = head for i in range(1, index): probe = probe.next item = probe.next probe.next = item.next item.next = None  return head, item.data def printStructure(head): """Prints the items in the structure referred to by head."""  probe = head while probe != None: print(probe.data, end=" ") probe = probe.next print() def main(): """Tests modifications."""  head = None  head = insert(0, "1", head) print("1:", end=" ") printStructure(head) (head, item) = pop(0, head) print("1:", item, end=" ") printStructure(head) # Add five nodes to the beginning of the linked structure  for count in range(1, 6): head = Node(count, head) (head, item) = pop(0, head) print("5 4 3 2 1:", item, end=" ") printStructure(head) (head, item) = pop(length(head) - 1, head) print("1 4 3 2:", item, end=" ") printStructure(head) (head, item) = pop(1, head) print("3 4 2:", item, end=" ") printStructure(head) # try and except index error and print its message  try: pop(4, head) except IndexError as e: print(e.__str__()) if __name__ == "__main__": main()