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

304 Chapter 10 Elementary Data Structures

preceded by a pull from the bottom. If the buffer for the shift register holds N bytes,
then, after N or more pushes, the bottom byte of the shift register is the first in among
the current bytes in the shift register, the next-to-bottom is the second in among the
current bytes, and so on. If all pushes into the shift register are from accumulator B, only
one macro and one pointer are needed to implement this data structure. (See the problems
at the end of the chapter.) Although these two sequential structures are more common
than the deque, we have focused on the deque in our discussion to illustrate the differences
between accessing these sequential structures' top and bottom with the 6812.
In this section we have studied the sequential structures that are commonly used in
microcomputers; the string and the variations of the powerful deque, the stack, queue, and
shift register. As you have seen, they are easy to implement on the 6812.

10.4 Linked List Structures

The last structure that we discuss is the powerful linked list structure. Because its careful
definition is rather tedious and it is not as widely used in microcomputer systems as the
structures discussed in the previous sections, we examine this structure in the context of
a concrete example, a data sorting problem. Suppose that we have a string of ASCII
letters, say,
t c x u a f b (12)

where we want to print the letters of the string in alphabetical order.
We will store this string of letters in a data structure called a tree, using a linked
list data structure to implement the tree. The reason that we do not want to store the
letters in consecutive bytes of memory as, say, a vector, but in a linked list
implementation of a tree, is that, stored as a vector, the time to find a particular letter
grows linearly with the number of letters in the string. If the letters were files of data,
searching for a particular file could take days if the number of files is large. Organized as
a linked list implementation of a tree, the search time grows logarithmically with the
number of files so that searching for that same file could be done in seconds. Large
collections of data are typically stored in some manner to improve the time to search
them, and the linked list implementation of a tree is a common way to do this.

Figure 10.8. Picture of the Tree Representing the String (12)