Question

ch 6

ex 14

lists plus, c++ plus data structures, linked list understanding

Problem:

Use the linked lists contained in the array pictures in figure 6.19 (see pics) to amswer the following questions :

14. Use the linked lists contained in the array pictured in Figure 6.19 to answer the following questions: a. What elements are in the list pointed to by listi? b. What elements are in the list pointed to by list2? c. What array positions (indexes) are part of the free space list? d. What would the array look like after the deletion of Nell from the first list? e. What would the array look like after the insertion of Anne into the second list? Assume that before the insertion, the array is as pictured in Figure 6.19.

please show some explanation / work so that i can grasp and retain this information

Thank you so much for your time!

Answer 1

1. We have been asked about elements in list1. as in the figure, list1 contains value 0, thius means list1 starts with index [0] of nodes.

So, the first element of list1 is the element stored in .info corresponding to [0] i.e. John

.next corresponding to John contains 4, this means the next element of list is stored at index [4] i.e. Nell

.next corresponding to Nell contains 8, this means the next element of list is stored at index [8] i.e. Susan

.next corresponding to Susan contains 9, this means the next element of list is stored at index [9] i.e. Sussane

.next corresponding to Sussane is NUL, so, list1 terminates here.

so, list1 = [John Nell Susan Sussane]

2. Similarly, we can find out elements in list2 also

the first element of list2 is the element stored in .info corresponding to [1] i.e. Mark

.next corresponding to mark contains 5, this means the next element of list is stored at index [5] i.e. Naomi

.next corresponding to Naomi contains 6, this means the next element of list is stored at index [6] i.e. Robert

.next corresponding to Robert is NUL, so, list2 terminates here.

So, list2 = [Mark Naomi Robert]

3. free starts with 7, .next of 7 contains 2, .next of 2 contains 3 and .next of 3 is Nul

So, index 7, 2 and 3 are part of free list

4. if we delete Nell from the list1, .next of John will be replaced by .next of Nell and index of Nell will be added to free list i.e. 4 will be added to .next of index [3] and .next of index [4] will be set to NUL.

Here is final List

node	.info	.next
[0]	John	8
[1]	Mark	5
[2]		3
[3]		4
[4]		NUL
[5]	Naomi	6
[6]	Robert	NUL
[7]		2
[8]	Susan	9
[9]	Sussane	NUL

5. When we add an element to a list, it is added at the end To add a new name, we need to take a node from free, write new value to this node and set .next of the last element of list to index of this node and further set .next of index corresponding to this node to NUL.

In our case, we take the last node of the free list i.e. 3 and do the following

write Anne to .info of index [3]

set .next of [6] to 3

set .next of index [2] to NUL

Here is the final list

node	.info	.next
[0]	John	4
[1]	Mark	5
[2]		NUL
[3]	Anne	NUL
[4]	Nell	8
[5]	Naomi	6
[6]	Robert	3
[7]		2
[8]	Susan	9
[9]	Sussane	NUL