(i) f(n) nlogn (ii) f(n) 3n +2n + 1 Q2-20 pts) Consider a scenario wherein 100,0
ID: 3751043 • Letter: #
Question
(i) f(n) nlogn (ii) f(n) 3n +2n + 1 Q2-20 pts) Consider a scenario wherein 100,000 objects (each of size: 40 bytes) need to be stored in a List. (a) Determine the memory (in bytes) that would need to be allocated to the List if it were to be implemented as a: (i) Dynamic array; (ii) Singly Linked List and (ii) Doubly Linked List (b) If we were to do frequent insert operations that would insert elements to the beginning of the list, which implementation (dynamic arrays or Linked List) would you prefer and why?Explanation / Answer
Answer (a):
(i) For a dynamic array, we need a pointer(4 bytes) to point to the beginning of the array. Now each of the 100,000 objects has a memory of 40 bytes. Therefore, the total memory allocated is, 4 + 40 * 100000 = 4000000 + 4 = 4000004 bytes.
(ii) A Singly Linked List has 100000 nodes each comprising of one object(40 bytes) and one next pointer(4 bytes). There is also a pointer to the start of the linked list. Therefore, total memory allocated is, 4 + (40 + 4) * 100000 = 4400004 bytes.
(iii) A Double Linked List has 100000 nodes each comprising of one object(40 bytes) and one next pointer(4 bytes) and one prev pointer(4 bytes). There is also a pointer to the start of the linked list. Therefore, total memory allocated is, 4 + (40 + 8) * 100000 = 4800004 bytes.
Here it is assumed that a pointer variable occupies 4 bytes of memory. This value may vary from one computer system to another. For a different value of pointer size, the approach is the same as described above.
Answer (b):
In an array if we are to insert at the beginning, we have to move every element to the next position to make space in the 0th location. Thus this involves displacing(moving or swapping) N objects where N is initial no. of objects. This can get very costly for bigger objects. Therefore, this is not the best implementation for the given requirement.
In a linked list, inserting at the front involves just ~3 steps(based on your implementation it can be reduced to 1) and this takes constant time and involves no heavy copy or move operations. Therefore, this is the best implementation for the given purpose.
The 3 steps involved in front insertion of linked list are, making a new node with new data in it, pointing its next to the current front node, pointing the front pointer to the new node.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.