12.15 Assignment 5 - Question 1

Write a MIPS program to insert a given node in a linked list.

Given:

the head of a linked list, i.e, address of the start (first node) of the list

location: number of node in the linked list after which node is to be inserted (0 to insert before the 1st node, 1 to insert after 1st node and so on.)

the address of the node to be inserted And each node contains:

an integer value

address to the next node (address is NULL (0) if it is the last node in the list)

Write the following three functions that will be called in order to update the linked list by inserting the node.

main

task: calls the insert function and reads the value of the inserted node.

insert

inputs: head of linked list (head), location to insert node (n) and address of node to be inserted (node)

task: calls the find function and inserts the node after the n^th node in the linked list. If the number is greater than the size of list, then insert the node at the end of the list.

output: value of the inserted node.

find

inputs: head of linked list (*head) and location to insert node (n)

task: navigate the linked list to find the addresses of the n^th and (n+1)^th nodes

outputs: addresses of the n^th and (n+1)^th nodes.

Refer to the Linked List.pdf file on canvas support material to understand how linked lists are stored in memory and what are the changes when a node is inserted in a list (example used is the same as the one given below). For further explanation, refer to the video and explanation in Assignment 5 Discussion.

Following is a sample C code segment (this code is incomplete and does not include creating the linked list or the node to be inserted) to perform the required task. You may modify the code for the functions, but the task performed should not be changed.

// Parameters of a node in the linked list struct node { int value; // Value in the node accessed by node->value int* next; // Address of next node accessed by node->next }; int main() { // Variable Declaration int *head; // address of head (first node) of linked list int *node; // address of node to be inserted int n; // number of the node in the list after which node is to be inserted int val; // Value of the node to be inserted // Task of main function val = insert(head, n, node); } int insert(int* head, int n, int* node) { int* addr1, addr2; // addr1 = address of n^th node, addr2 = address of (n+1)^th node if (n == 0) { node->next = head; // Next for inserted node = head of original list head = node; // head updated to the inserted node return(node->value); // value of the node = data at the address of the node } [addr1, addr2] = find(head, n); addr1->next = node; // Next for n^th node = node to be inserted node->next = addr2; // Next for inserted node = (n+1)^th node of original list return(node->value); // value of the node = data at the address of the node } int* find(int* head, int n) { int* curr = head; // Start with head of linked list for (int i = 1, i < n; i ++) { curr = curr->next; // Update the pointer to next node address if (curr->next == 0) break; } return([curr, curr->next]); } 

Registers	Variables
$s0	head
$s1	node
$s2	n
$s3	val

Linked List and Node in Memory:

Addresses	Contents
node	node->value
head	node1->value
head + 4	node1->next
node1->next	node2->value
node1->next + 4	node2->next
node2->next	node3->value
node2->next + 4	node3->next

Example Test: If the values of $s0 through $s3 and Memory contents are initialized in the simulator as:

(Use the '+' button under the Registers display to initialize register values for $s0, $s1, $s2 and the '+' button under the Memory display to initialize the initial array elements.)

Registers	Data
$s0	4000
$s1	8000
$s2	2
$s3	0

Addresses	Contents
8000	230
4000	4
4004	3848
3848	-15
3852	6104
6104	-10
6108	5008
5008	0
5012	4500
4500	40
4504	0

The resultant registers are:

Registers	Data
$s0	4000
$s1	8000
$s2	2
$s3	230

The resultant array is:

Addresses	Contents
8000	230
8004	6104
4000	4
4004	3848
3848	-15
3852	8000
6104	-10
6108	5008
5008	0
5012	4500
4500	40
4504	0

Grading: Manual score (10 points) will be added after the deadline.

4 automated tests each worth 5 points. The registers $s0, $s1, $s2, $s3 and the linked list elements in memory will be checked by the automated tests.

Comments specifying your choice of registers and each line of your code (5 points).

Correct use of Nested Procedure Calls (5 points).