Hvordan gennemløber man et linkedlist?

vil du ikke finde den løber der har den bedste tid?

here goes i hvert fald:

public Runner getHurtigstRunner()
{
  Runner res = (Runner) runners.get( 0 );
 
  for( int i = 1; i < runners.size(); i++ )
      if( res.time > (Runner) runners.get( i ).time )
        res = (Runner) runners.get( i );
 
  return res; 
}

hvis der er nogle Runner'e med samme tid, får du den første i listen med den tid.

Jeg foretrækker at bruge iterator klassen til den slags.

Værsessgo:

public Runner getHurtigstRunner()
{
  Runner best=null;
  Runner current=null;
  Iterator it = runners.iterator();
  while (it.hasNext())
  {
    current = (Runner) it.next();
    if (best == null)
      best = current;
    else
    if (current.time <= best.time)
      best = current;
  }
  return best;
}

Med en LinkedList tager det lang tid
at indicere som i riversens forslag.
Brug i stedet en iterator der vil
gennemløbe listen hurtigere, du kan
iøvrigt løbe begge veje med ListIterator.
public Runner getFastestRunner() {
Iterator iterator = runners.iterator();
Runner res = (Runner)iterator.next();
while ( iterator.hasNext() ) {
Runner r = (Runner)iterator.next();
if ( res.time > r.time )
    res = r;
}
return res;
}
PS implementeringen antager at der er mindst
et element i listen.

Du skal bruge en Iterator, de er netop lavet til det samme.

En alternativ (og pæn) løsning kunne være at lade Runner implementere Comparable og lave en compareTo-metode, der sammenligner to Runner-objekter efter deres tid.

Hvis man så bruger en SortedSet i stedet for en linkedList, vil den automatisk sortere løberne efter deres tider.

Hvis du vil have en hægtet liste der er hurtig at løbe igennem sekventielt kan du implementere din egen.

Foruden de faste pointere til første og sidste element så lav en dynamisk pointer der peger på det sidste element der blev spurt på. Derved bladres der kun et element hver gang der spørges på et nyt (hvis der spørges sekventielt 1, 2, 3, ...)

Suns implementering af en hægtet liste LinkedList vil bladre fra den ene ende og så frem (eller tilbage) hver gang, det bliver i værste fald.

1+2+3+4+5+6+...+N for nummer N 
samme som  ½(n*(n+1))

1000:    500500
100000:  5000050000 (totalt uacceptabelt)

Mange tak for alle jeres kommentar

codemon: Det er effektivt og hurtigt at
køre igennem LinkedList med en iterator,
kun hvis du bruger get metoden har du
problemet med langsom tilgangstid.
Iøvrigt er dine estimater for pessimistiske
idet Sun implementering (som det fremgår
af dokumentationen) kører baglæns hvis
indeks ligger i anden halvdel af listen,
så din summation bliver:
(1+2+..+N/2)*2 hvorved du får
N^2/8 (N stor). Dette har dog ingen betydning
hvis du benytter er iterator, men som du siger
er det uacceptablt at benytter random access
for en LinkedList.

oops, der røg en 2 faktor, det skulle
være N^2/4.

Den er vældig smart den Iterator, kan jeg egentlig bruge den i andre sammenhæng, jeg tænker på hashtabeller f.eks?

Det er det smarte ved iteratorer,
de understøttes af en forfærdelig masse
klasser, specielt alle Collections.
Desværre understøtter HashTable det
ikke, men den understøtter dog Enumeration
som er næste det samme blot ikke så
sikkert (og med uheldige navne). Den kan
så tilgengæld med values metoden returnere
en Collection som kan levere en iterator.
Det er desværre lidt kompliceret, men
at kende Collections framework'et tillader
dig at løse mange opgaver med meget lidt kode,
idet der findes mange algoritmer der er
defineret for Collections.
PS Det er Collection interfacet jeg taler om,
der er også en klasse der hedder Collections
som indeholder søge og sorteringsalgoritmer
etc. Ovenfor har jeg benyttet Collections
som flertal af Collection.

takker for dit hurtige svar