doppelt verkettete liste

[ETlearner]

hallo,
ich muss in meiner hausaufgabe mit einer klasse für doppeltverkettete Listen arbeiten.
es gibt 4 methoden, die ich implementieren muss :
1. Implementieren Sie die Methode void appendHead(T element), die ein neues Element
an den Anfang der Liste anfugt.
2. Implementieren Sie die Methode T popHead(), die das Element am Anfang der Liste
zuruckgibt und entfernt.
3. Implementieren Sie die Methode void appendTail(T element), die ein neues Element
an das Ende der Liste anfugt.
4. Implementieren Sie die Methode T popTail(), die das Element am Ende der Liste zuruckgibt
und entfernt.

appendhead und appendtail funktionieren.

doch bei der methode poptail wird das vorletzte element gelöscht anstatt das letzte...
und bei der pophead-methode das zweite element anstatt das erste...

pophead-Methode:

  T popHead(){
	if(head==null){
		return null;}
	
	else{
		Node a= head.next;
		head.next=head.next.next;
		head.next.prev=head;
		return a.value;
		
		}
	
	}

poptail-Methode:

 T popTail(){
	if (head==null){
		return null;
		}
	else{
		Node a= tail;
		tail.prev.next=null;
		return a.value;
		}
		}

wo ist mein fehler?

danke im voraus
mfg

 

[SlaterB]

was soll man da sagen, der Code steht da und so ist es auch?!

wenn die Liste mit drei Elementen A, B, C beginnt, wovon A der head ist,
dann heißt:
> head.next=head.next.next;
lasse A auf C zeigen,

also wird B, das bisherige head.next, herausgeschnitten, dessen value gibst du ja auch zurück,
das return ist quasi direkt als 'head.next.value' abzulesen

was ist daran jetzt als Rätsel zu lösen?
das erste Element ist head, die Rückgabe head.value wäre vom ersten Element, head.next.value ist vom zweiten,

genauso deutlich könntest du eine Methode

int a = ..
int b = ..;
return a;

schreiben und fragen warum a und nicht b zurückgegeben wird,
eben genau weil du es so gecodet hast, ohne versteckte Rätsel, einfach von dem einen zum anderen wechseln..,

dass es bei deiner Methode nicht ganz leicht ist, head zu löschen, ist klar,
wenn du dabei Probleme oder Fragen hast, kann man dazu vielleicht nachdenken,
aber die Frage ob das erste oder zweite.., die läßt ja eher vermuten dass du keine Zeile des Codes verstehst/ selber geschrieben hast

 

[Sesostris]

Das erinnert schon sehr stark an deine letzte Hausaufgabe: Listen und Generics
Bereits damals hast du viele hilfreiche Antworten bekommen, die - wenn ich mir deine Codefragmente so ansehe - bei dir nicht wirklich angekommen sein können. Beschäftige dich lieber mit einer einfach verketteten Liste, bevor du dich an mehrfach verkettete Listen wagst.

Als Tipp kann ich dir noch mitgeben, dass du bei deinen pop-Methoden immer drei Fälle unterscheiden musst:
1. leere Liste
2. einelementige Liste
3. mehrelementige Liste

Das kann aber nur funktionieren, wenn head und tail in ihren jeweiligen push-Methoden richtig gesetzt wurden - was ich bei dir mangels Code leider nicht überprüfen kann.

 

[ETlearner]

hast recht... die frage war wirklich unnötig

ich komme nicht darauf wie ich head löschen kann...

ich würde es mir so denken:
sei A B C die liste...
zuerst speicher ich die daten von A ab...
durch head.next.prev=null; müssten die daten von head ja eigentlich gelöscht werden oder?...
dann gebe ich die daten von A zurück

T popHead(){
	if(head==null){
		return null;}
	
	else{
		Node a= head; 
		head.next.prev=null;
		
		return a.value;
		
		}
	
	}

 

[ETlearner]

und hier ist die ganze klasse

public class DoubleLinkedList <T> {
	
	
	public class Node{	
		private T value;
		private Node next;
		private Node prev;
		public Node(T value, Node next, Node prev){
			this.value=value;
			this.next=next;
			this.prev=prev;
			}
	}
	
private Node head;
private Node tail;
public DoubleLinkedList(){
	head=null;
	tail=null;
	}
public void appendHead (T value){
	head=new Node(value, head, null);
	if(tail==null){
			tail=head;}
	else{
			head.next.prev=head;
			}
	}
	
T popHead(){
	if(head==null){
		return null;}
	
	else{
		Node a= head;
		head.next.prev=null;
		
		return a.value;
		
		}
	
	}

public void appendTail(T value){
	tail= new Node(value, null, tail);
	if(head==null){
		head=tail;}
	else{
		tail.prev.next=tail;
		}
	}
	
T popTail(){
	if (head==null){
		return null;
		}
	else{
		Node a= tail;
		tail.prev.next=null;
		return a.value;
		}
		}
		
	
public void printForward(){
	Node a= head;
	while(a.next!=null){
		System.out.println(a.value);
		a=a.next;
		}
	System.out.println(tail.value);
	System.out.println("\n");
	}
	
	
void printBackward(){
	Node a=tail;
	while(a.prev!=null){
		System.out.println(a.value);
		a=a.prev;
		}
	System.out.println(head.value);
	System.out.println("\n");
	}
	
	
	
	
	
	
}

 

