Dictionary Implementations - Data Structures and Abstractions with Java - page 508

LISTING 20-4

SortedVectorDictionary ' s private inner class KeyIterator

private class KeyIterator implements Iterator<K>
{

private Iterator<Entry> traverser;

private KeyIterator()
{

traverser = dictionary.iterator();
} // end default constructor

public boolean hasNext()
{

return traverser.hasNext();
} // end hasNext

public K next()
{

Entry nextEntry = traverser.next();
return nextEntry.getKey();
} // end next

public void remove()
{

throw new UnsupportedOperationException();
} // end remove
} // end KeyIterator

The method getValueIterator has an analogous implementation: You define another inner
class similar to KeyIterator . We leave the details as an exercise.

Note: Using ArrayList instead of Vector
Since ArrayList and Vector each implement the interface java.util.List , and since we
were careful to use only methods in this interface, you could replace Vector with ArrayList
in the implementation of SortedVectorDictionary .

Linked Implementations

20.21

The last implementations of the ADT dictionary that we will consider in this chapter store the dic-
tionary's entries in a chain of linked nodes. As presented in Chapters 3 and 14, for example, a chain
can provide as much storage as necessary for the entries. You can encapsulate the two parts of an
entry into an object, as Figure 20-6a illustrates, just as you did for an array or a vector. If you
choose this option, your dictionary class can use the classes Node from Segment 3.25 and Entry
from Segment 20.17.

Another option does not use the class Entry . You could use two chains, as in Figure 20-6b, but
a simpler approach is to revise the definition of a node to include both parts of the entry, as
Figure 20-6c illustrates. The private inner class Node , defined within the dictionary class, would
then contain the data fields.

VideoNote

Linked-chain dictionaries