Lists Implementation 2: Growing Array

Last time we looked at the specification of a generic List ADT, and one implementation that supports those operations. Now we'll see that the same ADT can be implemented completely differently; i.e., provide the same interface for working with data, but with different "guts" to make that happen. Why would we do that? There are efficiency trade offs between different implementations for different usage patterns. So we'll review how we talk about efficiency in CS.

• Growing array list implementation

All the code files for today: GrowingArray.java; ListTestArray.java.

Slides from class

Growing array list implementation

For a completely different way to implement the List interface, let's use an array. An array is a more primitive representation of an ordered set of elements, in that it has a fixed length that we have to specify when we create it, and we can't add/remove elements. (C and Matlab programmers are used to such arrays, though as with lists, Java indexes arrays starting at 0.). While linked lists require us to start at the beginning and proceed sequentially from an element to its next, arrays are "random access" — we can instantly get/set any element. (They are basically just one big chunk of memory, into which we index a given element by knowing the fixed size of each element. Array object types are specificied with square brackets, and to get/set elements, we give the index in square brackets. For example:

int[] numbers = new int[10];
for (int i=0; i<10; i++) {
  numbers[i] = i*2;
}

The basic picture is:

To belabor the point, an array of n elements has elements indexed from 0 to n–1, only. An array of n elements does not have an element with index n. Thus the 10 elements of our array are numbers[0], numbers[1], numbers[2], ..., numbers[9].

The code:

• We declare an array of ints named "numbers".
• We initialize it to actually be able to hold 10 ints. (Again, if we don't new, there will be a run-time error — try it so you'll recognize it.)
• We have a loop over each element in the array (0..9) and set its value. What's in the array now? (Again, if we go <= 10 rather than < 10 there will be a run-time error — try it so you'll recognize it.)

So how can an array be used to implement a list, which can grow? The trick is that when we run out of room, since we can't grow the array, we instead create a new one (say of double the size) and copy over the elements.

Our implementation: GrowingArray.java. We simply use the underlying array for get and set, and a loop for toString. In addition to the array, we keep a variable size that says how many elements are actually filled in. We can then compare that to the actual length of the array (array.length, a variable not a method) and allocate and copy over if needed.

Add and remove may also require some element shifting. If we are adding in the middle of the array, we need to shift things after it to the right by one index, in order to make room. Likewise, if we are removing in the middle of the array, we shift things after it to the left by one step, in order to fill in the hole it would leave behind. Note the order of the loops: from right to left for add vs. from left to right for remove. Step through it.