[ETlearner]

so funktionierts :

T popHead(){
	if(head==null){
		return null;}
	
	else{
		Node a= head;
		head=head.next;
		
		return a.value;
		
		}
	
	}

 

[Sesostris]

Für eine mehrelementige Liste sollte popHead() in etwa so aussehen:

			Node a = head;
			head = head.next;
			head.prev = null;
			return a.value;

Bei popTail() ersetzt du jedes head durch tail und jedes next durch prev und umgekehrt.

Aber - und ich wiederhole mich - du musst noch den Sonderfall einer einelementigen Liste beachten.

EDIT: Wenn du, wie in deinem letzten Beitrag, head.prev = null; weglässt, dann wird die head-Referenz zwar korrekt um ein Element verschoben, aber das alte head-Element befindet sich noch immer in deiner Liste.

 

[ETlearner]

im falle, dass es nur ein element gibt müsste die methode doch auch wiederum klappen oder?


Node a = head; -->a speichert daten von head bzw. tail ab da head == tail
head = head.next; -->head ist head.next... also null
head.prev = null; -->head.prev ist ja eh schon die nullreferenz
return a.value;

oder würde es in diesem fall nicht funktionieren?

 

[Sesostris]

Probier es doch aus. Meiner Meinung nach sollte das eine NullPointerException geben. Warum? Weil bei einer einelementigen Liste, wie du bereits richtig erkannt hast, head und tail auf den selben Knoten zeigen, musst du danach auch beide auf null setzen.

EDIT: Die NullPointerException gibts es genau hier...

Node a = head; -->a speichert daten von head bzw. tail ab da head == tail
head = head.next; -->head ist head.next... also null
head.prev = null; -->head.prev ist ja eh schon die nullreferenz
return a.value;

Da head "eh schon die nullreferenz" ist, kann man auch nicht auf die Instanzvariable prev zugreifen.

 

[ETlearner]

T popHead(){
	if(head==null){
		return null;}
	
	else if(head==tail){
		Node a=head;
		head=null;
		tail=null;
		return a.value;
		}

		
	else{
		  Node a = head;
            head = head.next;
            head.prev = null;
            return a.value;
		}
	
	}

ist es so richtig?

 

[ETlearner]

public class DoubleLinkedList <T> {
	
	
	public class Node{	
		private T value;
		private Node next;
		private Node prev;
		public Node(T value, Node next, Node prev){
			this.value=value;
			this.next=next;
			this.prev=prev;
			}
	}
	
private Node head;
private Node tail;
public DoubleLinkedList(){
	head=null;
	tail=null;
	}
public void appendHead (T value){
	head=new Node(value, head, null);
	if(tail==null){
			tail=head;}
	else{
			head.next.prev=head;
			}
	}
	
T popHead(){
	if(head==null){
		return null;}
	
	else if(head==tail){
		Node a=head;
		head=null;
		tail=null;
		return a.value;
		}

		
	else{
		  Node a = head;
            head = head.next;
            head.prev = null;
            return a.value;
		}
	
	}

public void appendTail(T value){
	tail= new Node(value, null, tail);
	if(head==null){
		head=tail;}
	else{
		tail.prev.next=tail;
		}
	}
	
T popTail(){
	if (head==null){
		return null;
		}
	else if(head==tail){
		Node a=head;
		head=null;
		tail=null;
		return a.value;
		}
	else{
		Node a= tail;
		tail=tail.prev;
		tail.next=null;
		return a.value;
		}
		}
		
	
public void printForward(){
if(head==null){System.out.println("LEERE LISTE");
				}
else{
	Node a= head;
	while(a.next!=null){
		System.out.println(a.value);
		a=a.next;
		}
	System.out.println(tail.value);
	System.out.println("\n");
	}}
	
	
void printBackward(){
	if(head==null){System.out.println("LEERE LISTE");
				}
	else{
	Node a=tail;
	while(a.prev!=null){
		System.out.println(a.value);
		a=a.prev;
		}
	System.out.println(head.value);
	System.out.println("\n");
	}
	
	
	
}}

jetzt funktionieren alle methoden -.-^^
ich glaube so ist das programm vollständig...