Lab 4 - Linked lists and functions

Intro to Computer Architecture
Spring, 2018
Due:  March 12 (11:59 pm)

Write a program to implement doubly-linked lists of integers in MIPS assembly language  Your implementation will include functions to

List specifications

1.  A "list" should be stored as a struct consisting of two addresses:  a pointer to the head of the list and a pointer to the tail of the list.  You can create an empty list in your data section with the directive

list:    .word    0,0

2.  A node is a struct consisting of three words:  a data item, a prior pointer, and a next pointer.

3.  Use a value of 0 to indicate a null pointer.

4.  Allocate space for list nodes as follows:

Main program

The main program will operate on two linked lists, one containing even integers and the other containing odd integers.  The program will read a sequence of integers from the user, and insert each one into the appropriate list.  Items should be added to the end of the list.  The input will be terminated by a value of -9999.  When the input is complete

When you display the contents of the list use the format shown below.  For each node, print the address of the node, the prior and next pointers from the node, and the data item in the node.  Print the data items in decimal and all of the addresses in hex.

sample input:

307
200
419
100
500
257
-9999

sample output:

even list in forward order:
address         prior           next           data
0x10040018      0x00000000      0x10040030      200
0x10040030      0x10040018      0x1004003c      100
0x1004003c      0x10040030      0x00000000      500

odd list in forward order:
address         prior           next           data
0x1004000c      0x00000000      0x10040024      307
0x10040024      0x1004000c      0x10040048      419
0x10040048      0x10040024      0x00000000      257

even list in reverse order:
address         prior           next           data
0x1004003c      0x10040030      0x00000000      500
0x10040030      0x10040018      0x1004003c      100
0x10040018      0x00000000      0x10040030      200

odd list in reverse order:
address         prior           next           data
0x10040048      0x10040024      0x00000000      257
0x10040024      0x1004000c      0x10040048      419
0x1004000c      0x00000000      0x10040024      307

Function specifications:

Write (and use) functions for the following:

a.  Insert a data item in a linked list.  (a0 = address of the list; a1 = item to be added)

b.  Print the contents of a linked list in forward order.  If the list is empty, either print nothing, or print a message to indicate that the list is empty. (a0 = address of the list)

c.  Print the contents of a linked list in reverse order.  If the list is empty, either print nothing, or print a message to indicate that the list is empty. (a0 = address of the list)


The functions should work on any linked list, so within your functions, you should not refer to the linked list directly by name.