Question

There are two calsses: node.py and a5.py. The a5.py contains three important methods:

• Length -> Outputs the length of the linked list
• Insert -> Inserts an element into the linked list
• PrintStructure -> Prints the entire linked list starting from the head

The task is to fill in these methods given in the a5.py. Hints are given to you inside the a5.py class so make sure to check them out. Note that one of the important concepts in this example is that when a new element is inserted into the list, it gets inserted into it’s appropriate (sorted) position. Please take a look at the examples to see how random values are inputted and the result is sorted.

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

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

NODE.PY

"""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

A5.PY

"""
File: a5.py


Define a length function.
Define a printStructure function.
Define an insert function.
Test the above functions and the Node class.
"""

from node import Node

def length(head):
    """Returns the number of items in the linked structure
    referred to by head."""
    probe = head
    count = 0
   
    # ADD CODE HERE: Count the number of nodes in the structure
   
    return count
   
def insert(newItem, head):
    """Inserts newItem at the correct position (ascending order) in
    the linked structure referred to by head.
    Returns a reference to the new structure."""
    # if head == None:
        # if structure is empty
        # ADD CODE HERE       
    # else:
        #Insert newItem in its place (ascending order)
      # ADD CODE HERE
       
    return head

def printStructure(head):
    """Prints the items in the structure referred to by head."""
    # ADD CODE HERE

def main():
    """Gets words from the user and inserts in the
    structure referred to by head."""
   
    head = None
    userInput = input('Please enter a word (or just hit enter to end): ')
    while userInput != '':
        head = insert(userInput, head)
        userInput = input('Please enter a word (or just hit enter to end): ')
    print('The structure contains', length(head), 'items:')
    printStructure(head)

if __name__ == "__main__": main()

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

Note: Please maintain proper code spacing (indentation), just copy the code part and paste it in your compiler/IDE directly, no modifications required.

#code

from Node import Node


def length(head):
    """Returns the number of items in the linked structure
    referred to by head."""
    probe = head
    count = 0
    #loops until probe is None
    while probe!=None:
        #updating count, advancing probe
        count+=1
        probe=probe.next
    return count


def insert(newItem, head):
    """Inserts newItem at the correct position (ascending order) in
    the linked structure referred to by head.
    Returns a reference to the new structure."""
    #creating a new node with newItem as data
    node=Node(newItem)
    #if head is None, returning node
    if head == None:
        return node
    #checking if newItem can be added before current head
    #assuming data is of string type, comparing without case sensitivity as
    #displayed by second example in the sample output (algorithm Ana Bill button car)
    if newItem.lower()<head.data.lower():
        #adding head as next of node and returning node
        node.next=head
        return node
    #taking a reference to head
    probe=head
    #loops until probe.next is None
    while probe.next!=None:
        #checking if element can be added between probe and probe.next
        if newItem.lower()>=probe.data.lower() and newItem.lower()<=probe.next.data.lower():
            #adding between the nodes and returning head
            node.next=probe.next
            probe.next=node
            return head
        probe=probe.next
    #if still not added, adding at last and returning head
    probe.next=node
    return head

    return head


def printStructure(head):
    """Prints the items in the structure referred to by head."""
    probe=head
    #looping and printing each item separated by white spaces
    while probe!=None:
        print(probe.data,end=' ')
        probe=probe.next
    print()


def main():
    """Gets words from the user and inserts in the
    structure referred to by head."""

    head = None
    userInput = input('Please enter a word (or just hit enter to end): ')
    while userInput != '':
        head = insert(userInput, head)
        userInput = input('Please enter a word (or just hit enter to end): ')
    print('The structure contains', length(head), 'items:')
    printStructure(head)


if __name__ == "__main__": main()