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

10.4 Linked List Structures 309

* SUBROUTINE SCAN
*
* SCAN scans the linked list TREE from the left, putting out the characters in
* alphabetical order. The address of TREE is passed in X with the calling sequence
*
* LDX #TREE
* BSR SCAN
*
SCAN: CPX #0 ; If pointer is a "null" (0)
BEQ L ; Exit without doing anything
PSHX ; Save link
LDX 1, X ; Left successor link.into X
BSR SCAN ; Call this subroutine again
LDAA [ 0, SP ] ; Get character
JSR OUTCH ; Put out next character
PULX ; Pull pointer from stack
LDX 3 f X ; Move pointer to right successor into B
BRA SCAN ; Call this subroutine again
L: RTS

Figure 10.14. Subroutine SCAN Using Address Pointers

usually accesses one list-(row) after the list (row) above it was accessed. In a linked list,
one can use any link from one list to go to another list. By providing appropriate links
in the list, the programmer can easily implement an algorithm that requires going from
list to list in a particular order. Linked lists generally store addresses rather than index
numbers, to simplify the procedure and to avoid an artificial restriction on length. The
linked list above can be stored as in Figure 10.13, and the procedure in Figure 10.14 can
be used to read the list.
Compare the implementation of the tree structure above using a linked list with one
using a simple table where the nodes are put down successively by levels. Not only are
most offsets calculated to go from node to successor node, but gaps will be left in the
table where the tree has no successors, and testing for the end of the search will be
messy. Even constructing this table from the string will be difficult. However the linked
list program can be written in a simple and logical form, using the power of the data
structure to take care of many variations. In the example above, nodes that have no left
successor or nodes that have no right successor are handled the same way as nodes that
have two successors. While links can simplify the program, as we have just discussed,
additional links can speed up a program by permitting direct access to lists that are linked
via several link list-link list . . . -link list steps. Linked lists can simplify the program
as well as speed it up, depending on how the designer uses them.
This final section briefly introduced the linked list structures. These are very useful
in larger computers, although rarely seen in microcomputers, in our experience.
Nevertheless, they are well known to be useful in artificial intelligence applications so
that you may expect to see them used in the near future in robots and pattern recognition
devices. You should read further material on these powerful structures.