Beginning Algorithms (2006)
.pdf
Chapter 3
// expected
}
try { list.delete(0);
fail();
}catch (IndexOutOfBoundsException e) {
//expected
}
}
You’ve tested what happens when you delete by position, but what about deleting by value? Deleting by value is not as straightforward as deleting by index — as you know, a list may contain the same value more than once, so you also need to ensure that in the event that there are duplicates, deleting by value only removes the first occurrence each time it is called:
public void testDeleteByValue() { List list = createList();
list.add(VALUE_A); list.add(VALUE_B); list.add(VALUE_A);
assertEquals(3, list.size()); assertSame(VALUE_A, list.get(0)); assertSame(VALUE_B, list.get(1)); assertSame(VALUE_A, list.get(2));
assertTrue(list.delete(VALUE_A));
assertEquals(2, list.size()); assertSame(VALUE_B, list.get(0));
assertSame(VALUE_A, list.get(1));
assertTrue(list.delete(VALUE_A));
assertEquals(1, list.size()); assertSame(VALUE_B, list.get(0));
assertFalse(list.delete(VALUE_C));
assertEquals(1, list.size()); assertSame(VALUE_B, list.get(0));
assertTrue(list.delete(VALUE_B));
assertEquals(0, list.size());
}
How It Works
The first four tests exercise the basic functionality of deleting a specific element. Deletion is the inverse of insertion, so you can expect that when an element is deleted, the size of the list will decrease by one and that any elements to the right of the deleted element will shift left by one. The contract for “delete by index” also states that it must return the value just deleted, so this is also tested.
54
Lists
The method testDeleteOutOfBounds() — as with all the bounds-checking tests — attempts to access the list with an invalid position: first using a negative position, and then using a position that is too big. Each time, you expect an IndexOutOfBoundsException to be thrown to indicate an application programming error.
The method testDeleteByValue() ensures that you can delete a value from a list without knowing its exact location. The test inserts three values into the list, two of which are duplicates of one another. It then removes one of the duplicate values and ensures the other is still contained within the list. The same value is used again to ensure that the second occurrence is removed. Next, it attempts to delete a value that doesn’t exist. This should have no effect on the list. Finally, it deletes the last known remaining value, leaving the list empty. Each time, you have checked that the value returned from delete is correct: Deleting a value that does exists should return true; and deleting an unknown value should return false.
Try It Out |
Testing Iteration |
One of the most difficult parts of a list implementation to get right is iteration. Recall that the List interface extends the Iterable interface (from Chapter 2), requiring implementations to provide an iterator over the contents.
You will need to test three general scenarios: iteration over an empty list, iteration forward from the start, and iteration backward from the end.
Start by testing the behavior when iterating over an empty list:
public void testEmptyIteration() { List list = createList();
Iterator iterator = list.iterator();
assertTrue(iterator.isDone());
try { iterator.current(); fail();
} catch (IteratorOutOfBoundsException e) { // expected
}
}
Next you test forward iteration from the beginning of the list:
public void testForwardIteration() { List list = createList();
list.add(VALUE_A); list.add(VALUE_B);
list.add(VALUE_C);
Iterator iterator = list.iterator();
iterator.first();
55
Chapter 3
assertFalse(iterator.isDone()); assertSame(VALUE_A, iterator.current());
iterator.next();
assertFalse(iterator.isDone()); assertSame(VALUE_B, iterator.current());
iterator.next();
assertFalse(iterator.isDone()); assertSame(VALUE_C, iterator.current());
iterator.next();
assertTrue(iterator.isDone()); try {
iterator.current();
fail();
}catch (IteratorOutOfBoundsException e) {
//expected
}
}
Finally, you test reverse iteration beginning with the last element in the list:
public void testReverseIteration() { List list = createList();
list.add(VALUE_A); list.add(VALUE_B); list.add(VALUE_C);
Iterator iterator = list.iterator();
iterator.last();
assertFalse(iterator.isDone()); assertSame(VALUE_C, iterator.current());
iterator.previous();
assertFalse(iterator.isDone());
assertSame(VALUE_B, iterator.current());
iterator.previous();
assertFalse(iterator.isDone()); assertSame(VALUE_A, iterator.current());
iterator.previous();
assertTrue(iterator.isDone()); try {
iterator.current();
fail();
} catch (IteratorOutOfBoundsException e) { // expected
}
}
56
Lists
How It Works
When iterating over an empty list, you expect isDone() to always return true, indicating that there are no more elements.
The method testForwardIteration() creates a list containing three values and obtains an iterator. It then calls first() to start at the first element of the list and makes successive calls to next() and current(), checking that the values are returned in the expected order. The method isDone() should only return true after all of the elements have been visited.
Testing reverse iteration follows the same steps as testing forward iteration, except that you start at the last element and work your way backward by calling previous() instead of next().
In all cases, once the iterator has completed — isDone() returns true — an attempt is made to access the iterator by calling current(). This should throw an IteratorOutOfBoundsException.
Try It Out |
Testing Methods for Finding Values |
Lists enable searching for values via the indexOf() and contains() methods.
The indexOf() method returns the position (0, 1, 2, . . .) of the value if found, and -1 if not found. In the event that a list contains duplicate values, indexOf() should only ever find the first occurrence:
public void testIndexOf() { List list = createList();
list.add(VALUE_A); list.add(VALUE_B); list.add(VALUE_A);
assertEquals(0, list.indexOf(VALUE_A)); assertEquals(1, list.indexOf(VALUE_B)); assertEquals(-1, list.indexOf(VALUE_C));
}
The method contains() returns true if a value is found; otherwise, it returns false:
public void testContains() { List list = createList();
list.add(VALUE_A); list.add(VALUE_B); list.add(VALUE_A);
assertTrue(list.contains(VALUE_A)); assertTrue(list.contains(VALUE_B)); assertFalse(list.contains(VALUE_C));
}
57
Chapter 3
How It Works
Both tests populate a list with three values, one of which is a duplicate.
The method testIndexOf() then checks that the correct position is returned for existing values — A and B — and that -1 is returned for a non-existing value — C. In the case of the duplicate value, the position of the first occurrence should be returned.
The method testContains() checks that contains() returns true for existing values and false for nonexisting ones.
Try It Out |
Testing What Happens When a List Is Cleared |
Last but not least, you will test what happens when you reset a list by calling clear(). The list should be empty and its size reset to 0:
public void testClear() { List list = createList();
list.add(VALUE_A); list.add(VALUE_B); list.add(VALUE_C);
assertFalse(list.isEmpty()); assertEquals(3, list.size());
list.clear();
assertTrue(list.isEmpty()); assertEquals(0, list.size());
}
How It Works
The method testClear() populates the list with three values and then calls clear, after which the list is checked to ensure it no longer contains any values.
Implementing Lists
By now you should have a thorough understanding of list functionality. Having codified the expected behavior as tests, you can easily determine whether your implementations are working as expected. You can now dive into some well-earned production coding.
There are many ways to implement a list, but the two most common, and the two presented here, are an array-based implementation and a so-called linked list. As the name suggests, an array list uses an array to hold the values. A linked list, conversely, is a chain of elements in which each item has a reference (or link) to the next (and optionally previous) element.
You will begin with the simplest case, the array list, followed later by the more sophisticated linked list. Both have characteristics that make them more or less useful depending on the requirements of your
58
Lists
application. For this reason, you will consider the specific pros and cons of each along with the explanation of the code.
In every case, we will make some assumptions about the type of data that can be stored within a list. Specifically, we will not allow lists to contain null values. Not allowing null values simplifies the code by removing many boundary conditions that tend to arise when dealing with null values. This restriction shouldn’t cause you much concern because in most business applications, lists rarely, if ever, contain null values.
An Array List
As the name suggests, an array list uses an array as the underlying mechanism for storing elements. Because of this, the fact that you can index directly into arrays makes implementing access to elements almost trivial. It also makes an array list the fastest implementation for indexed and sequential access.
The downside to using an array is that each time you insert a new element, you need to shift any elements in higher positions one place to the right by physically copying them. Similarly, when deleting an existing element, you need to shift any objects in higher positions one place to the left to fill the gap left by the deleted element.
Additionally, because arrays are fixed in size, anytime you need to increase the size of the list, you also need to reallocate a new array and copy the contents over. This clearly affects the performance of insertion and deletion. For the most part, however, an array list is a good starting point when first moving away from simple arrays to using richer data structures such as lists.
Try It Out |
Creating the Test Class |
First you need to define the test cases to ensure that your implementation is correct. Start by creating a class named ArrayListTest that extends the AbstractListTestCase class you created earlier:
package com.wrox.algorithms.lists;
public class ArrayListTest extends AbstractListTestCase { protected List createList() {
return new ArrayList();
}
public void testResizeBeyondInitialCapacity() { List list = new ArrayList(1);
list.add(VALUE_A); list.add(VALUE_A); list.add(VALUE_A);
assertEquals(3, list.size()); |
|
|
assertSame(VALUE_A, list.get(0)); |
|
|
assertSame(VALUE_A, |
list.get(1)); |
|
assertSame(VALUE_A, |
list.get(2)); |
} |
public void testDeleteFromLastElementInArray() {
59
Chapter 3
List list = new ArrayList(1);
list.add(new Object());
list.delete(0);
}
}
How It Works
You already did most of the hard work when you created the AbstractListTestCase class earlier. By extending this class, you necessarily inherited all of the tests. Therefore, the only other one that was needed was to implement the createList() method in order to return an instance of an ArrayList class, which will be used by the tests. In addition to the standard tests, a couple of extras are needed due to the way array lists work internally.
The first method, testResizeBeyondInitialCapacity(), is needed because as the size of an array list increases, the underlying array is resized to accommodate the extra elements. When this happens, you want to make sure that the contents are correctly copied. The test starts by constructing an array list with an initial capacity of one. Three values are then added. This causes the underlying array to grow accordingly. As a consequence, the elements are copied from the original array to a new, larger one. The test then ensures that the size and contents have been copied successfully.
As the name implies, the second test method, testDeleteFromLastElementInArray(), checks what happens when you delete the last element in the list. As you will see in the code a bit later, this boundary condition can lead to ArrayIndexOutOfBoundsExceptions if not handled correctly.
Try It Out |
Creating the ArrayList Class |
Now that you have created the test cases, you can safely proceed to creating the array list implementation. Start by creating the ArrayList class as shown here:
package com.wrox.algorithms.lists;
import com.wrox.algorithms.iteration.ArrayIterator; import com.wrox.algorithms.iteration.Iterator;
public class ArrayList implements List {
private static final int DEFAULT_INITIAL_CAPACITY = 16;
private final int _initialCapacity; private Object[] _array;
private int _size;
public ArrayList() { this(DEFAULT_INITIAL_CAPACITY);
}
public ArrayList(int initialCapacity) {
assert initialCapacity > 0 : “initialCapacity must be > 0”;
_initialCapacity = initialCapacity;
60
Lists
clear();
}
public void clear() {
_array = new Object[_initialCapacity]; _size = 0;
}
...
}
How It Works
The class itself is quite simple. All it needs is a few fields and, of course, to implement the List interface. You have created a field to hold the array of elements and a separate field to hold the size of the list. Be aware that the size of the list is not always the same as the size of the array: The array will almost always have “spare” capacity at the end, so the length of the array doesn’t necessarily match the number of elements stored in the list.
There are also two constructors. The first is really a convenience — it calls the second with some default values. The second constructor takes as its only argument the size of the initial array, which is validated and saved before calling clear() to initialize the element array and reset the size of the list.
(Technically, you could allow a value of 0, but that would require resizing the array the first time you inserted a value. Instead, force the caller to pass a value that is at least 1.)
Try It Out |
Methods for Inserting and Adding Values |
The first method you will implement inserts values into a list at a specified position:
public void insert(int index, Object value) throws IndexOutOfBoundsException {
assert value != null : “value can’t be null”;
if (index < 0 || index > _size) {
throw new IndexOutOfBoundsException();
}
ensureCapacity(_size + 1);
System.arraycopy(_array, index, _array, index + 1, _size - index); _array[index] = value;
++_size;
}
private void ensureCapacity(int capacity) { assert capacity > 0 : “capacity must be > 0”;
if (_array.length < capacity) {
Object[] copy = new Object[capacity + capacity / 2]; System.arraycopy(_array, 0, copy, 0, _size);
_array = copy;
}
}
61
Chapter 3
Once you can insert a value, adding a value to the end of the list follows naturally:
public void add(Object value) { insert(_size, value);
}
How It Works
The insert() method starts by validating the input. In the first instance, you need to check for null values, as these are explicitly not allowed. Second, as you may recall from the test cases, insert() is required to throw an IndexOutOfBoundsException if any attempt is made to insert before the first element or further than one beyond the last element of the list.
Next, because arrays are fixed in size but lists are not, it is also necessary to ensure that the underlying array has enough capacity to hold the new value. For example, say you had an array that was of length five and you wanted to add a sixth element. The array clearly doesn’t have enough space, but it won’t magically resize for you either, thus, the call to ensureCapacity() ensures that there is enough room in the array to accommodate another value. Once the call to ensureCapacity() returns, you know you have enough space, so you can safely shift the existing elements to the right by one position to make room for the new value. Finally, you store the value into the appropriate element, remembering to increase the size of the list.
The method ensureCapacity() handles the dynamic resizing of the underlying array. Anytime it detects that the underlying array is too small, a new array is allocated, the contents are copied over, and the old array is discarded, freeing it up for garbage collection. You could use any number of strategies for determining when and how big to allocate the new array, but in this particular example, the size of the array is increased by an additional 50 percent over what is actually required. This provides a kind of safety net that ensures the list doesn’t spend most of its time allocating new arrays and copying the values across.
The add() method simply delegates to insert, passing the size of the list as the insertion point, thereby ensuring that the new value is added to the end.
Try It Out |
Methods for Storing and Retrieving Values by Position |
Now you will create the two methods get() and set(), used for storing and retrieving values. Because this particular implementation is based on arrays, access to the contained values is almost trivial:
public Object get(int index) throws IndexOutOfBoundsException { checkOutOfBounds(index);
return _array[index];
}
public Object set(int index, Object value)
throws IndexOutOfBoundsException { assert value != null : “value can’t be null”; checkOutOfBounds(index);
Object oldValue = _array[index]; _array[index] = value;
return oldValue;
62
Lists
}
private void checkOutOfBounds(int index) { if (isOutOfBounds(index)) {
throw new IndexOutOfBoundsException();
}
}
private boolean isOutOfBounds(int index) { return index < 0 || index >= _size;
}
How It Works
After first checking that the requested position is valid, the get() method returns the value contained at the element for the specified index, while the set() method replaces whatever value was already there. Additionally, set() takes a copy of the value that was originally stored at the specified position before overwriting it. The original value is then returned to the caller.
As you can probably tell, an array list performs extremely well for indexed access. In fact, while indexed access to a list is generally considered to be O(1), array lists come about as close as you will get to delivering on that promise with identical best, worst, and average case performance.
Try It Out |
Methods for Finding Values |
As indicated in the discussion on get() and set(), lists are ideal for storing values in known positions. This makes them perfect for certain types of sorting (see Chapters 6 and 7) and searching (see Chapter 9). If, however, you want to determine the position of a specific value within an unsorted list, you will have to make do with the relatively crude but straightforward method of linear searching. The indexOf() method enables you to find the position of a specific value within a list. If the value is found, its position is returned; otherwise, -1 is returned to indicate the value doesn’t exist:
public int indexOf(Object value) {
assert value != null : “value can’t be null”;
for (int i = 0; i < _size; ++i) { if (value.equals(_array[i])) {
return i;
}
}
return -1;
}
Having provided a mechanism for searching the list via indexOf(), you can proceed to implement contains():
public boolean contains(Object value) { return indexOf(value) != -1;
}
63