CHAP. 8] GRAPH THEORY 155
of pointers. Figure 8-1 is a schematic diagram of a linked list with six nodes. That is, each node is divided into
two parts: the first part contains the information of the element (e.g., NAME, ADDRESS,...), and the second
part, called thelink fieldornextpointer field, contains the address of the next node in the list. This pointer field
is indicated by an arrow drawn from one node to the next node in the list. There is also a variable pointer, called
START in Fig. 8-1, which gives the address of the first node in the list. Furthermore, the pointer field of the last
node contains an invalid address, called anull pointer, which indicates the end of the list.
Fig. 8-1 Linked list with 6 nodesOne main way of storing the original data pictured in Fig. 8-2, uses linked lists. Observe that there are separate
(sorted alphabetically) arrays for the customers and the salesmen. Also, there is a pointer array SLSM parallel
to CUSTOMER which gives the location of the salesman of a customer, hence operationAcan be performed
very easily and quickly. Furthermore, the list of customers of each salesman is a linked list as discussed above.
Specifically, there is a pointer array START parallel to SALESMAN which points to the first customer of a
salesman, and there is an array NEXT which points to the location of the next customer in the salesman’s list
(or containsa0toindicate the end of the list). This process is indicated by the arrows in Fig. 8-2 for the
salesman Ray.
Fig. 8-2OperationBcan now be performed easily and quickly; that is, one does not need to search through the list
of all customers in order to obtain the list of customers of a given salesman. Figure 8-3 gives such an algorithm
(which is written in pseudocode).
Stacks, Queues, and Priority Queues
There are data structures other than arrays and linked lists which will occur in our graph algorithms. These
structures, stacks, queues, and priority queues, are briefly described below.
(a) Stack:Astack, also called alast-in first-out(LIFO) system, is a linear list in which insertions and deletions
can take place only at one end, called the “top” of the list. This structure is similar in its operation to a stack
of dishes on a spring system, as pictured in Fig. 8-4(a). Note that new dishes are inserted only at the top of
the stack and dishes can be deleted only from the top of the stack.