Page 331 - Introduction to Microcontrollers Architecture, Programming, and Interfacing of The Motorola 68HC12

308 Chapter 10 Elementary Data Structures

* SUBROUTINE SCAN scans the linked list TREE from the left, putting out the
* characters in alphabetical order. The calling sequence below scans TREE
*
* LDX #TREE
* CLRB ; Put LINK to 0
* BSR SCAN
*
SCAN: CMPB #$FF
BEQ L
LDAA #3
MUL
PSHB ; Save 3 * B on stack
INCB ; 3 * (B) + 1 into B
LDAB B, X ; Left successor link into B
BSR SCAN
LDAA 0, SP ; Recover 3 * B
LDAA A, X
JSR DUTCH ; Put out next character
PULB ; Recover 3 * B from stack, remove from stack
ADDB #2
LDAB B, X ; Link to right successor into B
BRA SCAN
L: RTS

Figure 10.12. Subroutine SCAN Using Indexes

The main idea of linked lists is that the list generally has an element that is the
number of another list, or it has several elements that are numbers of other lists. The
number, or link, allows the program to go from one list to a related list, such as the list
representing a node to the list representing a successor of that node, by loading a register
with the link element. The register is used to access the list. This is contrasted to a
sequential search of consecutive rows of a table, which is a vector of lists. In a table, one

Location Letter Left Right
0x800 t 0x803 0x806
0x803 c OxSOc OxSOf
0x806 X 0x809 0
0x809 u 0 0
0x8 Oc a 0 0x812
OxSOf f 0 0
0x812 b 0 0

Figure 10.13. Linked List Data Structure for SCAN