Dictionaries - Data Structures and Abstractions with Java - page 486

lineNumber++;
} // end while
data.close();
} // end readFile

The most interesting part of this method is the list of line numbers as the value associated with
a search key. Since we have chosen a linked implementation of the list, we need to be concerned
with the efficiency of adding to the end of the list. If the underlying chain of nodes has only a refer-
ence to the first node—as is true of LinkedListWithIterator —each such addition requires a tra-
versal to reach the end of the chain. Choosing a list implementation that maintains a reference to
the last node in the chain would make the addition to the end of the list quite efficient. We discussed
such tail references in Chapter 11. We should make this adjustment to our class of lists for this
application.

19.21

The method display . Earlier, we chose a list implementation that included an iterator so that the
following method display could display the line numbers in the concordance efficiently. Notice
that we use the dictionary iterators, just as we did in the analogous method display given in
Segment 19.17 for the previous example. But here each value is a list with its own iterator, which
we use to traverse the list's line numbers.

public void display()
{

Iterator<String> keyIterator = wordTable.getKeyIterator();
Iterator<ListWithIteratorInterface<Integer>> valueIterator =
wordTable.getValueIterator();

while (keyIterator.hasNext())
{

// display the word
System.out.print(keyIterator.next() + " ");
// get line numbers and iterator
ListWithIteratorInterface<Integer> lineList = valueIterator.next();
Iterator<Integer> listIterator = lineList.getIterator();
// display line numbers
while (listIterator.hasNext())
{

System.out.print(listIterator.next() + " ");
} // end while
System.out.println();
} // end while
} // end display

Question 9 Write a method getLineNumbers for the class Concordance that returns a list of
the numbers of the lines that contain a given word.

Java Class Library: The Interface Map

19.22

The standard package java.util contains the interface Map<K, V> that is similar to our interface for the
ADT dictionary. The following method headers are for a selection of methods in Map that are like the
ones you have seen in this chapter. We have highlighted where they differ from our methods.