Java Doppelt Verkettete Liste umdrehen

hubertus1990

Lt. Commander
Dabei seit
Sep. 2005
Beiträge
1.365
Hi Leute, stehe jetzt schon seit beinahe einer Stunde vor folgendem Problem:

Ich verwende in einem von mir geschriebenen Java-Programm eine doppelt verkettete Liste. Nun soll diese umgedreht werden, doch ich komme nicht dahinter wie ich das bewerkstelligen soll. Irgendetwas mit den zeigern auf die einzelnen Nodes mache ich falsch.

Mein Programm sieht so aus
Code:
public class LinkedList {
	
	private Node head; // verweis auf das erste element der liste
	private Node tail; // verweis auf das letzte element der liste


//methoden......

public void reverse() {

?
}


public class Node {
	
	public Node next; // verweis auf die nächste node, null falls keine vorhanden
	public Node prev; // verweis auf die vorhergehende node, null falls keine vorhanden
	public int val;
	
	Node (int val) { // konstruktor
		
		this.val = val;
	}
}

}
 

Rossie

Commodore
Dabei seit
Dez. 2010
Beiträge
4.101
Dass die Java Runtime dafür eine Funktion bietet, ist Dir bekannt?

Edit: Ah, ok, Du verwendest eine selbstgeschriebene Implementation?
 

Darlis

Commodore
Dabei seit
Jan. 2011
Beiträge
4.231
Einfach die Referenzen von next und prev, sowie head und tail vertauschen? Oder was hast du bisher probiert?
 

Rossie

Commodore
Dabei seit
Dez. 2010
Beiträge
4.101
Wie sieht der Code Deiner LinkedList denn komplett aus? Die grundsätzliche Vorgehensweise zum Austausch sollte klar sein?
 

hubertus1990

Lt. Commander
Ersteller dieses Themas
Dabei seit
Sep. 2005
Beiträge
1.365
Ich verwende 2 Print-Methoden um zu überprüfen, ob die Liste wirklich umgedreht wurde:

Code:
	public void printFront() { // printing the elements one after another, starting with head
		
		StringBuffer a = new StringBuffer();
		Node n = head;
		
		while(n != null) {
			
			a.append(n.val + " ");
			n = n.next;
		}
		
		System.out.println(a);
	}
	
	public void printBack() { // printing the elements one after another, starting with tail
		
		StringBuffer a = new StringBuffer();
		Node n = tail;
		
		while(n != null) {
			
			a.append(n.val + " ");
			n = n.prev;
		}
		
		System.out.println(a);
	}

	public void reverse() {

		Node save = tail;
		Node savetail = null;
		head = save;

		while (tail != null || save != null) {

			save.next = tail.prev;
			save.prev = tail.next;
			savetail = save;

			save = save.next;
			tail = tail.prev;

		}

		tail = savetail;

	}

Mit der oben gezeigten reverse() methode Sieht das Ergebnis so aus: (6 Nodes mit den values 0-5):

printFront();
Ergebnis: 0 1 2 3 4 5
printBack();
Ergebnis 5 4 3 2 1 0

reverse();

printFront();
Ergebnis: 5 4 3 2 1 0
printBack();
Ergebnis: 0
 

Darlis

Commodore
Dabei seit
Jan. 2011
Beiträge
4.231
Am Anfang setzt du save = tail, d.h. beide Variablen zeigen auf das selbe Objekt. Also steht in deiner Schleife zu Anfang dann so etwas:
Code:
save.next = save.prev;
save.prev = save.next;
Ohne eine dritte Variable wirst du hier nicht auskommen.
 

hubertus1990

Lt. Commander
Ersteller dieses Themas
Dabei seit
Sep. 2005
Beiträge
1.365
Hab das jetzt mal so geändert, das Ergebnis ist nach wie vor das gleiche, logischerweise.

Es scheint irgendein Problem mit den next und prev pointern von Tail zu geben, da nach dem umdrehen der liste nur noch eine 0 mit printBack() ausgegeben wird.
 

Darlis

Commodore
Dabei seit
Jan. 2011
Beiträge
4.231
Wie wärs damit:
Code:
Node node = head;
while (node != tail) {
	node.reverse() // vertauscht nur die Referenzen
	node = node.prev;
}
// node zeigt jetzt auf tail
node.reverse(); //letzter Vertausch

// head und tail vertauschen
tail = head;
head = node;
Nachtrag: Bei deinem Code ist die letzte Zeile in der while-Schleife der Fehler: tail = tail.prev;
Du hast ja die Referenzen von tail vertauscht hast, zeigt tail.prev auf das ehemalige tail.next, welches ja null ist.
 
Zuletzt bearbeitet:

hubertus1990

Lt. Commander
Ersteller dieses Themas
Dabei seit
Sep. 2005
Beiträge
1.365
Funktioniert so nicht, da reverse eine Klassenmethode ist/ sein soll und daher nicht auf ein Objekt angewendet werden kann.
 

