Zweifach-verkettete Liste umkehren

Burned

Mitglied
Hallo zusammen,
ich soll eine zweifach verkettete Liste schreiben, an der sich an einer gewünschten Stelle m ein neues Element einsetzen lässt. So weit kein Problem.
Danach soll ich die gesamte Liste allerdings umkehren und ausgeben. Ich hab das ganze geschrieben, verliere aber immer alle Elemente, außer das, dass ich am ende der Liste stehen hab.

Die entsprechenden Code-Zeilen:

Java:
	//Umdrehen der Liste
	   public void reverse() {
		   Elem pos;
		   Elem temp;
		   Elem temp2;
		   Elem nStart;
		   nStart = ende;
		   temp = ende;
		   temp2 = ende;
		   pos = ende;
		   
		   while (temp != null) {
			   temp2 = pos.getNext();
			   pos.setNext(pos.getPrev());	
			  
			   temp = temp.getNext();
			   pos.setPrev(temp2);
			   
			   
			   pos = pos.getNext();			   
		   }
		  
		   ende = temp2;
		   start= nStart;
		   start.setPrev(null);
		   ende.setNext(null);
		   
		   
	   }

Ich hab mir das ganze schon mit Stift und Papier aufgemalt und geguckt, was sich da in den einzelnen Schritten tut, ob ich einen der Pointer vielleicht falsch setze oder vergesse, aber ich finde meinen Denkfehler einfach nicht.. Kann mir jemand von euch auf die Sprünge helfen?
 
