Doppelt verkettete Liste implementieren

Status
Nicht offen für weitere Antworten.

BlueDolphin

Mitglied
Hallo,

ich bin grade dabei eine doppelt verkettete lineare Liste zu implementieren: insert(), search() und die Ausgabe hauen schon hin, aber bei der delete()-Mathode bin ich so langsam am verzweifeln ???:L

Es funktioniert zwar für den Fall, dass das zu löschende Element an der ersten Stelle, bzw. in der Mitte steht, jedoch gibt er mir dann das letzte Element immer 2x aus?

PS: Der Fall, "Element steht am Ende" wird noch nicht abgefragt (wollte es erstmal so testen), es geht hier erstmal nur um den Fall "Element am Anfang" oder "Element irgendwo in der Mitte":

hier mein Code:

Code:
public class CD_Archiv { 

   public class CD_Node {
   	
    String title; 
    String artist; 
      
    CD_Node prev; // vorheriges Element 
    CD_Node next; // naechstes Element
       
    CD_Node(String titel, String interpret) {
    	
    	 this.title = titel; 
    	 this.artist = interpret; 
      
    }
    } 
    
   CD_Node first; // erstes Element 
   CD_Node last;  // letztes Element
   int count = 0; 
    
    
   // neues Element (Knoten) am Anfang in die Liste einfuegen ----------------
   
   void insert(String title, String artist) {
   	
   	 CD_Node cd = new CD_Node(title, artist); // Erzeugen eines neuen Knotens 
   	 
   	 // falls Liste leer
   	 if (first == last) {
   	 	
   	 	cd.prev = cd;
   	 	cd.next = last;
   	 	first = cd;
   	 }
   	 
   	 cd.next = first;
   	 
   	 if (first != last) {
   	 		
    	first.prev = cd;
   	 	first = cd;
    	cd.prev = last;
   	 }
   	 count++; 
   }
   
   // --------------------------------------------------------------------------
   
   
   // Element aus Liste loeschen -----------------------------------------------
   
   void delete(String artist) {
   	
    CD_Node temp = first; 
       
      for (int i = 1; i <= count; i++){ 
         
         if (artist.equals(temp.artist)) { 
               
               System.out.println(temp.artist); 
              	
               //wenn temp nicht erstes Element...	
			   if (temp.prev != last) {
   		
   					(temp.prev).next = temp.next;
   			   }
   			   else {
   					
   					//wenn temp erstes Element...
   					first = temp.next;
   			   }
   				
   			   //wenn temp nicht vorletztes Element		
   			   if (temp.next != last) {
   		
   					(temp.next).prev = temp.prev;
   			   }
               
               	System.out.println(temp.artist); 
            
         } 
         
         temp = temp.next; 
     }  	
   }
   
   
   // Ausgabe der gesamten Liste (iterativ) ------------------------------------
   
   void print_iterativ() {
  	
  	 CD_Node temp = first;
  	
  	 for (int i = 1; i <= count; i++) {
  		
  	    System.out.println("Nr." + i + " : " + temp.artist + " - " +temp.title);
  		temp = temp.next;
  	 }
   }
   
   // --------------------------------------------------------------------------
   
   
  public static void main (String[] args) {
  	
  	CD_Archiv test = new CD_Archiv();
  	
  	test.insert("Best Of", "Bon Jovi");
  	test.insert("Stadium Arcadium", "Red Hot Chili Peppers");
  	test.insert("Around the World", "R.E.M.");
  	test.print_iterativ();
//	test.title_search("Bon Jovi");
  	test.delete("R.E.M.");
  	test.print_iterativ();
  }
}

hab die search() rausgenommen, ist ja hier nicht wichtig

Danke schonmal im Voraus
 

PyroPi

Aktives Mitglied
Hi,

