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 I have so far 

node.py

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

class Node(object): 

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

# newItem goes at the head

head = Node(newItem, head)

else:

# Search for node at position index - 1 or the last position

probe = head

length_linked_structure = length(head)

if index >= length_linked_structure:

index = length_linked_structure - 1

while index > 1:

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

# check precondition

if 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()

Unit Test Incomplete insert( ) inserts a new item at the provided index Test Output (3) 021 F FAIL: test_insert_test (__main_.. UnitTests) Traceback (most recent call last): File "/root/sandbox3c46ceddt-test-ca52aee8.py", line 17, in tes AssertionError: None is not true : expected 021 to match : 12 " Ran 1 test in 0.001s FAILED (failures=1) Test Contents (3) Unit Test - Complete insert( ) moves items at index when inserting