Beginning Algorithms (2006)

Chapter 3

How It Works

The indexOf() method performs a linear search of the list to find a value. It achieves its goal by starting at the first position within the list and working its way through each element until either the value is found or the end is reached.

The contains() method calls indexOf() to perform a search on its behalf and returns true only if it is found (indexOf >= 0).

Although simple to implement, linear searching doesn’t scale very well to large lists. Imagine a list containing the following values: Cat, Dog, Mouse, Zebra. Now imagine you were to search for each value in turn (first Cat, then Dog, and so on.) and count the number of comparisons needed to find each value.

Cat, being the first in the list, will take one comparison. Dog will take two, Mouse three, and Zebra four. If you calculate the average number of comparisons required, 1 + 2 + 3 + 4 / 4 = 10 / 4 = 2.5, you can see that for a list containing N items, the average number of comparisons required is around N / 2, or O(N). This is the same as the worst-case time and therefore clearly not a very efficient method for searching.

Chapter 9, “Binary Searching,” introduces a more efficient method for searching a list, but for now we will make do with this “brute force” approach to searching.

Try It Out

Methods for Deleting Values

The List interface provides two methods for deleting values. The first of these enables you to delete a value by its position:

public Object delete(int index) throws IndexOutOfBoundsException { checkOutOfBounds(index);

Object value = _array[index]; int copyFromIndex = index + 1; if (copyFromIndex < _size) {

System.arraycopy(_array, copyFromIndex,

_array, index,

_size - copyFromIndex);

}

_array[--_size] = null; return value;

}

You also need to support the deletion of a specified value without knowing its precise location. As with contains(), you can take advantage of the fact that you already have a mechanism for determining the position of a value using indexOf():

public boolean delete(Object value) { int index = indexOf(value);

if (index != -1) { delete(index);

return true;

}

return false;

}

64

Lists

How It Works

After first checking the validity of the input, the first delete() method copies all values to the right of the deletion point left one position. Then the size of the list is decremented accordingly and the value in the last element of the array is cleared.

It is necessary to clear the last element of the array because you haven’t actually moved the values left by one position, you’ve only copied them. If you didn’t clear out what used to be the last element containing a value, you might inadvertently hold on to copies of deleted values, thereby preventing them from being garbage collected. This is more commonly referred to as a memory leak.

Notice the bounds checking to ensure you don’t cause an ArrayIndexOutOfBoundsException when deleting from the last element of the array. In fact, you may like to try commenting out the entire block of code under the if statement and rerunning the tests to see what happens. Also notice you have been careful to take a copy of the value that was stored at the deleted position so that it can be returned to the caller.

It is worth noting here that the capacity of the underlying array never shrinks. This means that if the list grows very large and then shrinks significantly, there may be a lot of “wasted” storage. You could get around this problem by implementing the inverse of ensureCapacity(). Each time you delete an element from the list, you could check the new size against some percentage threshold. For example, once the size drops to 50 percent of the list capacity, you could reallocate a smaller array and copy the contents across, thereby freeing up the unused storage. However, for the sake of clarity, we have chosen not to do this.

As an aside, the code for the JDK implementation of ArrayList behaves in exactly the same way. Again, nothing to worry about in most cases, but something to keep in mind nevertheless.

The second delete() works by first calling indexOf() to determine the position of the first occurrence of the specified value, calling the first delete() method if found. The performance of the first delete() method is O(1) — discounting the time taken to copy the values — whereas the second delete() is intrinsically tied to the performance of indexOf(), giving an average deletion time of O(N).

Try It Out

Completing the Interface

You’re almost done with implementing the entire List interface. There are only a few more methods to cover:

public Iterator iterator() {

return new ArrayIterator(_array, 0, _size);

}

public int size() { return _size;

}

public boolean isEmpty() { return size() == 0;

}

65

Chapter 3

How It Works

The iterator() method is very simple — you already have the necessary code in the form of the ArrayIterator class from Chapter 2.

Implementing the size() method is even simpler. The insert() and delete() methods already maintain the size of the list, so you simply return whatever value is currently stored in the _size field.

Finally, isEmpty() returns true only if the size of the list is zero (size() == 0). Although trivial in implementation, isEmpty() — like all the convenience methods on the List interface — makes your application code more readable by reducing the amount of “noise.”

A Linked List

Rather than use an array to hold the elements, a linked list contains individual elements with links between them. As you can see from Figure 3-3, each element in a linked list contains a reference (or link) to both the next and previous elements, acting like links in a chain.

Index: 0

Index: 1

Index: 2

next

next

A

B

C

previous

previous

Figure 3-3: Elements of a doubly linked list have references in both directions.

More precisely, this is referred to as a doubly linked list (each element has two links), as opposed to a singly linked list in which each element has only one link. This double linking makes it possible to traverse the elements in either direction. It also makes insertion and deletion much simpler than it is for an array list.

As you might recall from the discussion on array lists, in most cases when deleting or inserting, some portion of the underlying array needs to be copied. With a linked list, however, each time you wish to insert or delete an element, you need only update the references to and from the next and previous elements, respectively. This makes the cost of the actual insertion or deletion almost negligible in all but the most extreme cases. For lists with extremely large numbers of elements, the traversal time can be a performance issue.

