C++ Questions: 1. How many bytes are required to store N data items in each of t

Question

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?

Explanation / Answer

The answers are as follows:

1. Items take D bytes and pointer takes P bytes

   In case of array based list = N * D bytes
   In case of linked list = N*(D + P) bytes
   In case of double liked list = N * (D + 2P) bytes

2. The counter will hold the count of how many times the item is looked into.This number will be stored along with each item. Once this counter data is there, we can sort the items based on that. Once sorted to look up an item we don't need to traverse the whole list because if we know the counter value for that item, it will be accessed very easily.May be we can store these couters pointing to certain items (number of items can be more than one as it is possible that more than two items will have same count. But still searching this arrangement will be better than just the simple list of items.

3.   Comparison of complexity:

     In array :
                Searching is of O(n)(unsorted array, each item needs to be compared). Insertion at the end is O(1).
                Insertion in the middle O(n)(shifting the elements to the right)
                Removing the element is O(n).(shifting the elements to the left)
                Accessing the element is of O(1) with a given index.
                Modifying an item is of O(1)

     In linked list :
                Searching is of O(n)(unsorted list, each item needs to be compared).
                Insertion in the middle O(n)(reaching the position to insert we need to traverse the list)
                Removing the element is O(n).(reaching the element to be removed ,we need to traverse the list)
                Accessing the element is of O(n)(reaching the element to be removed ,we need to traverse the list).
                Modifying an item is of O(n) (reaching the element to be modified ,we need to traverse the list)

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 (array based list because we need to access the elements randomly and the size is known)
     b.      Class roster (linked list because size may not be known)
     c.      A table when many inserts and deletes are involved (Array as insertion and deletion is easy as compared to linked list)
     d.      A collection when you have no clue regarding how big the list will become. (Linked list as size is not known)

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

Plain linked list stores the data sequentially but accessing the elements randomly becomes easy. If we need to access 10th element we just need to add the address to the first item to access the 10th element but in case of linked list we need to traverse the list as per the links to reach the 10th element.Also insertion and deletion needs more effort as compared to linked list. Mostly plain linked list will be applicable when we know the size otherwise linked list are more favorable.In case the size increasses, plain linked list will need a new allocation and value needs to be copied but in case of linked list we just need to create a node and link it appropriately.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.