Beginning Algorithms (2006)

Chapter 3

major difference between arrays and lists, however, is that whereas an array is fixed in size, lists can resize — growing and shrinking — as necessary.

As a minimum, a list supports the four core operations described in Table 3-1.

Table 3-1: Core Operations on a List

Operation Description

insert	Inserts a value into a list at a specified position (0, 1, 2, . . .). The size of the list
	will increase by one. Throws IndexOutOfBoundsException if the specified
	position is outside the range (0 <= index <= size()).
delete	Deletes the value at a specified position (0, 1, 2, . . .) in a list and returns what-
	ever value was contained therein. The size of the list will decrease by one.
	Throws IndexOutOfBoundsException if the specified position is outside the
	range (0 <= index < size()).
get	Obtains the value at a specified position (0, 1, 2, . . .) in the list. Throws
	IndexOutOfBoundsException if the specified position is outside the range
	(0 <= index < size()).
size	Obtains the number of elements in the list.

These operations are all that is absolutely necessary for accessing a list. That said, however, if the operations listed were the only ones available, then you would find yourself copying and pasting the same code repeatedly as you discovered more sophisticated ways to access your lists. For example, there is no specific method for changing the value of an existing element (as you might do with an array), although you can achieve the same thing by first deleting the element and then inserting a new one in its place. To prevent the unnecessary duplication of logic that comes from repeatedly using such a simple interface, you can choose to encapsulate this common behavior inside the list itself by implementing some convenience operations, as described in Table 3-2.

Table 3-2: Convenience Operations on a List

Operation	Description
set	Sets the value at a specified position (0, 1, 2,. . .) in the list. Returns the value
	originally at the specified position. Throws IndexOutOfBoundsException if
	the specified position is outside the range (0 <= index < size()).
add	Adds a value to the end of the list. The size of the list will increase by one.
delete	Deletes the first occurrence of a specified value from a list. The size of the list
	will decrease by one if the value is found. Returns true if the value is found,
	or false if the value doesn’t exist.
contains	Determines whether a specified value is contained within a list.
indexOf	Obtains the position (0, 1, 2,. . .) of the first occurrence of a specified value
	within a list. Returns -1 if the value is not found. Equality is determined by
	calling the value’s equals method.

44

		Lists
	Operation	Description
	isEmpty	Determines whether a list is empty or not. Returns true if the list is empty
		(size() == 0); otherwise, returns false.
	iterator	Obtains an Iterator over all elements in a list.
	clear	Deletes all elements from a list. The size of the list is reset to 0.

All of these operations can be implemented on top of the core operations described previously. However, by choosing to implement them as part of the list, you create a much richer interface, thereby greatly simplifying the job of any developer that uses a list.

The set() operation, for example, can easily be implemented using a combination of delete() and insert(),add() and insert(), isEmpty() and size(), and so on. However, again we stress that beyond the core operations, it is this richness, this encapsulation of common functionality and behavior, that makes a data structure such as a list so powerful.

Try It Out

Creating the List Interface

Having described the operations in a general sense, it’s time to create an actual Java interface that you will implement later in the chapter:

package com.wrox.algorithms.lists;

import com.wrox.algorithms.iteration.Iterable;

public interface List extends Iterable { public void insert(int index, Object value)

throws IndexOutOfBoundsException; public void add(Object value);

public Object delete(int index) throws IndexOutOfBoundsException; public boolean delete(Object value);

public void clear();

public Object set(int index, Object value)

throws IndexOutOfBoundsException; public Object get(int index) throws IndexOutOfBoundsException;

public int indexOf(Object value); public boolean contains(Object value); public int size();

public boolean isEmpty();

}

How It Works

As you can see, you have quite literally taken the operations and converted them, one by one, into methods on an interface, with all the appropriate parameters, return types, and exceptions. It is by no means a trivial interface; there are numerous methods to implement. Once you get into the actual implementation, however, you will see that this extra functionality is quite simple to provide.

