Java Doppelt Verkettete Liste umdrehen

[hubertus1990]

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

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]

Dass die Java Runtime dafür eine Funktion bietet, ist Dir bekannt?

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

 

[hubertus1990]

Genauso ist es

 

[Darlis]

Einfach die Referenzen von next und prev, sowie head und tail vertauschen? Oder was hast du bisher probiert?

 

[Rossie]

Wie sieht der Code Deiner LinkedList denn komplett aus? Die grundsätzliche Vorgehensweise zum Austausch sollte klar sein?

 

[hubertus1990]

Ich verwende 2 Print-Methoden um zu überprüfen, ob die Liste wirklich umgedreht wurde:

	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]

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:

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

Ohne eine dritte Variable wirst du hier nicht auskommen.

 

[hubertus1990]

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]

Wie wärs damit:

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.

 

[hubertus1990]

Funktioniert so nicht, da reverse eine Klassenmethode ist/ sein soll und daher nicht auf ein Objekt angewendet werden kann.

 

[Darlis]

Ich sehe da keine Klassenmethoden....
Die Instanzmethode Node.reverse() musst ja noch implementieren oder du schreibst es aus, wie in deinem Code.

 

[hubertus1990]

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.

	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]

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]

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]

Nur aus Interesse, gibt es einen bestimmten Grund, weshalb du mit einer eigenen Implementierung einspringst?

 

[hubertus1990]

Ja, ich habe von der Uni aus die Aufgabe, alles selbst zu implementieren und keine vorgefertigten Methoden zu benutzen.

 

[Whiz-zarD]

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]

+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]

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!

 

[Whiz-zarD]

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.