***DATA STRUCTURES AND ALGORITHMS USING JAVA**By: William McAllister - Chapter 4: Linked Lists and Iterators****

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.

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.

f) Add the node locations to your answer to part (e), as shown in 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.

h. ***** 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.)

Chapter in the Lases and inerators Linked Lists of them share the There are several opes of linked lists, but all one other mode with , overy made in the structure has at least one field, of another made with the captain of the unique in Each node's location is stored in at lea first nodeif there is one). data set that sometimes Figure 4illustrates .2 these two characteristics usins. Hamas. and G. Rather than storing the nodes addressed in a Sea contain the addresses of other nodes. Consider that either the first left) or the second Figure 4.2b, we can follow ning at Node T) to locate all the other modes. For examp second link fields, Node G, stored at location gates stored at location 20, and finally Node B, stored at this traveling through the other a determined in way (by in an assumption implicit in a node references contiguous memory the constraint of locate array elements. Link fields free us from sequential nature of accessing linked lists through the link fields and NodeT to be the starting Notes encountered me. This is location 2. Since the main we no longer the net to reduces RAM Nodes information 20 NodeB's information 332 Node Ts information 20 649 Node G's information 332 Figure 4.2a A Linked List with Two Link Fields