You’ll also notice that the List interface extends the Iterable interface introduced in Chapter 2. This interface provides a single iterator() method and allows a list to be used anywhere you write code that need only iterate over the contents of a list.

45

Chapter 3

With this interface in mind, have a look at the following two snippets of code. The first creates an array with three values and then iterates over it, printing each value in turn:

String[] anArray = ...;

anArray[0] = “Apple”; anArray[1] = “Banana”; anArray[2] = “Cherry”;

for (int i = 0; i < anArray.length; ++i) { System.out.println(anArray[i]);

}

The second piece of code creates a list with three values and iterates over it, printing each value as it goes:

List aList = ...;

aList.add(“Apple”);

aList.add(“Banana”);

aList.add(“Cherry”);

Iterator i = aList.iterator()

for (i.first(); !i.isDone(); i.next()) { System.out.println(aList.current());

}

There isn’t a lot of difference between the two — you could argue that in some ways, the version with the list is more readable. In particular, the use of add() and an iterator helps to convey the intent of the code.

Testing Lists

Even though you haven’t yet implemented a single concrete list, you can still think about and describe in code the different scenarios your lists are likely to encounter. To ensure the correct behavior of the various list implementations, you need to create some tests that any implementation must satisfy. These tests will implement in code the requirements described in Tables 3-1 and 3-2 and become the definition of the list contract. Moreover, by working through each of the tests, you should gain a good understanding of the expected behavior of a list, which will make it much easier when it comes time to write your own implementation.

Try It Out

Creating a Generic Test Class

You already know there will be two list implementations. Ordinarily, you might think you would need to create an individual test suite for each, but it’s possible to create a single test suite that can be re-used across all of your different implementations. To do this, create an abstract class containing the actual test cases along with some hooks for subclassing. To get started, you need to define the abstract base class that can be extended by concrete test classes specific for each implementation of a list:

46

Lists

package com.wrox.algorithms.lists;

import com.wrox.algorithms.iteration.Iterator;

import com.wrox.algorithms.iteration.IteratorOutOfBoundsException; import junit.framework.TestCase;

public abstract class AbstractListTestCase extends TestCase { protected static final Object VALUE_A = “A”;

protected static final Object VALUE_B = “B”; protected static final Object VALUE_C = “C”;

protected abstract List createList();

...

}

Apart from some common test data, you’ve defined an abstract method that returns an instance of a list. This will be used by your test methods to obtain a list to test. Anytime you wish to create a test suite for a new type of list, you can extend AbstractListTestCase and implement the createList() method to return an instance of the specific list class. In this way, you are able to re-use the same tests regardless of the actual implementation.

Now let’s move on to testing the behavior of a list.

Try It Out

Testing Methods for Inserting and Adding Values

Insertion is probably the most fundamental function of a list — without it, your lists would remain empty. Here is the code:

public void testInsertIntoEmptyList() { List list = createList();

assertEquals(0, list.size()); assertTrue(list.isEmpty());

list.insert(0, VALUE_A);

assertEquals(1, list.size()); assertFalse(list.isEmpty()); assertSame(VALUE_A, list.get(0));

}

Next, you want to test what happens when you insert a value between two other values. You expect any elements to the right of the insertion point to shift position by one to make room:

public void testInsertBetweenElements() { List list = createList();

list.insert(0, VALUE_A); list.insert(1, VALUE_B); list.insert(1, VALUE_C);

47

Chapter 3

assertEquals(3, list.size());

assertSame(VALUE_A, list.get(0));

assertSame(VALUE_C, list.get(1)); assertSame(VALUE_B, list.get(2));

}

Now make sure you can insert before the first element of the list:

public void testInsertBeforeFirstElement() { List list = createList();

list.insert(0, VALUE_A); list.insert(0, VALUE_B);

assertEquals(2, list.size()); assertSame(VALUE_B, list.get(0)); assertSame(VALUE_A, list.get(1));

}

Also test inserting a value after the last element. This is fundamentally how you add to a list. (You will possibly find yourself doing this more often than any other type of insertion, so you need to get this right!)

