Bluedolphin
Grünschnabel
Hallo, ich bin grade dabei eine doppelt verkettete Liste zu implementieren und komme bei der letzten Methode einfach nicht weiter:
Wir sollen eine rekursive print-Methode schreiben, welche die Liste in umgekehrter Reihenfolge ausgibt. Das Ganze soll effizient implementiert werden, d.h. ein vorheriges Durchlaufen der Liste um das Ende zu suchen ist unzulässig. Es soll auch kein Zusatzfeld "foot" eingefügt werden.
Kann mir jemand dazu vll. einen Denkanstoß geben? Ich kann es mir nur so vorstellen, wie bei meiner Mathode print_rekursiv() (nur halt in umgekehrter Reihenfolge), aber da wird ja das Ende gesucht.
Danke schonmal im Voraus
Mein Code:
Wir sollen eine rekursive print-Methode schreiben, welche die Liste in umgekehrter Reihenfolge ausgibt. Das Ganze soll effizient implementiert werden, d.h. ein vorheriges Durchlaufen der Liste um das Ende zu suchen ist unzulässig. Es soll auch kein Zusatzfeld "foot" eingefügt werden.
Kann mir jemand dazu vll. einen Denkanstoß geben? Ich kann es mir nur so vorstellen, wie bei meiner Mathode print_rekursiv() (nur halt in umgekehrter Reihenfolge), aber da wird ja das Ende gesucht.
Danke schonmal im Voraus
Mein Code:
Code:
public class Student {
public class Student_Node {
String name;
int matr_nr;
Student_Node prev; // vorheriges Element
Student_Node next; // naechstes Element
Student_Node(String name, int matrikelnummer) {
this.name = name;
this.matr_nr = matrikelnummer;
}
}
Student_Node first;
Student_Node last;
Student_Node temp2;
// neues Element (Knoten) in die Liste einfuegen ----------------------------
void insert(String name, int matr_nr) {
// Erzeugen eines neuen Knotens
Student_Node studi = new Student_Node(name, matr_nr);
// falls Liste leer
if (first == null) {
studi.prev = studi;
studi.next = null;
first = studi;
temp2 = first;
}
else {
studi.next = first;
if (first != null) {
first.prev = studi;
}
first = studi;
studi.prev = last;
temp2 = first;
}
}
// Element aus Liste loeschen -----------------------------------------------
void delete(int matr_nr) {
Student_Node temp = first;
while (temp != null) {
if (temp.matr_nr == matr_nr) {
//wenn temp nicht erstes Element
if (temp.prev != null) {
(temp.prev).next = temp.next;
}
else {
//wenn temp erstes Element
first = temp.next;
}
//wenn temp nicht letztes Element
if (temp.next != null) {
(temp.next).prev = temp.prev;
}
}
temp = temp.next;
}
}
// Studenten nach Matrikelnummer suchen -------------------------------------
void search(int matr_nr) {
Student_Node temp = first;
boolean found = false;
// gesuchtes Element = erstes Element ? ...
if (temp.matr_nr == matr_nr) {
found = true;
}
// ...falls nicht laufe durch Liste
while (temp.next != null && temp.matr_nr != matr_nr) {
if (temp.next != null) {
temp = temp.next;
}
if (temp.matr_nr == matr_nr) {
found = true;
}
}
if (found == true) {
System.out.println("Folgender Student wurde gefunden: " + temp.name);
}
else {
System.out.println("Die Liste enthaelt keinen Studenten mit der Matrikelnummer " + matr_nr);
}
}
// Ausgabe der gesamten Liste (iterativ) ------------------------------------
void print_iterativ() {
Student_Node temp = first;
while(temp != null) {
System.out.println(temp.matr_nr + " - " +temp.name);
temp = temp.next;
}
}
// Ausgabe der gesamten Liste (rekursiv) -----------------------------------
void print_rekursiv() {
if (temp2 != null) {
System.out.println(temp2.matr_nr + " - " +temp2.name);
temp2 = temp2.next;
print_rekursiv();
}
}
// --------------------------------------------------------------------------
public static void main (String[] args) {
Student test = new Student();
test.insert("Max Mustermann", 123);
test.insert("Christian Mueller", 456);
test.insert("Stefanie Meier", 789);
test.print_iterativ();
// test.search(788);
System.out.println("");
// test.delete(123);
// System.out.println("");
test.print_iterativ();
// System.out.println("");
test.print_rekursiv();
}
}