Task: Write a CASM assembler program that augments our linked list program with two new subroutines:

insert_sorted(int newvalue, node* head_ptr) -- returns the address of the new node if head_ptr is null, otherwise it returns head_ptr

print_list(node* head_ptr)

Note that insert_sorted() returns the address of the new node if head_ptr is NULL (the number 0.) This occurs when the list is empty. The main program needs to be able to permanently save the head of the chain. So the main program just assigns to its head point whatever insert_sorted returns.

To allocate a new "node" in the linked list, simply get the memory location from a variable FREEMEMPTR, and use that address. Make sure to add 2 to FREEMEMPTR (which is just a simple integer variable) so that next time you don't reclaim memory that is already used.

print_list() merely spins through the entire list and prints out the list, one after the other, using STD 4095.

Rubric:

30	Program functions correctly for all test cases (see below)
10	Proper structures are used (assembler templates and array templates)
10	Comments exist

Test cases:

1. print_list prints an empty list correctly

2. print_list prints a list with 1 or more elements correctly (in right order)

3. insert_sorted creates a list with one node and returns that address when head_ptr == NULL

4. insert_sorted() puts a new node into the middle of an existing list correctly (in the correct place)

5. insert_sorted() puts a new node into an existing list at the end if the new value is greater than all the values in the list

Image of the linked list in memory:

;-------------------------------------------------------------------------

HEAD: NUM 2500 ; pointer to first node

FREEMEMPTR: NUM 2508 ; next free spot after end of the chain

=2500

NUM 46 ; first node in the list

NUM *+1 ; pointer to next free slot (will be 2501)

NUM 99 ; second node in list

NUM *+1

NUM 17 ; third node in the list

NUM *+1

NUM 57 ; third node in the list

NUM 0 ; NULL, end of list marker

The directive NUM *+1 means to add 1 to the current memory pointer as it is being assembled. Think of the *, when it is used as an operand to NUM, as being "this memory location right here, i.e. the address of this NUM."