public void testInsertAfterLastElement() { List list = createList();

list.insert(0, VALUE_A); list.insert(1, VALUE_B);

assertEquals(2, list.size()); assertSame(VALUE_A, list.get(0)); assertSame(VALUE_B, list.get(1));

}

Next you’ll test that the list correctly handles an attempt to insert a value into a position that falls outside the bounds. In these cases, you expect an IndexOutOfBoundsException to be thrown, indicating an application programming error:

public void testInsertOutOfBounds() { List list = createList();

try {

list.insert(-1, VALUE_A); fail();

} catch (IndexOutOfBoundsException e) { // expected

}

try {

list.insert(1, VALUE_B); fail();

} catch (IndexOutOfBoundsException e) { // expected

}

}

48

Lists

Finally, you can test the add() method. Even though it is simple enough to add to a list using only the insert() method, it is more natural (and requires less coding) to express this intention with a specific method:

public void testAdd() {

List list = createList();

list.add(VALUE_A); list.add(VALUE_C); list.add(VALUE_B);

assertEquals(3, list.size()); assertSame(VALUE_A, list.get(0)); assertSame(VALUE_C, list.get(1)); assertSame(VALUE_B, list.get(2));

}

How It Works

The method testInsertIntoAnEmptyList() merely checks that when you insert a value into an empty list, the size of the list will increase by one and that you are then able to retrieve the value from the expected position.

The method testInsertBetweenElements() tests what happens when you attempt to insert a value between two others. The test starts off with a list containing two values — A and B in positions 0 and 1, respectively, as shown in Figure 3-1.

Index: 0

A

Index: 1

B

Figure 3-1: List prior to insertion.

It then inserts another value — C — between them at position 1. This should put the new value between the A and B, resulting in a list that looks like the one shown in Figure 3-2.

Index: 0	Index: 1	Index: 2
A	C	B

Figure 3-2: List after insertion between two elements.

As you can see, the B has shifted right one position to make room for C.

49

Chapter 3

The method testInsertBeforeFirstElement() ensures that inserting a value into the first position shifts all existing values right one place. The test uses the same insertion point — position 0 — each time insert() is called and confirms that the values end up in the correct order: The A should start off in position 0 and then move right one place to make room for the B.

The method testInsertAfterLastElement() ensures that you can add to the end of the list by inserting a value into a position that is one greater than the last valid position. If the list contained one element, inserting into position 1 would place the new value at the end. If the list contained three elements, inserting into position 3 would place the new value at the end. In other words, you can add to a list by inserting into a position that is defined by the size of the list.

The method testInsertOutOfBounds() checks that your list correctly identifies some common programming errors, such as using a negative insertion point or using an insertion point that is one greater than the size of the list (using an insertion point that is the size of the list adds to the end). The test code starts off with an empty list, meaning that the first position — position 0 — is the only place into which a new value can be inserted. Any attempt to use a negative value or anything greater than zero should result in an IndexOutOfBoundsException.

Finally, the method testAdd() tests the behavior of the convenience method, add(). Three values are added to the list, which is then checked to ensure they end up in the correct order. As you can see from the relative simplicity of testAdd() versus testInsertAfterLastElement(), having a specific method for adding to the end of a list makes the code much more readable and requires slightly less code. More important, it requires less thinking to get it right. Calling add() is far more intuitive than calling insert(), passing in the value of size() as the insertion point!

Try It Out

Testing Methods for Retrieving and Storing Values

Once you can place values into a list, the next thing you’ll want to do is access them. For the most part, you have already tested the behavior of get() (and size() and isEmpty() for that matter) while testing insert() and add(), so you’ll start by testing set():

public void testSet() {

List list = createList();

list.insert(0, VALUE_A); assertSame(VALUE_A, list.get(0));

assertSame(VALUE_A, list.set(0, VALUE_B)); assertSame(VALUE_B, list.get(0));

}

Another thing you haven’t tested are the boundary conditions: What happens when you attempt to access a list before the start or beyond the last element? As with insert(), attempts to access a list beyond the boundaries should result in an IndexOutOfBoundsException:

