A linked list is a linear data structure consisting of a set

A linked list is a linear data structure consisting of a set of nodes, where each one except the last one points to the next node in the list. (Appendix A provides more information about linked lists.) Suppose we have the set of 5 nodes shown in the illustration below. These nodes have been scrambled up and placed in a MARIE program as shown below. Write a MARIE program to traverse the list and print the data in order as stored in each node.

Solution

Address Label

(hex) JUMP start

00D Addr, Hex 0006 //Top of list pointer, address of node 1

00E Node2, Hex 0032 //Node data is the character 2.

00F Hex 0008 //address of node 3.

010 Node4, Hex 0034 //character \"4\".

011 Hex 000A //address of node 5

012 Node1, Hex 0031 //Character 1

013 Hex 0002 //address of node2

014 Node3 Hex 0033 //Character 3

015 Hex 0004 // addresss of node 4

016 Node5 Hex 0035 //Character 5

017 Hex 0000 //end of the list

Next Hex 0000 //pointer to next element

ONE Hex 0001 //one

Start LOAD Addr //LOAD LINK HEAD

STORE Next //

LOAD Next

Loop SKIPCOND 400 //if AC==0 - end of list reached

JUMP NextElem

JUMP End

NextElem CLEAR //Next is not null

ADDI Next // Load data value from current pointter to AC

OUTPUT // Display it

LOAD ONE // AC <-- 1

ADD Next // AC <--- Next+1 (pointer field address)

STORE Next // AC ---> Next

CLEAR // AC <---- 0

ADDI Next // AC <--[Next] (load next address from pointer field)

STORE Next // AC--> Next (Next loop)

JUMP Loop

End HALT