Zitat

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

	Java-Quelltext
1 2 3 4 5 6	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:

	Java-Quelltext
1 2 3 4 5 6 7 8 9 10	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.
b) schreibe eine methode, void insert(comparable x), die das objekt x an der richtigen stelle einfügt.

	Java-Quelltext
1 2 3 4 5 6	public boolean contains (object o){ Node p=first; while((p.next != null) || (p.compareTo(o)==0)) p=p.next; return (p!=null); }

	Java-Quelltext
1 2 3 4 5 6 7 8 9 10	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; }