liegt einfach daran, daß du in deiner delete-Methode beim Löschen an geeigneter Stelle ein count-- einfügen muß. Wenn du in der print_iterativ-Methode die Schleife länger als count laufen läßt, listet er dir beliebig oft das letzte Element in der Liste auf.

Günstiger wäre es glaub ich, wenn der Vorgänger vom ersten und der Nachfolger vom letzten Element auf null zeigen würden, dann wüßtest du genau wann die Liste Schluß ist (späterstens bei einer NullPointerException :wink: ). Irgendwie sind mir die Zeilen 43-45 nicht ganz klar, willst du die Liste zyklisch verketten?

Viele Grüße,

PyroPi
 

BlueDolphin

Mitglied
lol...och nee son dummer Fehler und ich find ihn net...thx

über deinen vorschlag denk ich nach, muss jetzt aber erstmal los...
 

BlueDolphin

Mitglied
So,

delete() funktioniert nun auch richtig. Ich habe jetzt auch den Counter rausgenommen, den braucht man eh garnet.

Bei der letzten Methode komme ich aber 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 Methode 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();
  }
}
 

Leroy42

Top Contributor
Ich verstehe nicht, wo die Schwierigkeit ist. Du hast doch bereits einen Zeiger auf
das letzte Element ???:L

Code:
public void printRek() {
  Studen cur = last;
  while (cur != null) {
    System.out.println(cur);
    cur = cur.prev;
  }
}
 

Leroy42

Top Contributor
Oh, sorry: die Methode soll ja rekursiv sein :oops:
Code:
public void printRek() {printRek(last);}
public void printRek(Student studi) {
  if (studi != null) {
    System.out.println(studi);
    printRek(studi.prev);
  }
}
 

Leroy42

Top Contributor
Noch ein Hinweis:

Code:
  void print_iterativ() { 
      
      Student_Node temp = first;    
         
     while(temp != null) { 
         
         System.out.println(temp.matr_nr + " - " +temp.name); 
        temp = temp.next; 
      } 
   }

Es ist mehr OOP-Stil dem Studenten selbst seine Ausgabe bestimmen zu lassen:

Code:
void print_iterativ() { 
  Student_Node temp = first;    
    while (temp != null) { 
      System.out.println(temp); 
      temp = temp.next; 
    } 
}

und in Student-Node
Code:
public String toString() {
  return "Student(" + temp.matr_nr + " - " +temp.name + ")";
}
 

BlueDolphin

Mitglied
edit: Quatsch

erstmal vielen Dank (auch für die Hinweise) ich habe "last" aber bei der insert-Methode noch garnicht gesetzt, d.h. es ist von anfang an null ... dann muss ich also nur noch last in der insert-Methode setzen um das Ende nicht suchen zu müssen...danke nochmal
 

BlueDolphin

Mitglied
Hallo Leroy42,

meine Antwort von eben war Quatsch. Schieben wir´s mal auf die späte Stunde :shock: .

Deine Lösung ist schon richtig, aber es soll bei der Lösung auf ein foot- bzw. last-Element, also auf einer Zeiger auf das letzte Element verzichtet werden.
Ebenso soll die Liste nicht durchlaufen werden, um das Ende zu finden.

Hast Du (oder jemand anders) da vll. noch ne Idee?

Danke
 

Leroy42

Top Contributor
Ich glaube, ich weiß worauf dein Lehrer hinaus will. :cool:

Ihm geht's darum, euch auf den Unterschied zwischen
tail-rekursiven Algos und den anderen (keine Ahnung mehr, wie die heißen :shock: )
aufmerksam zu machen.

In deinem Fall, ersetze einfach

Code:
public void printRek() {printRek(last);}
public void printRek(Student studi) {
  if (studi != null) {
    System.out.println(studi);
    printRek(studi.prev);
  }
}

durch

Code:
public void printRek() {printRek(first);}
public void printRek(Student studi) {
  if (studi != null) {
    printRek(studi.next);
    System.out.println(studi);
  }
}