A doubly linked list also maintains references to the first and last elements in the list — often referred to as the head and tail, respectively. This enables you to access either end with equal performance.

Try It Out

Creating the Test Class

Remember that the tests are the best way of validating that your implementation meets the requirements set out in Tables 3-1 and 3-2 at the beginning of the chapter. This time, create a class named

LinkedListTest that extends AbstractListTestCase:

66

Lists

package com.wrox.algorithms.lists;

public class LinkedListTest extends AbstractListTestCase { protected List createList() {

return new LinkedList();

}

}

How It Works

As you did for your ArrayListTest class earlier, you extend AbstractListTestCase in order to take advantage of all the predefined test cases. This time, however, the createList() method returns an instance of LinkedList. Notice also that this time you haven’t created any additional test cases because the tests already defined in AbstractListTestCase will be sufficient.

Try It Out

Creating the LinkedList Class

Begin by creating the LinkedList class with all its fields and constructors:

package com.wrox.algorithms.lists;

import com.wrox.algorithms.iteration.Iterator;

import com.wrox.algorithms.iteration.IteratorOutOfBoundsException;

public class LinkedList implements List {

private final Element _headAndTail = new Element(null); private int _size;

public LinkedList() { clear();

}

...

}

How It Works

As with any other list, the first thing you need to do is implement the List interface. Once again, you track the size of the list through the instance variable _size. (Theoretically, you could derive the size each time it’s required by counting every element, but that really wouldn’t scale!)

Not so obvious is why you have a single, unmodifiable, element _headAndTail instead of the two references discussed at the start of the section. This field is known as a sentinel. A sentinel — often referred to as the null object pattern or simply a null object — is a technique for simplifying an algorithm by adding a special element to one or both ends of a data structure to avoid writing special code that handles boundary conditions. Without the use of a sentinel, our code would be littered with statements that checked for and updated null references of the head and tail. Instead, use the next and previous fields of the sentinel point to the first and last elements of the list. Moreover, the first and last elements can themselves always refer back to the sentinel as if it was just another element in the chain. Sentinels can be a difficult concept to grasp, so don’t worry too much if it seems a little strange at first. In fact, trying to formulate an algorithm that uses sentinels is not always a particularly intuitive process. However, once you become accustomed to using them, you will find that your algorithms become more elegant and succinct — try writing a doubly linked list without one and you will soon see what we mean.

67

Chapter 3

Lastly, a constructor calls clear(). You’ll create the clear() method later, so don’t worry too much about what it does right now — suffice it to say that it resets the internal state of the class.

Try It Out

Creating an Element Class

Unlike an array list, a linked list has no inherent place to store values, so you will need some other way of representing an element. For this, you create the aptly named Element inner class:

private static final class Element { private Object _value;

private Element _previous; private Element _next;

public Element(Object value) { setValue(value);

}

public void setValue(Object value) { _value = value;

}

public Object getValue() { return _value;

}

public Element getPrevious() { return _previous;

}

public void setPrevious(Element previous) {

assert previous != null : “previous can’t be null”; _previous = previous;

}

public Element getNext() { return _next;

}

public void setNext(Element next) {

assert next != null : “next can’t be null”; _next = next;

}

public void attachBefore(Element next) { assert next != null : “next can’t be null”;

Element previous = next.getPrevious();

setNext(next);

setPrevious(previous);

next.setPrevious(this); previous.setNext(this); }

public void detach() {

68

Lists

_previous.setNext(_next); _next.setPrevious(_previous);

}

}

How It Works

For the most part, the inner class Element is quite straightforward. In addition to holding a value, each element also holds references to the next and previous elements, along with some simple methods for getting and setting the various fields.

At some point, however, your code will need to insert a new element into a list. This logic is encapsulated inside the method attachBefore().

As the name suggests, this method allows an element to insert itself before another by storing the references to the next and previous elements and then updating them to refer to itself.

You also need to delete elements. For this, you created the method detach(), which allows an element to remove itself from the chain by setting the next and previous elements to point at one another.

Notice that at no point in all of this have you needed to check for null values or update references to the head or tail. This is only possible because you are using a sentinel. Because the sentinel is itself an instance of Element, there will always be a next and previous element to update.

Try It Out

Methods for Inserting and Adding Values

Inserting into a linked list is conceptually simpler than it is for an array list because no resizing is involved. However, a little bit of logic is involved in finding the correct insertion point:

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();

}

Element element = new Element(value); element.attachBefore(getElement(index)); ++_size;

}

private Element getElement(int index) { Element element = _headAndTail.getNext();

for (int i = index; i > 0; --i) { element = element.getNext();

}

return element;

}

69

Chapter 3

As for add(), you again simply delegate to insert(), passing the size of the list as the point for insertion:

public void add(Object value) { insert(_size, value);

}

How It Works

As always, insert() starts by first validating the input. You then create a new element with the specified value, find the insertion point, and attach it to the chain before finally incrementing the size of the list to reflect the change.