Java:
           temp2 = ende;
           pos = ende;
           
           while (temp != null) {
               temp2 = pos.getNext();

temp2 = ende; Unnötig - wird eh gleich wieder überschrieben

pos=ende;
temp2=pos.getNext() - ähm next vom letzten ist normalerweise null

Also so ganz ohne Debugger und ganzen Sourecode sehe ich nicht konkret was du machen willst, aber vielleicht sieht es jemand anderes.
Kannst ja trotzdem mal den Code der ganzen Klasse reinstellen.
 
welchen Sinn hat die temp-Variable? sie wird nirgendwo benutzt,
Zeile 23 ende = temp2; scheint mir falsch, temp2 zeigt doch immer auf das vorletzte Element,

von start= nStart = ehemaliges Ende sollte am Anfang aber alles richtig laufen,
mit meinem Kopf kann ich vorerst keinen Verknüpfungsfehler sehen,
besser wäre ein vollständiges Programm mit main-Methode für eine Test-Ausgangsliste,
vielleicht war die schon falsch verknüpft (in Rückrichtung) so dass es jetzt auffällt

allgemein könntest du auch alles selber mit Log rauskriegen, benenne alle Elemente eindeutig, logge jedes Setzen eines Links mit Text a la
"Prev von Element 7 zeigt nun auf Element 6" usw.
und gib schon während des Durchlaufs am Ende jeder Runde eine Ausgabe der Schleife vom ehemaligen Ende aus soweit wie vorhanden
 
In den Verknüpfungen vorher seh ich keine Fehler.. hab mir da auch immer alles einzeln ausgeben lassen.. Ich geb euch mal den gesamten Code, den ich bis jetzt geschrieben habe:

Java:
public class Elem {

	Elem () { }

	private int value;
	private Elem next;
	private Elem prev;
	
	public void setValue (int newValue) {
		value = newValue;
	}
	
	public int getValue () {
		return value;
	}
	
	public void setNext (Elem nextElem ) {
		next = nextElem;
	}
	
	public Elem getNext () {
		return next;
	}
	
	public void setPrev (Elem prevElem) {
		prev = prevElem;
	}
	
	public Elem getPrev () {
		return prev;
	}
	
}

Das eigentlich Porg mit Beschreibung wie ich mir reverse() gedacht habe:
Java:
public class Aufgabe62 {
	
	private Elem start;
	private Elem ende;
	private int count = 0;

	//Zählt die Elemente, die vom User hinzugefügt werden
	public void Counter () {
			count++;
	}
	
	//Bei leerer Liste	
	public void sortIn (Elem newElem) {
		if (start == null) {
			newElem.setNext (null);
			newElem.setPrev (null);
			start = newElem;
			ende = newElem;
			
			Counter();
			System.out.println("sortIn");
			}
	}
	
	//Einsortieren an einer gewünschten Stelle m
	public void insert (Elem InsElem, int m) {
		int help = 0;
		Elem pos;
		
		if ( m <= 0) {
			InsElem.setNext(start);
			InsElem.setPrev(null);
			
			start = InsElem;
			ende = start;
			Counter();
			System.out.println("an den Anfang der Liste");
		}
		
		else if (m > count) {			
			ende.setNext(InsElem);
			InsElem.setPrev(ende);
			
			ende = InsElem;
			Counter();	
			System.out.println("an das Ende der Liste");
		}
		
		else {
			pos = start;
			while (help < m) {
				pos = pos.getNext();
				help++;
			
			InsElem.setNext(pos);
			InsElem.setPrev(pos.getPrev());
			pos.getPrev().setPrev(InsElem);
			pos.getPrev().setNext(InsElem);
			System.out.println("in die Mitte der Liste");
		}
		}
	}
	
	//Umdrehen der Liste
	   public void reverse() {
		   Elem pos;
		   Elem temp;
		   Elem temp2;
		   Elem nStart;
		   nStart = ende;
		   temp = ende;
		   temp2 = ende;
		   pos = ende;
		   
		   while (temp != null) {
			   
			   //temp2 soll den next-Pointer des jetzigen Elements annehmen
			   temp2 = pos.getNext();
			   //Next-Pointer wird auf jetzigen Previous umgebogen
			   pos.setNext(pos.getPrev());	
			   //temp wird auf nächstes(vorheriges) Element gesetzt
			   temp = temp.getNext();
			   //der previous-Pointer wird auf den alten Next-Pointer umgebogen
			   pos.setPrev(temp2);
			   //pos wird auf nächstes(vorheriges) Element gesetzt
			   pos = pos.getNext();			   
		   }
		  
		   ende = temp2;
		   start= nStart;
		   start.setPrev(null);
		   ende.setNext(null);
		   
		   
	   }
	   
	public String toString() {
		String out = "";
		
		for (Elem pos = start; pos != null; pos = pos.getNext()) {
			out = out + pos.getValue() + "\n";
			System.out.println("toString");
		}
		
		return out;
	}
	
}

Und die Main:
Java:
import javax.swing.*;
public class MainList {
	public static void main(String [] args){
		
		Aufgabe62 liste = new Aufgabe62();
		
		Elem newElement1 = new Elem();
		newElement1.setValue(10);
		liste.insert(newElement1, 0);
		JOptionPane.showMessageDialog(null, liste.toString());
		
		Elem newElement2 = new Elem();
		newElement2.setValue(14);
		liste.insert(newElement2, 2);
		JOptionPane.showMessageDialog(null, liste.toString());
		
		Elem newElement3 = new Elem();
		newElement3.setValue(12);
		liste.insert(newElement3, 1);
		JOptionPane.showMessageDialog(null, liste.toString());
		
		liste.reverse();
		JOptionPane.showMessageDialog(null, liste.toString());
		
		
	}
}
 
verwende folgende toString()-Methode für die Liste und korrigiere dann erstmal das Original oder stelle notfalls Fragen dazu
Java:
    public String toString()   {
        String out = "toString:\n";
        for (Elem pos = start; pos != null; pos = pos.getNext())  {
            out += pos.getValue();
            out += ", prev: " + (pos.getPrev() == null ? "null" : pos.getPrev().getValue());
            out += ", next: " + (pos.getNext() == null ? "null" : pos.getNext().getValue());
            out += "\n";
        }
        return out;
    }
Ausgabe derzeit für die 10, 12, 14-Liste
Code:
toString:
10, prev: 12, next: 12
12, prev: 10, next: 14
14, prev: 10, next: null
wie vermutet Rückrichtung nicht so toll (bin stolz 😉 )
 
So, hab meine Fehler gefunden und behoben, wurde aber auch Zeit. 😛

Hier der Vollständigkeit halber noch einmal der (jetzt laufende) Quellcode des Programms:

Java:
public class Aufgabe62 {
	
	private Elem start;
	private Elem ende;
	private int count = 0;

	//Zählt die Elemente, die vom User hinzugefügt werden
	public void Counter () {
			count++;
	}
	
	//Bei leerer Liste	
	public void sortIn (Elem newElem) {
		if (start == null) {
			newElem.setNext (null);
			newElem.setPrev (null);
			start = newElem;
			ende = newElem;
			
			Counter();
			System.out.println("sortIn");
			}
	}
	
	//Einsortieren an einer gewünschten Stelle m
	public void insert (Elem InsElem, int m) {
		int help = 0;
		Elem pos;
		
		if ( m <= 0) {
			InsElem.setNext(start);
			InsElem.setPrev(null);
			
			start = InsElem;
			ende = start;
			Counter();
		}
		
		else if (m > count) {			
			ende.setNext(InsElem);
			InsElem.setPrev(ende);
			
			ende = InsElem;
			Counter();
		}
		
		else {
			pos = start;
			while (help < m) {
				pos = pos.getNext();
				help++;
			
			InsElem.setNext(pos);
			InsElem.setPrev(pos.getPrev());
			pos.getPrev().setNext(InsElem);
			pos.setPrev(InsElem);
		}
		}
	}
	
	//Umdrehen der Liste
	   public void reverse() {
		   Elem pos;
		   Elem temp;
		   Elem nStart;
		   nStart = ende;
		   temp = ende;
		   pos = ende;
		   
		   while (pos != null) {
			   System.out.println("durchlauf: "+x);
			   //temp soll den next-Pointer des jetzigen Elements annehmen
			   temp = pos.getNext();
			   //Next-Pointer wird auf jetzigen Previous umgebogen
			   pos.setNext(pos.getPrev());	
			   //temp wird auf nächstes(vorheriges) Element gesetzt
			   pos.setPrev(temp);
			   //pos wird auf nächstes(vorheriges) Element gesetzt
			   pos = pos.getNext();	
			  // System.out.println(pos.getNext().getValue());
		   }
		  
		   ende = temp;
		   start = nStart;
	   }
	   
	    public String toString()   {
	        String out = "toString:\n";
	        for (Elem pos = start; pos != null; pos = pos.getNext())  {
	            out += pos.getValue();
	            out += ", prev: " + (pos.getPrev() == null ? "null" : pos.getPrev().getValue());
	            out += ", next: " + (pos.getNext() == null ? "null" : pos.getNext().getValue());
	            out += "\n";
	        }
	        return out;
	    }
	
}

Vielen dank für die Hilfe! =)
 

Neue Themen


Zurück
Oben