Quiz 3

CS18

20 pts., Apr. 29

1. Compare and contrast pointer-based and array-based implementations of a linked list with respect to:
   1. The amount of memory needed to store a list.

      More memory is required to store a list using an array implementation, due to the static nature of an array and the requirement that large lists be capable of being stored. On the other hand, the pointer associated with each item of a pointer-based list represents overhead.

   2. How much work is required to insert an item at the beginning of a list, as a function of the number of items on the list, n.

      For a pointer-based list, the amount of work is constant --- O(1). For an array-based list, the work is proportional to the length of the list --- O( n). This is because each of the items in the list must be shifted one position in the array.

   3. How much work is required to insert an item at the end of a list, as a function of the number of items on the list, n.

      For a pointer-based list, the amount of work is O( n), because the entire list must be traversed to locate its end. For an array-based list, the amount of work is O(1). The end of the list can easily be determined from the data member holding the number of items in the list and the new item simply appended onto the array with no need for shifting any data.