und schon erfolgt die Ausgabe in umgekehrter Reihenfolge.

Sowas ähnliches wurde mir übrigens mal als Bewerbungsaufgabe
für einen Job während der Semesterferien gestellt:

Semesterjob-Bewerber-Tester mit ständig rumrennender Katze hat gesagt.:
Schreib' mal eine rekursive Funktion in C, die eine Ganzzahl bekommt
und diese ziffernweise ausgibt, ohne andere Operationen als modulo (%)
zu benutzen und ohne Schleifen.

Interessant war, daß es ihm völlig egal war, daß ich noch nie etwas mit der
Sprache C zu tun hatte; ihm kam es darauf an, zu beobachten, wie ich an diese
Aufgabe herangehe...
 

BlueDolphin

Mitglied
boah, vielen Dank ... haut hin ... da wär ich nie drauf gekommen

Ihm geht's darum, euch auf den Unterschied zwischen
tail-rekursiven Algos und den anderen (keine Ahnung mehr, wie die heißen )
aufmerksam zu machen.

vll. fällt ja noch jemandem ein, wie die heissen :wink: würd mich mal interessieren
 

Leroy42

Top Contributor
Ich glaube, die heißen einfach nur, allgemein-rekursiv.

Der Unterschied ist einfach, daß tail-rekursive Funktionen,
also Funktionen die nur einen direkt-rekursiven Aufrug als
letzte Anweisung haben, vom Compiler/Interpreter automatisch
in eine gleichwertige, iterative Variante transformiert werden können,
während dies für allgemein-rekursive, nicht per Programm möglich ist.

BlueDolphin hat gesagt.:
boah, vielen Dank ... haut hin ... da wär ich nie drauf gekommen

Tröste dich; jeder fängt mal an und muß erst ein Gefühl dafür bekommen.

Übrigens habe ich, die oben beschriebene Aufgabe, auch nicht vollständig lesen
können. Aber meine Art der Lösungssuche hat mir stande pedes eine Einstellung,
und damit auch eine spätere Verzögerung beim Studiumfortschreiten, verschafft.

