Hallo Leute. Ich hab versucht meinen Quellcode für einfach verkettete Listen umzuschreiben so dass es zu Doppelt verketteten Listen wird. Leider komm ich nicht so ganz zurecht. Ich weis nur folgendes: ich muss nur die methoden insert und delete anpassen, stimmt das? wäre nett wenn ihr mir da weiterhelfen könntet. Tausend dank im Vorraus.
Code:
public class Cons2 {
/** Creates a new instance of Cons2 */
public Object obj; // das Objekt in dieser Zelle
public Cons2 next;
public Cons2 prev;
// Verweis auf die naechste Zelle
public Cons2(Object obj) {
this.obj = obj;
next = null;
prev = null;
}
}
public class ConsList
{
private Cons head, foot; // Kopf und Fuss der Liste
public ConsList() { head = foot = null; /* neue leere Liste */ }
public boolean contains(Object obj) { return contains(head, obj); }
protected boolean contains(Cons cons, Object obj) {
if (cons == null) return false;
else if (cons.obj == obj) return true;
else return contains(cons.next, obj);
}
public void print() {
System.out.print("Liste [");
print(head); // rekursive Ausgabe der Cons-Zellen
System.out.println("]");
}
protected void print(Cons cons) {
if (cons == null) return ; // letzte Zelle erreicht
System.out.print(cons.obj); // Objekt ausgeben
if (cons.next != null) {
System.out.print(", ");
print(cons.next); // Rekursiv weiter
}
}
public void insert(Object obj) {
Cons cons = new Cons(obj); // neue Cons-Zelle
cons.next = head; // vorne anfuegen..
head = cons; // .. und Kopf der Liste anpassen
if (foot == null) foot = cons; // eventuell auch den Fuss
}
public void append(Object obj) {
Cons cons = new Cons(obj); // neue Cons-Zelle
if (foot == null) head = foot = cons; // genau eine Cons-Zelle
else { // hinten anfuegen und Fuss anpassen
foot.next = cons;
foot = cons;
}
}
public void remove(Object obj) {
if (head == null) return ;
if (head.obj == obj) {
if (head == foot) foot = head = null;
else head = head.next; // erste Cons-Zelle entfernen
} else remove(head, head.next, obj);
}
protected void remove(Cons prev, Cons cons, Object obj) {
if (cons == null) return ;
if (cons.obj == obj) {
// vorherige Cons-Zelle auf Nachfolgende zeigen lassen,
// somit faellt 'cons' aus der Liste
prev.next = cons.next;
if (foot == cons) // evtl. Fuss anpassen
foot = prev;
} else remove(cons, cons.next, obj);
}
public boolean isEmpty() { return head == null; }
public Object removeHead() {
if (head == null) return null;
Object res = head.obj;
if (head == foot) head = foot = null;
else head = head.next;
return res;
}
public static void main (String ... args) {
// Kleines Testprogramm fuer Listen:
ConsList l = new ConsList();
System.out.println("leer? " + l.isEmpty());
String s1 = "Hallo", s2 = "Welt";
l.insert(s1);
System.out.println("leer? " + l.isEmpty());
l.print();
l.insert(s2);
l.print();
l.remove(s2);
l.print();
l.append(s2);
l.print();
l.remove(s2);
l.remove(s1);
l.print();
System.out.println("leer? " + l.isEmpty());
}
}
