CODEWITHSUNDEEP
javalinked-listdoubly-linked-list
Chip
Chip

Reputation: 155

Find min in Linked list

I'm trying to find the min in a linked list of Vertices. This is what I wrote, but it is faulty. I don't get an error, but my program doesn't work and I think this is the source of the error. What am I doing wrong? 

      Iterator itr = vertices.iterator();
      Vertex smallest= getVertex(s);
      Vertex temp;
      while (itr.hasNext()){
          smallest=(Vertex)itr.next();
           if(itr.hasNext() && vertices.size()> 1 ){//there are at least 2 vertices left
                temp = (Vertex)itr.next();
                if (temp.distance< smallest.distance){
                    smallest = temp;
                }
          }
     }

Upvotes: 1

Views: 65

Answers (1)

Andy Turner
Andy Turner

Reputation: 140504

The problem is that you are consuming two elements from the iterator on each iteration (via itr.next()), so this means you are only comparing some elements:

1----2----3-----4-----5-----6
\----/    \-----/     \-----/

You compare 1 and 2; 3 and 4; 5 and 6; but not 2 and 3; 4 and 5.

The easiest way to solve this is to keep the previous vertex:

Vertex prev = itr.next();
while (itr.hasNext()) {
  Vertex current = itr.next();

  // Compare prev and current

  prev = current;
}

Note also that you can avoid the casts (Vertex) if you declare the iterator with a type parameter:

Iterator<Vertex> itr = vertices.iterator();

Upvotes: 5

Related Questions