READ THE ASSIGNMENT IN ITS ENTIRETY BEFORE STARTING

Part $1.$ Linked List and The Heap

Linked lists are linear collections of elements used to store data. Unlike arrays, the order of a linked list is independent of the position of elements in memory. Instead, each element stores a pointer to the next element in the linked list.

the assignment deals with implementing and manipulating a singly linked list in RISC$-$V assembly. The linked list will contain a sentinel node, used to indicate the end of the list. The elements in the list should be allocated on the heap, with memory allocated using the sbrk syscall available in RARS.

Assignment Details

The assignment consists of implementing $6$ procedures $($functions$)$ defined in linked$\_$list.asm. Each procedure is documented in the comment above the relevant procedure label. You can assume any pre$-$conditions are fulfilled when the procedure is called. If applicable, your solution must adhere to the post$-$conditions specified in the documentation.

The first procedure you should implement is LL$\_$PUSH$\_$FRONT. The tests for every other procedure requires instantiating the linked list, which involves pushing an element to the front of the list. The other procedures can be implemented in any order. You will receive partial credit for each procedure implemented correctly.

Specification

Your solution must follow the following specification:

$1.$ Use $32-$bit RISC$-$V$.$

$2.$ Each node in the linked list should store a $4-$byte integer as well as a pointer to the next node.

$3.$ Memory for nodes in the linked list should be allocated on the heap using the sbrk syscall in RARS.

$4.$ An empty linked list consists of one sentinel node, which points to memory location $0$x$0$ and has the value $0.$

$5.$ The linked list should not allocate more memory than necessary. If implemented correctly, all nodes should be in a contiguous section of memory on the heap if LL$\_$PUSH$\_$FRONT is called successively. If allocations $($with sbrk$)$ are made in between calls to LL$\_$PUSH$\_$FRONT, then the nodes will not be in a contiguous section of memory. Your code must be able to handle nodes that aren't stored contiguously in memory.

$6.$ You can assume memory addresses returned from sbrk are $4-$byte aligned.

$7.$ You must save any callee$-$saved registers before use in the procedures. Failure to do so may result in an incorrect test output.

Linked List Example

After the following instructions $($note$,$ not assembly$)$:

Linked List Example

After the following instructions $($note$,$ not assembly$)$:

The heap should look like the following diagram:

Note that the Head of Linked List represents a register containing the address of the integer $3$ in the screenshot.

Note that the Head of Linked List represents a register containing the address of the integer $3$ in the screenshot.