Darlis

Commodore
Dabei seit
Jan. 2011
Beiträge
4.231
Ich sehe da keine Klassenmethoden....
Die Instanzmethode Node.reverse() musst ja noch implementieren oder du schreibst es aus, wie in deinem Code.
 

hubertus1990

Lt. Commander
Ersteller dieses Themas
Dabei seit
Sep. 2005
Beiträge
1.365
Habs jetzt auf ne andere Weise probiert, so klappts. Die variable "elements" ist ne Zählervariable die beinhaltet aus wie vielen Elementen die Liste besteht.

Code:
	public void reverse() {
		
		Node [] nodes = new Node[elements];
		
		for(int i = 0; i < elements; i++) {
			
			nodes[i] = new Node(head.val);
			head = head.next;		
		}
		
		head = null; tail = null;
		
		for(int i = elements - 1; i >= 0; i--) {
			
			if(i > 0) nodes[i].next = nodes[i-1];
			if(i < elements - 1) nodes[i].prev = nodes[i+1];
		}
		
		head = nodes[elements-1];
		tail = nodes[0];
		
	}
 

Darlis

Commodore
Dabei seit
Jan. 2011
Beiträge
4.231
Du machst aus der LinkedList eine ArrayList. Das ist wohl nicht ganz im Sinne des Erfinders, oder?

Möglicherweise bekommst du durch das Neuerstellen der Nodes auch unerwünschte Nebeneffekte, wenn du in einem anderen Teil deines Programms eine Referenz auf eine der Nodes speicherst.

reverse() ist übrigens immer noch keine Klassenmethode.
 

hubertus1990

Lt. Commander
Ersteller dieses Themas
Dabei seit
Sep. 2005
Beiträge
1.365
Naja das ich eine ArrayList draus mache ist etwas übertrieben, ich verwende nur zum umkehren ein Array. Nodes hinzufügen und wegnehmen funktionniert nach wie vor gleich und macht bisher keine Probleme... hab auch schon einige J-Unit Testfälle entworfen.
 

antred

Lt. Commander
Dabei seit
Juni 2010
Beiträge
1.288
Nur aus Interesse, gibt es einen bestimmten Grund, weshalb du mit einer eigenen Implementierung einspringst?
 

hubertus1990

Lt. Commander
Ersteller dieses Themas
Dabei seit
Sep. 2005
Beiträge
1.365
Ja, ich habe von der Uni aus die Aufgabe, alles selbst zu implementieren und keine vorgefertigten Methoden zu benutzen.
 
W

Whiz-zarD

Gast
Ich persönlich würde nicht die Referenzen (sprich deine Zeiger) verdrehen, sondern würde einfach ein Flag einbauen, ob die Liste in richtiger oder umgekehrter Reihenfolge bearbeitet werden soll.
Deine Elemente kennen das vorangegangene und das nächste Element, also wird das kein Problem sein.
Alles andere kostet nur Zeit und kann Fehler verursachen.
 

benneq

Admiral
Dabei seit
Juli 2010
Beiträge
9.242
+1 für Whiz-zarD, weil:
1. kostet das Umdrehen unnötig viel Zeit
2. ist das ganze fehleranfällig
3. braucht es vermutlich mindestens genau so viel Code wie ein Flag
 

Shagg

Ensign
Dabei seit
März 2010
Beiträge
215
Naja, er wird es schon umdrehen sollen. Aber das ist nu auch nicht so schlimm. ein einzelnes element hat ja immer vorgänger und nachfolger. dann speicherst du vorgänger einmal ab, setzt vorgänger = nachfolger, danach packst du in nachfolger, das zwischengespeicherte. das machst du auf jedem element und am ende vertauscht du noch head und tail. fertig!
 
W

Whiz-zarD

Gast
Habs jetzt auf ne andere Weise probiert, so klappts. Die variable "elements" ist ne Zählervariable die beinhaltet aus wie vielen Elementen die Liste besteht.
Wieso verwendest du dort ein Array? O_o

Hab da mal was zusammengebastelt, ohne zusätzliche Variablen.
Scheint in einem kurzen Test zu funktionieren.

Naja, er wird es schon umdrehen sollen. Aber das ist nu auch nicht so schlimm. ein einzelnes element hat ja immer vorgänger und nachfolger. dann speicherst du vorgänger einmal ab, setzt vorgänger = nachfolger, danach packst du in nachfolger, das zwischengespeicherte. das machst du auf jedem element und am ende vertauscht du noch head und tail. fertig!
Letzendlich sollte man sich aber fragen, wozu der Sinn hier eine doppeltverkettete Liste macht? Denn nicht ohne Grund kann man hier vor- und zurückgehen. Dann sollte man auch dieses Feature verwenden. Ansonsten kann man ja auch gleich eine einfachverkettete Liste nehmen. Dann spart man sich wenigstens eine Referenz pro Element.
 

Anhänge

Top