Die haben mich nämlich am Semesterferienende erpreßt, stundenweise weiter
zu arbeiten. Und zwar auf ganz gemeine Art erpreßt : Mit Geld! :shock:
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
Y Einfügen in eine doppelt verkettete Liste Java Basics - Anfänger-Themen 8
A Doppelt verkettete Liste rückwärts ausgeben Java Basics - Anfänger-Themen 17
D Doppelt Verkettete Zirkular-Liste Java Basics - Anfänger-Themen 1
B Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 8
scratchy1 doppelt verkettete Liste testen Java Basics - Anfänger-Themen 8
B Doppelt Verkettete Liste - Ist alles gut so? Java Basics - Anfänger-Themen 3
U Datentypen Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 13
J Methoden Doppelt verkettete Liste remove(Object) Java Basics - Anfänger-Themen 8
B OOP Über eine doppelt verkettete Liste iterieren Java Basics - Anfänger-Themen 4
L Doppelt verkettete Liste Java Basics - Anfänger-Themen 6
R doppelt verkettete Liste aus Arrays erstellen Java Basics - Anfänger-Themen 1
S Doppelt verkettete Liste Java Basics - Anfänger-Themen 3
G Doppelt Verkettete Liste Java Basics - Anfänger-Themen 2
A Doppelt Verkettete Liste Java Basics - Anfänger-Themen 16
E doppelt verkettete liste Java Basics - Anfänger-Themen 10
E Datentypen Doppelt verkettete Liste Java Basics - Anfänger-Themen 10
P Einfügen in doppelt verkettete Liste Java Basics - Anfänger-Themen 7
S Queue als doppelt verkettete Liste Java Basics - Anfänger-Themen 2
N doppelt verkettete liste einfügen Java Basics - Anfänger-Themen 7
K Datentypen Einfach/Doppelt verkettete Liste Java Basics - Anfänger-Themen 4
W Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 2
G Doppelt verkettete, generische Liste Java Basics - Anfänger-Themen 11
D doppelt verkettete Liste Java Basics - Anfänger-Themen 16
S Doppelt Verkettete Liste Java Basics - Anfänger-Themen 7
M Doppelt verkettete Liste Zeiger Vorgänger beim Einfügen Java Basics - Anfänger-Themen 2
J doppelt verkettete Liste Java Basics - Anfänger-Themen 5
L doppelt verkettete Liste Java Basics - Anfänger-Themen 6
B Doppelt verkettete Liste Java Basics - Anfänger-Themen 16
R Datentyp Ring - zyklisch doppelt verkettete Liste - HILFE! Java Basics - Anfänger-Themen 12
R doppelt verkettete Liste Java Basics - Anfänger-Themen 8
F doppelt verkettete liste! Java Basics - Anfänger-Themen 8
R doppelt verkettete azyklische Liste Java Basics - Anfänger-Themen 2
T Klasse in Java für doppelt verkettete Listen Java Basics - Anfänger-Themen 4
H Doppelt verkettete Listen Java Basics - Anfänger-Themen 2
S doppelt verkettete Listen Java Basics - Anfänger-Themen 4
X Vererbung: Doppelt verkettete Listen Java Basics - Anfänger-Themen 16
O Doppelt verkette Liste Element löschen Java Basics - Anfänger-Themen 15
J Doppelt verkette Liste ich bitte um Hilfe Java Basics - Anfänger-Themen 4
I Input/Output Code wird doppelt ausgeführt Java Basics - Anfänger-Themen 3
N package wird doppelt im exporer angezeigt Java Basics - Anfänger-Themen 2
L Wie frage ich ab, ob in einem Array, Werte doppelt vorkommen? Java Basics - Anfänger-Themen 4
J Fehler beim generieren von 4 Zufallszahlen Zahl doppelt ist eigentlich ausgeschlossen Java Basics - Anfänger-Themen 9
T Löschen in doppelt verketteter Liste Java Basics - Anfänger-Themen 1
L Input/Output Println wird doppelt ausgeführt Java Basics - Anfänger-Themen 11
D Interface Frame doppelt durch Aufruf der GUI Klasse Java Basics - Anfänger-Themen 1
B BufferedReader gibt Datei-Inhalt doppelt aus Java Basics - Anfänger-Themen 3
M Liste Implementation, doppelt next() Java Basics - Anfänger-Themen 13
D Klassen Doppelt so viele Elemente in Arraylist ? Java Basics - Anfänger-Themen 4
Salo Datentypen "Doppelt" List(e) ("gesucht") Java Basics - Anfänger-Themen 6
L do-while-Schleife läuft doppelt, try catch fehler Java Basics - Anfänger-Themen 12
T Java Methode wird unerwünscht doppelt aufgerufen?! Java Basics - Anfänger-Themen 4
OnDemand Doppelt Werte CSV Java Basics - Anfänger-Themen 2
llabusch Verkette Listen - Einfach und Doppelt Java Basics - Anfänger-Themen 3
N Erste Zeile bei BufferedReader doppelt lesen? Java Basics - Anfänger-Themen 2
E Erste Schritte Sortieren von Objekten in doppelt-verlinkter Liste Java Basics - Anfänger-Themen 9
S Methoden Methode wird doppelt aufgerufen ... Java Basics - Anfänger-Themen 5
J Mehrere Zufallszahlen erzeugen, aber keine darf doppelt erzeugt werden - Wie? Java Basics - Anfänger-Themen 5
B Doppelt gekettete Listen Java Basics - Anfänger-Themen 4
G PropertyChangeListener empfängt Events doppelt Java Basics - Anfänger-Themen 5
L doppelt verkette Liste Java Basics - Anfänger-Themen 5
H Fenster doppelt gezeichnet. Java Basics - Anfänger-Themen 2
G Einfügen aus Zwischenablage - alles doppelt? Java Basics - Anfänger-Themen 2
G JFileChooser kommt doppelt Java Basics - Anfänger-Themen 3
N Nullpointerexception bei Doppelt verketteter Liste Java Basics - Anfänger-Themen 7
M Listen richtig doppelt verkettet? Java Basics - Anfänger-Themen 13
D Exceptions in doppelt verketteter Liste Java Basics - Anfänger-Themen 5
C verify() wird doppelt aufgerufen (JTable + InputVerifier) Java Basics - Anfänger-Themen 8
H doppelt verkette liste Java Basics - Anfänger-Themen 2
L rückwärtsausgeben einer doppelt verketteten liste Java Basics - Anfänger-Themen 2
G JList und ListCellRenderer - Vector erscheint doppelt Java Basics - Anfänger-Themen 6
G JComboBox gibt SelectedItem immer doppelt aus Java Basics - Anfänger-Themen 4
B Array doppelt Felder löschen Java Basics - Anfänger-Themen 27
M Code wird doppelt ausgeführt Java Basics - Anfänger-Themen 2
R Zeilen aus datei lesen + doppelt gespeichert? Java Basics - Anfänger-Themen 3
G Trotz Abfrage immer noch Zahlen doppelt Java Basics - Anfänger-Themen 3
R Benutzerregistrierung: Doppelt registriert. Java Basics - Anfänger-Themen 8
M Verkettete Liste Java Basics - Anfänger-Themen 1
S Einfach-Verkettete-Listen Ausgabe zeigt nur 1. und letzte instanz Java Basics - Anfänger-Themen 2
H Java verkettete Liste, Wert eines Index zurückgeben Java Basics - Anfänger-Themen 1
Igig1 Autoparkplatz verkettete Liste erstes und letztes Auto Java Basics - Anfänger-Themen 13
R Rückgabe: verkettete Liste Java Basics - Anfänger-Themen 2
R einfach verkettete Liste Java Basics - Anfänger-Themen 1
R einfach verkettete Liste Java Basics - Anfänger-Themen 12
B Verkettete Liste durchgehen und einzelne Elemente in neue Liste tun Java Basics - Anfänger-Themen 9
B Bin komplett am verzweifeln :( Verkettete Liste die Objekte hat Attribut auslesen Java Basics - Anfänger-Themen 14
V einfach verkettete Listen Java Basics - Anfänger-Themen 10
A Verkettete Liste Java Basics - Anfänger-Themen 2
L verkettete Liste Java Basics - Anfänger-Themen 15
R Methoden Entferne alle identische Knoten (Typ String) aus verkettete Liste Java Basics - Anfänger-Themen 8
C Methoden Über eine einfach verkettete Liste Java Basics - Anfänger-Themen 8
H Verkettete Liste Java Basics - Anfänger-Themen 7
N Verkettete liste rückwärts ausgeben Java Basics - Anfänger-Themen 18
K Verkettete Liste und seine Methoden Java Basics - Anfänger-Themen 1
A Was könnten typische Prüfungsaufgaben zum Thema lineare, verkettete Listen sein? Java Basics - Anfänger-Themen 5
N Verkettete Liste implementieren Java Basics - Anfänger-Themen 5
O Einfach verkettete Liste - Revert Methode Java Basics - Anfänger-Themen 1
G Verkettete Liste - Neu erzeugte Elemente werden nicht ausgegeben Java Basics - Anfänger-Themen 5
S Einfach verkettete Liste Element an bestimmter Position einfügen Java Basics - Anfänger-Themen 24
C Verkettete Liste - sortiert einfügen Java Basics - Anfänger-Themen 7
R Erste Schritte Verkettete Liste will einfach nicht in meinen Schädel Java Basics - Anfänger-Themen 11

Ähnliche Java Themen

Neue Themen


Oben