1. Define a function length that expects a singly linked structure (the head of the structure) as an argument. The function returns the number of items (nodes) in the structure.

2. Define a function printStructure that expects a linked structure as an argument. The function prints each item in the structure. The function does not return a value.

3. Define a function insert that inserts an item into a singly linked structure in the correct position, so that the structure is always kept in ascending order (alphabetical). The function expects two arguments: the item and the linked structure (which may be empty). The function returns the modified linked structure.

The function main continually asks the user for a string, and adds it to a linked structure in ascending order, by calling the function insert. When the user enters an empty string, the program calls the function length to display the length of the list, then calls the function printStructure to display the contents of the list, then ends execution. You do not need to modify the function main.

The program uses the Node class:

"""

File: node.py

Node classes for one-way linked structures and two-way

linked structures.

"""

class Node(object):

def __init__(self, data, next = None):

"""Instantiates a Node with default next of None"""

self.data = data

self.next = next

Sample output 1: >>> RESTART: C:\a4.py Please enter a word (or just hit enter to end): bottle Please enter a word (or just hit enter to end): a Please enter a word (or just hit enter to end): water Please enter a word (or just hit enter to end): of Please enter a word (or just hit enter to end): The structure contains 4 items: a bottle of water

Sample output 2 (note: items are strings, so lexicographical order is ok): >>> RESTART: C:\a4.py Please enter a word (or just hit enter to end): 5 Please enter a word (or just hit enter to end): 10 Please enter a word (or just hit enter to end): 20 Please enter a word (or just hit enter to end): 15 Please enter a word (or just hit enter to end): 1 Please enter a word (or just hit enter to end): 8 Please enter a word (or just hit enter to end): The structure contains 6 items: 1 10 15 20 5 8

Sample output 3 (note: case should be ignored): >>> RESTART: C:\a4.py Please enter a word (or just hit enter to end): Ana Please enter a word (or just hit enter to end): Bill Please enter a word (or just hit enter to end): car Please enter a word (or just hit enter to end): algorithm Please enter a word (or just hit enter to end): button Please enter a word (or just hit enter to end): The structure contains 5 items: algorithm Ana Bill button car