The getElement() method is really the workhorse of this linked list implementation. It is called by a number of methods and traverses the list in search of the element at the specified position. This bruteforce approach gives insert() (and, as you will see later, delete()) an average and worst-case running time of O(N).

You can actually improve on the actual performance of getElement(). As the joke goes, “Q: How long is a linked list? A: Twice the distance from the middle to the end.” Recall that our linked list implementation holds a reference to both ends of the list, not just the head. If the position we are searching falls in the first half of the list, we can start at the first element and work our way forward. Conversely, if the desired position falls in the second half of the list, we can start searching from the last element and work our way backward. This means we never traverse more than half the list to reach our destination. Although this has no effect on the magnitude of the search times, it does effectively cut the actual average running times in half. This has been left as an exercise at the end of the chapter.

Try It Out

Methods for Storing and Retrieving Values

The way to go about setting and retrieving values from a linked list is almost identical to that for an array list except that instead of indexing into an array, you make use of the getElement() method you introduced for insert():

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

return getElement(index).getValue();

}

public Object set(int index, Object value) throws IndexOutOfBoundsException {

assert value != null : “value can’t be null”; checkOutOfBounds(index);

Element element = getElement(index); Object oldValue = element.getValue(); element.setValue(value);

return oldValue;

}

private void checkOutOfBounds(int index) { if (isOutOfBounds(index)) {

throw new IndexOutOfBoundsException();

}

70

Lists

}

private boolean isOutOfBounds(int index) { return index < 0 || index >= _size;

}

How It Works

In both cases, after first checking the validity of the position, you obtain the desired element and get or set the value as appropriate.

Because both get() and set() are tied to the implementation of getElement(), their running times are similarly constrained. This makes indexed-based retrieval of values from a linked list much slower on average than for an array list.

Try It Out

Methods for Finding Values

Conceptually at least, searching a linked list is really no different from searching an array list. You have little choice but to start at one end and continue searching until you either find the value you are looking for or simply run out of elements:

public int indexOf(Object value) {

assert value != null : “value can’t be null”;

int index = 0;

for (Element e = _headAndTail.getNext(); e != _headAndTail;

e = e.getNext()) {

if (value.equals(e.getValue())) { return index;

}

++index;

}

return -1;

}

The contains() method is identical in every way to the one found in ArrayList:

public boolean contains(Object value) { return indexOf(value) != -1;

}

How It Works

The difference between the linked list and array list implementations of indexOf() is really only in how you navigate from one element to the next. With an array list it’s easy: You simply increment an index and access the array directly. With linked lists, on the other hand, you need to use the links themselves to move from one element to the next. If the value is found, its position is returned. Once the sentinel is

71

Chapter 3

reached, however, you have fallen off the end of the list, the loop terminates, and -1 is returned to indicate that the value doesn’t exist.

The contains() method calls indexOf() and returns true.

Try It Out

Methods for Deleting Values

Deletion from a linked list is almost trivial. You actually implemented most of the code inside your Element inner class earlier:

public Object delete(int index) throws IndexOutOfBoundsException { checkOutOfBounds(index);

Element element = getElement(index); element.detach();

--_size;

return element.getValue();

}

And, of course, here’s a method for deleting by value:

public boolean delete(Object value) {

assert value != null : “value can’t be null”;

for (Element e = _headAndTail.getNext(); e != _headAndTail;

e = e.getNext()) {

if (value.equals(e.getValue())) { e.detach();

--_size; return true;

}

}

return false;

}

How It Works

After checking that the specified position is valid, the first delete() method obtains the appropriate element by calling getElement(), detaches it, and decrements the size of the list before returning its value.

The code for the second delete() method is almost the same as for indexOf(), the difference being that, rather than tracking and returning the position, upon finding the first matching element, you immediately delete it and return its value. (Don’t forget to decrement the size of the list after calling detach!)

Try It Out

Creating an Iterator

Iteration for a linked list is somewhat more involved than for an array list. Like searching and deleting, however, it is simply a matter of following the links — in either direction — until you reach an end. For this you will create an inner class, ValueIterator, to encapsulate the iteration logic:

72

Lists

private final class ValueIterator implements Iterator { private Element _current = _headAndTail;

public void first() {

_current = _headAndTail.getNext();

}

public void last() {

_current = _headAndTail.getPrevious();

}

public boolean isDone() {

return _current == _headAndTail;

}

public void next() {

_current = _current.getNext();

}

public void previous() {

_current = _current.getPrevious();

}

public Object current() throws IteratorOutOfBoundsException { if (isDone()) {

throw new IteratorOutOfBoundsException();

}

return _current.getValue();

}

}

Having defined the inner class, you can return an instance from the iterator() method:

public Iterator iterator() { return new ValueIterator();

}

How It Works

The ValueIterator class is virtually identical to the ArrayIterator class from Chapter 2 except that, as was the case for searching and deleting, you use the getNext() and getPrevious() methods to traverse forward and backward, respectively, between the elements until you reach the sentinel.

Try It Out

Completing the Interface

You have arrived at the last few methods of the interface: size(), isEmpty(), and clear():

public int size() { return _size;

}

public boolean isEmpty() { return size() == 0;

}

73