Hilfe bei Java-Übung

[dic]

ich bin hier am java lernen und habe hier folgende aufgabe zu lösen:

wir gehen davon aus, dass objekte, die die schnittstelle comparable implementieren, eine funktion compareTo() besitzen, die einen vergleich zweier objekte erlaubt.

Public interface comparable{

     /**

     * @return -1 wenn empfängerobjekt < other, +1 wenn > und 0 wenn ==

     */

     public int compareTo (Object other);

}

die folgende doppelt verkettete liste sei so aufgebaut (repräsentationsvariante), dass die listenelemente stets aufsteigend sortiert sind. die interessanten teile der klasse sehen wie folgt aus:

Public class list{

     Private static class Node{   // knotenklasse

          combarable value;       // inhalt eines knoten

          Node previous;          // referenz auf den vorgänger

          Node next               // referenz auf den nachfolger

     }


private Node first;       // referenz auf den ersten knoten

private Node last; 	  // referenz auf den letzten knoten

}

a) schreibe eine methode, die feststellt, ob ein object in der liste enthalten ist und je nach dem true oder false zurückgibt. schreibe eine methode, void insert(comparable x), die das objekt x an der richtigen stelle einfügt.

zu a) lautet meine antwort:

public boolean contains (object o){

     Node p=first;

     while((p.next != null) || (p.compareTo(o)==0))

          p=p.next;

     return (p!=null);

}

und zu so:

public void insert(combarable x){

     Node p=first;

     Node q=(Node)x;

     while(p.compareTo(q)==-1)

          p=p.next;

     q.previous=p;

     p.next.previous=q;

     q.next=p.next;

     p.next=q;

}

ist das so in ordnung?

bin für konstruktive beiträge dankbar!

grüße

[Klotzkopp]

Bedenke bei a), dass du in der Regel nicht die ganze Liste durchsuchen musst.

[dic]

danke, für die zügige antwort!

verbesserung zu a)

public boolean contains (object o){

     Node p=first;

     while(p.next!=null)

          if (p.compareTo(o)==0)

               return true;

          else

               p=p.next;

     return false;

}

hier bricht er dann rechtzeitig ab.

ist der rest denn so in ordnung gewesen?

grüße

[Klotzkopp]

Das ist keine Verbesserung, wenn der Wert nicht drin ist, gehst du immer noch die gesamte Liste durch. Das muss nicht sein, du kannst unter Umständen schon früher aufhören. Sagen wir beispielsweise, du suchst die 5, und die Liste beginnt mit 8...

[dic]

ein kleine verbesserung ist es doch schon. er muss doch nun nicht mehr bis ans ende laufen.

aber nun u.u. auch gar nicht mehr laufen... oder?

public boolean contains (object o){

     Node p=first;

     while(p.next!=null || p.compareTo(o)==1)  // 1, wenn empfängerobjekt > o

          if (p.compareTo(o)==0)

               return true;

          else

               p=p.next;

     return false;

}

grüße