store or clone the Iterator

[p7371464]

I have a LinkedList which stores some integer key.
For each key, I can use a computing function f() to get the
corresponding value.
In order to founding the key which has smallest value, I must work
through all key in the list.
Once found the key, I will remove the key from the list.
So I wrote the code as follow:

....
LinkedList<Integer> list = new LinkedList<Integer>();
....
....add some integer key to the list
.....

ListIterator<Integer> it = list.listIterator();
ListIterator<Integer> it_save;
Integer min=Integer.MAX_VALUE;

//walk through all key in the list to found the key have minimum value
while(it.hasNext()){
int key = it.next();
int value = f(i);

if(value < min){
it.previous();
It_save = it;
it.next();
}
}

//remove the key which has smallest value
it_save.remove();
.....

But the above code can not work correctly, have any method to store the
ListIterator variable while
scan the list ?

Thanks in advance.

 

[Thomas Hawtin]

I have a LinkedList which stores some integer key.
For each key, I can use a computing function f() to get the
corresponding value.
In order to founding the key which has smallest value, I must work
through all key in the list.
Once found the key, I will remove the key from the list.
So I wrote the code as follow:

Using ListIterator.previousIndex is the obvious solution. If the extra
iteration through the list is a performance problem, you've probably
started with the wrong data structure anyway (LinkedList is almost
always the wrong choice).

Tom Hawtin

 

[ricky.clarkson]

I would do this by looping through, and storing a minimum value..

int min=Integer.MAX_VALUE;

for (final Integer key: list)
{
int value=f(key);

if (value<min)
min=value;
}

return min;

Of course, this gives you a stupidly high number if there are no
elements in the list, and I'll leave solving that as an exercise for
the OP.

This can be nicely generalised into a method that takes a function as
an argument, which is also fun. See fpeas.util.Collections.min in
Functional Peas:

http://functionalpeas.googlecode.com/svn/trunk/src/fpeas/util/Collections.java

 

[Piotr Kobzda]

(e-mail address removed) wrote:

[...]

But the above code can not work correctly, have any method to store the
ListIterator variable while
scan the list ?

No.

But your goal can be achieved without of it, using only two independent
iterators. See implementation:

public static <T> T removeFirstMin(
LinkedList<T> list, Comparator<? super T> c) {
int left = list.size();
ListIterator<T> fit = list.listIterator();
ListIterator<T> bit = list.listIterator(left);
T f = fit.next();
T b = bit.previous();
for (; left > 1; --left) {
if (c.compare(f, b) <= 0) {
b = bit.previous();
} else {
f = fit.next();
}
}
fit.remove();
return f;
}

Which can be applied into your scenario this way:

removeFirstMin(list, new Comparator<Integer>() {

public int compare(Integer k1, Integer k2) {
int v1 = f(k1);
int v2 = f(k2);
return (v1<v2 ? -1 : (v1==v2 ? 0 : 1));
}

});


HTH,
piotr