C++ Questions:

1. How many bytes are required to store N data items in each of these three structures: array based list, linked list, and doubly linked list? Assume that each pointer occupies P bytes, and each data item occupies D bytes.

2. Let us assume that you have implemented a look-up table. You decide to keep a counter along with each data item to the count number of times each item is looked up, and use the counters to improve the look-up speed by rearranging the order of the data items. How will you do that? Describe your high-level approach.

3. Compare the complexity of operations for array based lists and linked lists. Identify and explain the reasons for the differences.

4. Which data structure (i.e., array based list or linked list) is the optimum one for following problems? Explain your reasoning.

a. Read only look-up table

b. Class roster

c. A table when many inserts and deletes are involved

d. A collection when you have no clue regarding how big the list will become

5. What are the benefits/costs of linked lists with head and tail nodes over plain linked lists? If you have to implement a linked list, will you consider this form? Why/Why not?