[ Data Structures with Java ] Section 12.4 : Iterator Applications

Preface :
List iterators find important applications in algorithms that use a scan to add and remove elements. In this section, we present the method insertOrder(), which can be used to build an ordered list. A related algorithm, removeDuplicates(), deletes all duplicate elements from an ordered list.

Ordered Lists :
In many applications, we wish to maintain an ordered list of elements with its values in ascending or descending order. An algorithm to add a new element must scan the ordered list of existing elements and identify the correct location for the new element. The following discussion illustrate the algorithm for a list in ascending order.
Begin by initializing a list iterator to reference the start of the list. Scan the list, looking for the first element whose value is greater or equal to the new item. This identifies the insertion location, and we can use the add() method to place the new item in the list. The fact that next() is used to both access a value and advance the iterator adds complexity to the insertion process. Let us at an example and explore the different situations in which the new elements becomes a minimum value, an intermediate value, or a maximum value in the updated list.
Assume intList is a linked list containing the Integer values 60, 65, 74 and 82 and curr is the list iterator. The following illustrates how one inserts a new value at front, middle, and back of the 4-element list.
- Insert 50 in the list
A first call to next() extracts the value 60, which is greater than or equal to 50. The scan terminates with curr referencing the second element in the list. Value 50 will be the minimum value in the new list and thus should be added at the front of the list immediately before 60; that is, at the element curroriginally referenced before it advanced to 65. The iterator has moved one position too far and so must be set back to its former position before we can call add(). Resetting the iterator is accomplished with a call to the method previous() :


- Insert 70 in the list
The scan terminates when next() extracts the value 74, which is the first value that is greater or equal to 70. As in the first case, the iterator curr has advanced to the next position and references 82. Inserting 70 must occur before 74. First, use previous() to reset curr and then use add() to insert the element :


- insert 90 in the list 
The scan of the list fails to find an element which is greater than 90. The iterator curr has reached the end of the list (curr.hasNext() == false). Insert 90 at the back of the list referenced by the current value of curr :


The method insertOrder() takes the list and the new value item as arguments and implements the algorithm. As the example illustrate, the new element always enters the list at a position referenced by the iterator curr. In the cases, however, where the new element has a value that is less than or equal to an existing list element, we must take into account that fact that the method next() has moved the iterator forward one position past the insertion point. A call to previous() repositions the iterator prior to using add() to insert the new element. The efficiency of the insertOrder() algorithm depends on the value of the new item. If the list has n elements, the worst-case performance occurs when the insertion occurs at the end of the list. This case requires n comparisons and has running time O(n). Also on average, we expect to search half the list to find an insertion point. As a result, the average running time is O(n). Below is the implementation of insertOrder() :

- Method insertOrder() implementation :

view plaincopy to clipboardprint?

1. public static extends Comparablesuper T>> void insertOrder(LinkedList orderedList, T item) {  
2.     java.util.ListIterator curr =  orderedList.listIterator();  
3.     while(curr.hasNext()) {  
4.         if(curr.next().compareTo(item)<0) continue;  
5.         curr.previous();  
6.         break;  
7.     }  
8.     curr.add(item);  
9. }  

Removing Duplicates from an Ordered List :
An algorithm to remove duplicates in an ordered list provides an interesting application of iterators. The process involves scanning the list with an iterator and comparing the current value with a target value. Let us use an example to trace the algorithm. Below figure (a) has iterator curr initially references the first element in the list. A call to next() extracts the value Integer 5 and moves the iterator forward. The initial value becomes the target value. A second call to next() extracts a duplicate value, which is removed from the list. Note that curr now references Integer 7, and the deletion removes the previous element (b) :

The method removeDuplicates() implements the algorithm. It assumes that the object type for the elements in the list implements equals(). After verifying that the list is not empty, the method assigns the initial value of target as the first list element. A loop scans the list and either removes an element or updates the value for target. Note that we only need to use an Iterator object. We move through the list in the forward direction. Below is the implementation of method removeDuplicates() :

- Method removeDuplicates() Implementation :

view plaincopy to clipboardprint?

1. public static extends Comparablesuper T>>   
2.        void removeDuplicates(LinkedList orderedList) {  
3.     if(!orderedList.isEmpty()) {  
4.         java.util.ListIterator curr = orderedList.listIterator();  
5.         T target = curr.next(), tmp;  
6.         while(curr.hasNext()) {  
7.             tmp = curr.next();  
8.             if(tmp.equals(target)) curr.remove();  
9.             else target = tmp;  
10.         }  
11.     }  
12. }  

This message was edited 2 times. Last update was at 05/10/2010 09:53:21