This question compares the space usage for two versions of a stack, one using a

Question

This question compares the space usage for two versions of a stack, one using a linked list in which each node holds a reference to an object and a pointer to the next node, and the other using the Java ArrayList (array cells holding references to objects). Suppose the stack holds 1000 objects at its peak usage. How many bytes of space are used (a) by the linked list implementation, and (b) by the ArrayList implementation, at peak usage? Use the following data: A reference/pointer to an object uses 4 bytes of space. The ArrayList starts with an initial capacity of 10, and doubles each time it is resized. The linked list implementation keeps a front reference/pointer to the first node Both implementations keep an integer size field (4 bytes) The ArrayList implementation keeps an integer capacity field (4 bytes)

Explanation / Answer

Considering a 32-bit compiler,

For

a) size of each node = size of pointer to next node + size of pointer to object

total size = total no of nodes * (size of each node + size of each object it points)

=1000 * ((4+4) + 4 ) = 12000 bytes

For

b) size of each cell = size of pointer to object

As per the question for containing references to 1000 objects, the arraylist will get resized in this form 10,20,40,80,160,320,640,1280. So it will have 1000 cells used for referencing and rest 280 cells(each of integer size i.e. 4bytes) will remain unused.

Total size used = no of used cells * (size of each pointer to object + size of each object it points) + no of unused cells * size capacity of cell

= 1000 * (4 + 4) + 280 * 4

= 9120 bytes

Thanks,

SPR.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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