Question

If the items in a list are floats taking 8 memory locations each, compare the amount of space required altogether if (a) the list is kept contiguously in an array 80 percent full (b) the list is kept contiguously in an array 60 percent full and (c) the list is kept as a linked list where the pointers take two memory locations each

Answer 1

Let us consider an array of maximum size 100. Then

a) The list which is 85% full will take 400*85 = 34000 memory locations to store defined values. But the net size altogether will be 100*400 = 40000 memory loactions, since the rest 15 undefined values will also exist and take up memory since the size of the array is fixed.

b) The list which is 60% full will take 400*60 = 24000 memory locations to store defined values. But the net size altogether will be 100*400 = 40000 memory loactions, since the rest 40 undefined values will also exist and take up memory since the size of the array is fixed.

c) If the list is kept as a linked list where the pointers take two mwmory locations each, then 2 pointers will be required per Node in a linked list. Thus the net size of each node in a linked list will be 400+2+2, (here size of each pointer is 2). So for n elements in the list, the memory required is non-contiguous and will be of net size (n*404)

Thus we can see from the above comparison that in an array type list, the size required to store is constant and is always equal to the size of the array no matter what the size of the list is. But in a linked list type list, the size required to store the list increases linearly with the size of the list.