Java Reference
In-Depth Information
KeyIterator
.
ValueIterator
has a similar definition. Both of these classes are like the inner class
IteratorForLinkedList
that appears in Segments 15.19 through 15.23 of Chapter 15.
LISTING 20-6
SortedLinkedDictionary
's private inner class
KeyIterator
private class
KeyIterator
implements
Iterator<K>
{
private
Node nextNode;
// node containing next entry in iteration
private
KeyIterator()
{
nextNode = firstNode;
}
// end default constructor
public boolean
hasNext()
{
return
nextNode !=
null
;
}
// end hasNext
public
K next()
{
K result;
if
(hasNext())
{
result = nextNode.getKey();
nextNode = nextNode.getNextNode();
}
else
throw new
NoSuchElementException();
return
result;
}
// end next
public void
remove()
{
throw new
UnsupportedOperationException();
}
// end remove
}
// end KeyIterator
20.26
Efficiency.
Like adding an entry, removing or retrieving an entry requires a sequential search of the
chain. Traversal of a sorted chain proceeds just as it would for an unsorted chain. Thus, the worst-
case efficiencies of the dictionary operations for a sorted linked implementation are as follows:
Addition
O(
n
)
Removal
O(
n
)
Retrieval
O(
n
)
Traversal
O(
n
)
