10. A data set consisting of four information nodes A, X, P, and C, is stored in a singly linked list. A field in each node named next is used to link them together. The memory locations of the nodes are: 200, 30, 500, and 60, respectively. The memory cell h is the list header. The nodes are to be stored in alphabetic order in the linked list.

a) Draw a picture, similar to Figure 4.2a, showing the relative position of the nodes in main memory.

FIGURE 4.2a

b) Add arrows to the picture drawn in part (a) to show the ordering of the nodes starting at the list header (see Figure 4.3).

c) Give the contents of the list header.

d) Give the contents of the next field of each node.

e) Draw the standard depiction (see Figure 4.4) of the four nodes in the linked list.

FIGURE 4.4

f) Add the node locations to your answer to part (e), as shown in Figure 4.5.

FIGURE 4.5

g) Assuming a field named back, was added to each node to order them in reverse alphabetic order, give the contents of this field for each node.

Draw the implementation level depiction (see Figure 4.9) of the nodes described in the previous example. (Make up the memory location of the dummy node and the locations of the other linked nodes that are used to implement the structure.)

RAM Node X's information 973 20 332 Node B's information nul 332 l nul1 Node Ts information 649 20 973 Node G's information 332 20 973 RAM Node X's information 973 20 332 Node B's information nul 332 l nul1 Node Ts information 649 20 973 Node G's information 332 20 973