public void testGetOutOfBounds() { List list = createList();

try { list.get(-1); fail();

50

Lists

}catch (IndexOutOfBoundsException e) {

//expected

}

try { list.get(0); fail();

}catch (IndexOutOfBoundsException e) {

//expected

}

list.add(VALUE_A);

try { list.get(1); fail();

}catch (IndexOutOfBoundsException e) {

//expected

}

}

You also want to test some boundary conditions when calling set():

public void testSetOutOfBounds() { List list = createList();

try {

list.set(-1, VALUE_A); fail();

} catch (IndexOutOfBoundsException e) { // expected

}

try {

list.set(0, VALUE_B); fail();

}catch (IndexOutOfBoundsException e) {

//expected

}

list.insert(0, VALUE_C);

try {

list.set(1, VALUE_C); fail();

} catch (IndexOutOfBoundsException e) { // expected

}

}

51

Chapter 3

How It Works

The method set() works in much the same way as setting the value of an element within an array, so after populating a list with a known value, testSet() replaces it and ensures that the new value is returned instead of the original.

The method testGetOutOfBounds() starts off with an empty list and attempts to access it using a negative position and then again using a position that is too large. Then, just to be doubly sure, it adds a value to the list, creating an element at position 0, and tries once again to access beyond the end of the list. In all cases, you expect an IndexOutOfBoundsException to be thrown.

The method testSetOutOfBounds() is basically the same as testGetOutOfBounds(), but instead of attempting to retrieve a value, you attempt to update its value by calling set().

Try It Out

Testing Methods for Deleting Values

The first type of deletion you’ll test involves deleting the only element in a list. You expect that after the deletion, the list will be empty:

public void testDeleteOnlyElement() { List list = createList();

list.add(VALUE_A);

assertEquals(1, list.size());

assertSame(VALUE_A, list.get(0));

assertSame(VALUE_A, list.delete(0));

assertEquals(0, list.size());

}

You also want to see what happens when you delete the first element of a list containing more than one element. All values should shift left one place:

public void testDeleteFirstElement() { List list = createList();

list.add(VALUE_A); list.add(VALUE_B); list.add(VALUE_C);

assertEquals(3, list.size()); assertSame(VALUE_A, list.get(0));

assertSame(VALUE_B, list.get(1)); assertSame(VALUE_C, list.get(2));

assertSame(VALUE_A, list.delete(0));

assertEquals(2, list.size()); assertSame(VALUE_B, list.get(0)); assertSame(VALUE_C, list.get(1));

}

52

Lists

Now see what happens when you delete the last element of a list containing more than one element:

public void testDeleteLastElement() { List list = createList();

list.add(VALUE_A); list.add(VALUE_B); list.add(VALUE_C);

assertEquals(3, list.size()); assertSame(VALUE_A, list.get(0));

assertSame(VALUE_B, list.get(1)); assertSame(VALUE_C, list.get(2));

assertSame(VALUE_C, list.delete(2));

assertEquals(2, list.size()); assertSame(VALUE_A, list.get(0)); assertSame(VALUE_B, list.get(1));

}

Next you test the behavior when deleting a value from between two others: All values to the right should shift left by one place:

public void testDeleteMiddleElement() { List list = createList();

list.add(VALUE_A); list.add(VALUE_C); list.add(VALUE_B);

assertEquals(3, list.size()); assertSame(VALUE_A, list.get(0));

assertSame(VALUE_C, list.get(1)); assertSame(VALUE_B, list.get(2));

assertSame(VALUE_C, list.delete(1));

assertEquals(2, list.size()); assertSame(VALUE_A, list.get(0)); assertSame(VALUE_B, list.get(1));

}

You also need to ensure that attempts to delete from the list outside the bounds throw an

IndexOutOfBoundsException:

public void testDeleteOutOfBounds() { List list = createList();

try { list.delete(-1); fail();

} catch (IndexOutOfBoundsException e) {

53