OOP Verkettete Liste

[bordon]

Hallo,
ich habe eine Frage zu einer verketteten Liste. Und zwar hab ich folgenden Code:

public class Hauptklasse {
	public static void main(String[] args){
		Liste verk = new Liste();
				
		verk.insertToTop("sieben");							
		verk.insertToTop("eins");							
		verk.insertToTop("vier");							
		
		verk.insertToEnd("drei");
		
		System.out.println(verk.search("eins"));	
		System.out.println(verk.search("achtzehn"));		
		
		System.out.println(verk.anzahl);				
	}

}
public class Knoten {
	String daten;
	Knoten next;
	Knoten prev;
	
	Knoten(String daten){
		this.daten=daten;	
		next=null;
		prev=null;
	}

}
public class Liste {
	Knoten head = null;
	Knoten tail = null;
	int anzahl = 0;
	
	void insertToTop(String daten){
		Knoten p = new Knoten(daten);
		p.next=head;
		head=p;
		anzahl++;
	}
	
	void insertToEnd(String daten){
		Knoten p = new Knoten(daten);
		if(head==null){
			head=p;
		}
		else{
			tail.next=p;
			tail=p;
		}
		anzahl++;
	}
	
	Boolean search(String daten){
		Knoten p = head;
		while(p!=null && p.daten!=daten){
			p=p.next;
		}
		if(p==null){
			return false;
		}
		else{
			return true;
		}
	}
	
}

Und zwar, wenn ich die Methode

verk.insertToEnd("drei");

aufrufe, kommt bei mir eine java.lang.NullPointerException und ich weiß nicht wieso.

Eine zweite Frage ist noch: Wie kann ich überprüfen, ob das Element das ich einfüge an erster oder letzter Stelle der Liste ist?

Danke für eure Hilfe und freundliche Grüße

 

[Marcinek]

Weil tail null ist

 

[bordon]

Aber ich hab doch mit den

verk.insertToTop("sieben");							
verk.insertToTop("eins");							
verk.insertToTop("vier");

schon was in die Liste geschrieben, wieso ist tail dann null? Muss ich in der Methode

void insertToTop(String daten){
		Knoten p = new Knoten(daten);
		p.next=head;
		head=p;
		anzahl++;
}

noch was mit tail machen?

 

[Marcinek]

Ja sicher..

Woher soll das Programm den wissen, dass da plörtlich nen wert rein muss?

 

[bordon]

Aber ich schreib doch was mit der Methode:

void insertToEnd(String daten){
		Knoten p = new Knoten(daten);
		if(head==null){
			head=p;
		}
		else{
			tail.next=p;
			tail=p;
		}
		anzahl++;
}

in tail rein????

 

[Marcinek]

Betrachte das mal ein wenig logischer..

Du hast 2 Finger

Head, zeigt auf den ersten und tail auf letzten.

Wenn du nun ans ende was einfügen willst, und head und tail zeigen auf nix, dann müssen beide auf das neue Element zeigen logisch.

Nun Fügst du nochmal was ans ende.

Dann hast du 2 Elemente, wovon auf den linken (bildlich) zeigt der head-Finger und auf den letzten der tailfinger.

Außerdem zeigt das linke element mit next auf das rechte.

Male dir das mal auf einem Blatt papier auf und vergleiche es mit deinem program.

 

[bordon]

ok, dass habe ich verstanden.
Ich habe versucht es umzusetzen und auf folgenden Vorschlag gekommen, der auch nicht funktioniert:

void insertToEnd(String daten){
		Knoten p = new Knoten(daten);
		tail=p;
		head=p;
		tail.next=p;
}

Wieso funktioniert das nicht?

 

[Marcinek]

Nun es ist vollkommen falsch.

Du musst mehrere Fälle unterscheiden.

1. Es gibt noch keine Elemente in der Liste

2. Es gibt nur 1 Element in der Liste

3. Du möchtest ein Elemente vorne (head) oder hinten (tail) einfügen.

Jetzt muss man sich überlegen.

Wie erkenne ich diese Fälle. (Hinweis, ich würde es auf keinen Fall an der Anzahl festmachen!)

Beispiel fall 1:

Es sind noch keine Elemente in der Liste, ergo ist head und tail null.

if(head == null && tail == null) {
   // Es gibt keine Elemente in der Liste!
  // Head und tail müssen auf das neue zeigen!
   head = p;
   tail = p;
}

Diesen Zustand musst du dir auf einem Papier aufmalen!

2 vierecke benannt head und teil zeigen nun auf ein drittes viereck p

Nun Fall 2:

head und tail sind schonmal != null! Warum? - Weil das 1. Elemente egal, ob tail oder head hinzugefügt sowohl von head als auch tail referenziert wird.

Nun kommt ein weiteres p2 während p1 schon in der Liste ist.

Wenn du das nun hinten einfügen willst, dann

(hier ist die reihenfolge wichtig!

tail (was p1 ist) auf p2 zeigen. also

tail.next = p2

und dann muss tail zu p2 werden.

tail = p2

Daraus ergibt sich

head   tail  
 |          |
 v         v
p1  ->  p2

und nun du