Question: 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.
- 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.
- Compare the complexity of operations for array based lists and linked lists. Identify and explain the reasons for the differences.
- Which data structure (i.e., array based list or linked list) is the optimum one for following problems? Explain your reasoning.
- Read only look-up table
- Class roster
- A table when many inserts and deletes are involved
- A collection when you have no clue regarding how big the list will become
- 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?