Question

Write a MIPS assembly language program that uses dynamic memory allocation to create and manage a linked list data structure.

Gives the user the following options:                        

1. To create and add the first node to a linked list.         

2. To add a single node to the pre-existing linked list.        

    The list must already exist before a new node can be added.       

    The nodes should be maintained in ascending order based on the data value within the nodes by inserting new nodes into the proper place within the list. If the data value matches a data value already in the list, then the new node should be inserted after any previous nodes that contain the same data value.                                                       

3. To delete a node from the linked list structure based on the ID field within the node. Remove the node with that ID                              

4. To search the list and display the node found to contain an ID that matches the target search ID.                  

5. To search the list and display all nodes found to contain a specified data value.                      

6. To display the nodes within the list from start to end by printing the ID and data fields of each.                    

7. To terminate the program by entering X as a command.        

Attempts to create a list should be rejected if a list already exits. Attempts to add to or access the list should be rejected if the list does not already exist. Allocate each node as a 3-word unit that contains the ID, data value and a link to the node that follows.

+--------------+-------------------+---------------+           

|   ID field   |   data field     | link field   |             +--------------+-------------------+---------------+            

(Use the sbrk syscall to obtain memory for the nodes.)                                                                       

When adding a node to the list, the new node should be inserted into the proper place within the list so as to keep the list in ascending order based on the data values within the nodes. Multiple nodes are allowed to have the same data value. A new node with the same data value as one or more existing nodes should be inserted after the existing nodes.   The link field within each node contains the address of the node that logically follows. A null link field contains 0 and indicates the final node within the linked list structure.      

A separate head pointer is used to specify the first node within the list. A null head pointer denotes an empty list.    

Sample output from the program is shown below. (Sample shows floating point. You do not need to have values that are floating point. You may have integer values.)

Console Specify an action to take for th linked list: C to create the list to display the list A to add a single node D to delete a node S to search for a node with the specified ID F to search for a node with a specified value Enter an integer for the ID field: 21 Enter the node s data field: 3.4 Specify an action to take for the linked list: C to create the list L to display the list A to add a single node D t冲d@lete nod* S to search for a node with the specified ID F to search for a node with a specified value OrX to terninate A Enter an integer for the ID field: 36 Enter the sode s data field: -1.2 Specify an action to take for the linked list: C to create the ist L to display the list A to add a single node D to delete a node, S to search for a node with the specif F t수 se reh for o node with ă specified value ied ID Or X to terninate :A Enter an isteger or th ID field: 7 Enter the ode's data f1eld: S6.9 Specily an action to take o the linked list: C to ereate the list L to display the list A to add a single node D to delete a node. S to search for a node with the specified ID F to search for node 뷰1th specified value r to terinate : L next node is: 36 .20000005 he next node is: 21 3.40000010 next node is:7 56.90000153 Specify an action to take for the linked list: C to create the list L to display the list. A to add a single node D to delete a node S to se arch for node with the pecified ID F to search for a node with a specified value Or X to terninate:

Answer 1

Solution:

............................................................................................................................................................

" Data options: .asciiz ""Please type in one of the number below and press enter: \n 1 - exit program \n 2 - next node \n 3 - previous node \n 4 - insert after current node \n 5 - delete current node \n 6 - reset \n 7 - debug \n"" insertMessage: .asciiz ""Please type a string up to 10 characters and press enter\n"" character: .asciiz """" empty: .asciiz ""There is no node yet \n"" doneAdding: .asciiz ""\nAdding is done\n"" currentls: .asciiz ""The current node: "" emptyLine: .asciiz ""\n