Here is a sketch of how we might implement the BiList interface using arrays.
If we run out of room we can resize the array used to store the list
elements. If we double the size of the array at each resizing, then
the average number of times an element is copied due to resizing is
approximately 1. To prove this, let the initial size of the array be
I, and suppose that the final size of the array is
N, and there were k resizes. Then
Using some summation facts we can show that the total number of array element copy operations is exactly N - I. Thus the average number of copy operations per element in the final array is (N-I)/N which is always less than 1, and approaches 1 in the limit as N gets much larger than I (i.e. as the number of resizings gets large). We say that the amortized cost of copying array elements is (bounded by a) constant. The strategy of doubling the size of the array on each resize operation appears to be an efficient one.
Exercise: Suppose that instead of doubling the array size, we increased it by some constant amount. That is, after kresizings, the size of the array is for some constant J. What would the amortized cost of element copying be then?