Question

How to write MIPS function that recursively prints out linked list that takes one argument (address of firstNode), and is separated by commas.  

Answer 1

• Understanding the linked list
• purpose of list to provide storage space
• The conventional data types likes, arrays, structures and unions can provide storage
• but traversal is more easier and effective in linked lists
• there arr 2 types of linked list – singly and doubly linked lists
• Singly linked lists just have a field called next pointer ( apart from their data variable)
• Doubly linked lists would have both previous and next pointers ( apart from data variable)
• for this question, it is suffice, if we just focus on singly linked list
• Singly linked list will also provide operations like insert, delete, traversals (in order, preorder, post order)
• In order: Left Visit Right ( LVR)
• pre order: V L R
• Post order : L R V
• The typical application is to use them on binary trees, binary search trees (BST), Avalanche (AVL) Trees, etc
• so much so for the basics, let us jump in to the code:

        .Ltext0:
                        .section       .rodata
                        .align 8

                .LC0:
0000 0A20456E                 .string        "\n Enter the data for the nodes of singly linked list please: "
     74657220 
     74686520 
     64617461 
     20666F72 

                .LC1:
003e 256400                   .string        "%d"
                        .text
                        .globl main
                main:

                .LFB0:

                        .cfi_startproc
0000 55                       pushq   %rbp
                        .cfi_def_cfa_offset 16
                        .cfi_offset 6, -16
0001 4889E5                   movq    %rsp, %rbp
                        .cfi_def_cfa_register 6
0004 4883EC20                 subq    $32, %rsp

0008 BF100000                 movl    $16, %edi
     00
000d E8000000                 call    malloc
     00
0012 488945F8                 movq    %rax, -8(%rbp)

0016 488B45F8                 movq    -8(%rbp), %rax
001a 48C74008                 movq    $0, 8(%rax)
     00000000 

0022 BF000000                 movl    $.LC0, %edi
     00
0027 B8000000                 movl    $0, %eax
     00
002c E8000000                 call    printf
     00

0031 488D45EC                 leaq    -20(%rbp), %rax
0035 4889C6                   movq    %rax, %rsi
0038 BF000000                 movl    $.LC1, %edi
     00
003d B8000000                 movl    $0, %eax
     00
0042 E8000000                 call    __isoc99_scanf
     00

0047 8B55EC                   movl    -20(%rbp), %edx
004a 488B45F8                 movq    -8(%rbp), %rax
004e 8910                     movl    %edx, (%rax)

0050 488B45F8                 movq    -8(%rbp), %rax
0054 488945F0                 movq    %rax, -16(%rbp)

0058 48837DF0                 cmpq    $0, -16(%rbp)
     00
005d 741B                     je      .L2

005f EB0C                     jmp     .L3

                .L4:

0061 488B45F0                 movq    -16(%rbp), %rax
0065 488B4008                 movq    8(%rax), %rax
0069 488945F0                 movq    %rax, -16(%rbp)

                .L3:

006d 488B45F0                 movq    -16(%rbp), %rax
0071 488B4008                 movq    8(%rax), %rax
0075 4885C0                   testq   %rax, %rax
0078 75E7                     jne     .L4

                .L2:

007a B8000000                 movl    $0, %eax
     00

007f C9                       leave
                        .cfi_def_cfa 7, 8
0080 C3                       ret
                        .cfi_endproc

                .LFE0:

                .Letext0:

// the same code is written in C language as well - just for better understanding

//#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
//#include <string.h>
// #include <conio.h>
#include <malloc.h>

/* I need to construct a dynamically singly linked
list using Mips Assembly. I would like for the user
to be able to enter integer values for each node and
the program allocate memory and assign the value
to the next node in the linked list. Could someone
show me how this would be done with lots of
comments so I understand what exactly is going on?
Thanks!
*/
// what we have just done below?
// declared a structure tag called vertex ( vertex = node in a linked list)
// the connection between nodes are vertices ( = plural of vertex) are done by arcs, links, or edges
// int data is simply a data of type integer - a variable to store actual key value of every node or vertex
// the tricky and challenging line to understan is:
//    struct vertex *nextPtr;
// we have made the recursive declaration for the data type struct ( = structure)
// which means the nextPtr ( = next Pointer) is again a variable of type structure tag vertex
// hence the concept of linked list will happen

struct vertex {
   int data;
   struct vertex *nextPtr;
};

/*
typedef struct vertex VERTEX;
VERTEX *headNode, *firstNode, *tempNode = 0;
int counter = 0;
int option = 1;
firstNode = 0;

*/
// VERTEX = node in a tree or a graph and also in our singly linked list
int main()
{

/*

while (option)   {
   headNode = (VERTEX *) malloc ( sizeof(VERTEX)):
   // allocate the memory = malloc for the size of the node
} // end while

*/
// time to create the first vertex or node of our list
struct vertex *rootNode;

// the root node must point at the begining or head of the struct tag vertex
rootNode = (struct vertex *) malloc ( sizeof ( struct vertex));

// at the begining the next will point to the ground = null, later when new nodes are added, the next pointer will get updated
rootNode->nextPtr = 0;
// now let us get the data from the user and put them as node value for each node
int data;
printf("\n Enter the data for the nodes of singly linked list please: ");
scanf("%d", &data);
rootNode->data = data;
// now we have to update the next pointer
// other wise the link may look broken
// hence we need a temperory (temp) tracker node
struct vertex *tempTrackerNode;
// this will keep track where we are exactly in the linked list
// for example if we had entered 100 data, the temp Tracker Node may point to node 45 when we are at node 45
// it will point to node 46 when we traverse to the right once
// unfortunately we can only travel ( traverse) in one direction as it is not a doubly linked list
// it is just a very basic singly linked list
// there are great stalwarts (Heroes) like circular linked lists
// which are much more powerful and intersting than the primitive singly linkedlists!!
// any way, back to the question, ......
// we have declared the tracker node
// now point it to the root in the list
tempTrackerNode = rootNode;
if ( tempTrackerNode != 0 ) // the list is not empty
   while ( tempTrackerNode -> nextPtr != 0 ) // while the list is not empty, keep looping
       tempTrackerNode = tempTrackerNode -> nextPtr;
   // end while
// end if

return 0; // exit
} // end of main()