CMPUT 229 — Computer Organization and Architecture I

Lab 2: Linked List to Array Conversion

Creator: Saumya Patel

Introduction

In this lab, you will develop your first RISC‑V assembly subroutine that converts a singly linked list into an array and locates the index of a specified target element.

Background

A linked list is a linear data structure where each element, called a node, is dynamically and independently allocated and stored in memory. The nodes of a linked list may be arbitrarily located in memory and may be in non-contiguous memory locations. Each node contains:

Accessing data stored in linked list instead of arrays has several disadvantages:

Thus, even if a program initially builds a linked list, for instance, because the total number of elements is unknown, if the list will be traversed many times, there is an advantage in converting the list to an array and accessing the elements in the array instead.

In this lab, you will use a singly linked list, a type of linked list in which each node points only to the next node. The pointer field of the last node uses a sentinel value (commonly 0 or –1, in this lab, 0) to signify the end of the list. Unlike arrays, linked lists do not require a fixed size and allow efficient insertion and deletion, although traversal must be done sequentially.

Understanding Linked Lists

1. Definition

A linked list is a sequence of nodes where each node stores data and a reference to the next node. Conceptually, it is similar to a series of connected waypoints, where each point provides the direction to the next.

The linked list is specified by the address of its first node in memory. If the linked list is empty, this address is zero (representing the null value). Each node of the linked list contains one integer value and the address of the next element in the list.

2. Use Case

Linked lists are preferred in scenarios where:

While arrays support faster access to elements with a specific index due to direct indexing, they are inefficient when resizing or inserting in between elements.

3. Memory Layout

Linked-list nodes may not be stored in contiguous memory blocks. Each node is dynamically allocated (e.g., using malloc) and comprises:

The pointer of the tail node holds the value of 0 to indicate the end of the linked list.

4. Visual Representation

Linked list diagram showing nodes connected by pointers Linked list diagram showing nodes connected by pointers

C code Example

Below is an example of how a singly linked list can be defined and used in C: 

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// insert at beginning
Node* insert(Node* head, int value) {
    Node* new_node = (Node*)malloc(sizeof(Node)); // allocate memory for new node, common.s already does this. dont worry about it 
    new_node->data = value;
    new_node->next = head;
    return new_node;
}

This snippet defines a node structure and a function that inserts a new node at the beginning of a singly linked list.

Task

Your task is to implement a RISC‑V subroutine called Convert which transforms a singly linked list into an array. This subroutine should begin at the head of the list, traversing each node sequentially and storing each node’s data into consecutive elements of the array. The traversal ends when the address of the next node of an node in the linked list is the address 0 (0x00000000). encountered in the pointer field, which is then placed in the following array element.

Additionally, you are required to locate a specified target element within the list. If the target is found, return the index of its last occurrence as well as return 1 indicating that the index is found . For example, if the target value is 5 and it appears at indices 2 and 7, return 7as well as 1 indicating that the index has been found. If it is not present, return 0 to indicate its absence as well return -1 for the index of the target (which has not been found). Upon completion, the array should contain all node data followed by the sentinel.

The implementation should:

Input Guarantees

Specifications

You are
not required to follow the standard register saving and restoring conventions in your implementation.

The assignment must include the following function:

Testing

When debugging, it can be very helpful to step through the assembly code instruction by instruction. You can use ebreak statements to pause the execution program execution at a specified instruction and examine the state of the registers and memory. From that point you can then execute instructions one by one.

The folder Code/Tests/ contains sample test cases. The *.txt files contain test inputs. The corresponding *.out file contains the correct output. The provided test cases are not extensive. Additional testing is required to ensure that the solution is correct.

To perfom a test, enter the complete file path of the corresponding test input into the Program Arguments box in RARS. The file path cannot have any spaces. Do not put quotations areound the filename. Provide a full path to the file. For example /home/user/cmput229/test.txt is a valid path, while /home/user/cmput 229/this is a test.txt is not. Once you have entered the path to the test case, you can run the program. If the program arguments field does not appear in your RARS, you need to change your settings. Go to Settings -> Program Arguments Provided To Program (second option) and make sure that this opiton is checked.

You can test your lab from a terminal with rars LABFILE pa TESTFILE where LABFILE is the path to magicSquare.s and TESTFILE is the path to the file that contains the test case you want to test. Depending on the version of RARS and your operating system RARS may print extra copyright lines. Ignore these lines.

Test cases are plain text files ending with .txt and must follow the format below: 

L T
[sequence of integers representing the linked list]

Where:

Example:

11 5
5 7 2 3 4 5 1 2 3 4 5

Resources

Marking Guide

Assignments too short to be adequately judged for code quality will be given a zero.

Submission

Ensure that your solution works in the lab machines because it will be graded using the lab machines.

There is a single file to be submitted for this lab: