A linked list is a linear data structure consisting of a set of nodes.pdf

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 Next
CLEAR // AC Next (Next loop)
JUMP Loop
End HALT.

1. 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

2. ADDI Next // AC <--[Next] (load next address from pointer field)
STORE Next // AC--> Next (Next loop)
JUMP Loop
End HALT