1. (20 points) Write a MIPS assembly program that reads in an integer which is assumed to be in the range 010. The program then reads that many additional integer values, inserting each of them into an initially-empty sorted list. After all the values are read, the entire list should be printed, with spaces (ASCII value 32) separating each value and terminated by a newline (ASCII value 10). Java code for the insertion part is below. I suggest that you develop the code a bit at a time: Begin with the printing and insertion into a position other than the front (i.e. without the if statement below); youll want to use the lab code so that the program starts with a non-empty list. Then, make your insertion code able to add to the front of the list (youll need to store the address of the first node in a register so that you can change it). Then put the insertion routine into a loop that reads a number and inserts it. To get the memory for each node, youll need to reserve a block that is big enough:

.data nodes: .space 80 #reserve space for 10 8-byte nodes

Then use a register to store the first unused address in this block of memory. (Initially, that would be the address of the nodes label.) To allocate memory for a new node, youd use the current value of your register and add 8 to its value. For example, if you were using $s0, then youd want something like

add $t0, $s0, $zero #give $t0 address of new node addi $s0, $s0, 8 #advance $s0 so it points at node after that one

Finally, here is the Java code for inserting into a sorted linked list:

public void insert(int val) { Node n = new Node(); n.val = val; Node curr = first; if(curr == null || val < curr.val) { //special case: inserting into front n.next = first; first = n; } else { while((curr.next != null) && (curr.next.val < val)) //find where to insert curr = curr.next; n.next = curr.next; //insert after curr curr.next = n; } }