Java LinkedList – Wie du eine verkettete Liste implementierst. Der Workshop!

Keylearnings:

  • Was ist eine doppelt verkettete Liste?
  • Was ist eine wahlfreie Datenstruktur?
  • Wie du Datensätze in eine LinkedList einfügst.
  • Wie du eine Liste mit Hilfe eines selbstgebauten Iterators durchläufst.
  • Wie du ein Element aus einer verketteten Liste löschst.

Heute mache ich ernst!

Oft werde ich gefragt wie lange man denn braucht um das Programmieren zu erlernen.

Meine Antwort: Das hängt ganz davon ab wie sehr du übst!

Und üben das wollen wir heute!

Ich möchte dir einen weiteren Listen-Typ zeigen. Nämlich die doppelt verkettete Liste, auch LinkedList genannt.

Genau wie für die ArrayList, gibt es auch für die LinkedList eine entsprechende Standard-Klasse, die die Funktionalität einer verketteten Liste implementiert.

Diese kannst du natürlich nutzen.

Aber das ist langweilig!  Denn ich bin mir sicher, dass du das, wenn du die Klassen für die ArrayList verstanden hast, mit Hilfe der Standarddokumentation auch locker selber hinbekommst.

Der Vollständigkeit wegen habe ich aber ein kleines Video gedreht, in dem ich dir zeige wie du die Java Klasse LinkedList verwendest um eine verkettete Liste zu implementieren.

Heute wollen wir einen anderen Weg gehen. Der heutige Artikel ist ein Workshop, in dem du lernst wie du selber eine Klasse implementierst, die eine verkettete Liste realisiert.

Das hat mehrere Vorteile:

  1. Du erhälst ein Verständnis dafür, wie eine Datenstruktur unter der Motorhaube funktioniert.
  2. Dir gehen Konzepte wie Iteratoren und dynamische Speicherverwaltung in Fleisch und Blut über.
  3. Es bietet sich eine hervorragende Gelegenheit das Konzept der objektorientierten Programmierung einzuüben.

Aber nichts destotrotz müssen wir als erstes festhalten über was wir reden.

Was ist eine doppelt verkettete Liste?

Sowohl das Array, als auch die ArrayList sind sogenannte wahlfreie Datenstrukturen.

Was bedeutet das nun schon wieder?

Bei einem wahlfreien Speicher kannst du zu jedem Zeitpunkt auf jeden beliebigen Wert in der Datenstruktur zugreifen.

So ist es bei Franka’s Einkaufsliste beispielsweise völlig egal, in welcher Reihenfolge Franka auf die in der Liste gespeicherten Artikel zugreift.

Niemand zwingt Franka die Liste von oben nach unten abzuarbeiten. Sie kann jeden Artikel nach Lust und Laune in den Einkaufswagen werfen.

Eine verkettete Liste ist hingegen kein wahlfreier Speicher. Der Zugriff auf die Daten in der Struktur unterliegt gewissen Regeln.

Am besten kannst du dir eine Liste vorstellen wie ein Fahrstuhl.

java verkettete Liste

Wenn du im Keller eines Hochhauses stehst und in den 20ten Stock willst, dann wirst du nach heutigem Stand der Technik nicht vom Keller in den 20 Stock gebeamt, sondern der Fahrstuhl muss jedes Stockwerk der Reihe nach passieren.

Zu erst den ersten, dann den zweiten, den dritten…den 19ten und so weiter. Erst dann kannst du im 20ten Stock aussteigen.

Und genau so, ist es auch bei einer verketteten Liste.

In einer verketteten Liste kannst du die Elemente nur eines nach dem anderen verarbeiten.

Bei einer einfach verketteten Liste sogar nur von vorne nach hinten. Eine doppelt verkettete Liste kann immerhin auch Rückwärts durchlaufen werden.

Wie ist eine verkettete Liste aufgebaut!

Eine Liste ist eine Verkettung von Knoten und ein Knoten ist nichts anderes als ein Behälter für die Daten, die du speichern möchtest, der außerdem einen Verweis auf den Vorgänger- und Nachfolgeknoten besitzt.

Weißt du was? Ich glaube es ist eine sehr gute Idee für die Knoten eine eigene Klasse zu entwerfen.

1: class Knoten{
	
2:	private Knoten successor = null;
3:	private Knoten predessor = null;
4:	private Object data = null;
	
5:	public Knoten(Knoten successor,Knoten predessor, Object data){
6:		this.successor = successor;
7:		this.predessor = predessor;
8:		this.data = data;
9:	}
	
11:	public Knoten getSuccessor(){ return this.successor; }
12:	public Knoten getPredessor(){ return this.predessor; }
13:	public Object getData(){return this.data; }
14:	public void setData(Object data){ this.data = data; }
15:	public void setSuccessor(Knoten knoten){this.successor = knoten;}
16:	public void setPredessor(Knoten knoten){this.predessor = knoten;}
	
17: }

Vergessen wir die Zeilen 11 bis 16! Hier stehen nur die getter und setter Methoden für die Klassenvariablen. Die sind allerdings spannend. Wir haben drei Stück davon.

In der Variable successor speichern wir den Nachfolgeknoten und in predetor den Vorgängerknoten. Beide Variablen sind sinvollerweise vom Datentyp Knoten.

In der Variablen data speichern wir die Daten, die wir in die Listen einfügen wollen. Da wir uns nicht auf einen Datentyp festlegen möchten, verwenden wir den allgemeinsten Datentyp Object.

Standardmäßig sind alle Variablen mit dem Wert null initialisert!

Mit dem Konstruktor der Klasse können wir einen Knoten erzeugen und mit Vorgänger, Nachfolger und den eigentlichen Daten initialisieren.

Die Implementierung einer LinkedList

Okay super! Wir können jetzt Knoten erzeugen!

Jetzt müssen wir uns nur noch um die Verkettung der Knoten kümmern.

Also Atme tief durch und mache ersteinmal Ommmmmmmm wie ein Yogalehrer.

Fertig? Gut! Dann überlegen wir uns jetzt wie das Wachstum der Liste aussieht!

LinkedList erster Knoten

Der Anfang! Eine leere Liste. Wir haben nichts! Der erste Knoten ist einsam und hat weder Vorgänger noch Nachfolger. Alles was wir tun müssen, ist unsere Daten in den Knoten zu packen.

Knoten ersterKnoten = new Knoten(null,null,"Ei");

Glückwunsch! Der erste Knoten ist erzeugt, das hat Spaß gemacht! Fügen wir einen weiteren Knoten in unsere Datenstruktur ein.

Jetzt wird es schon interessanter! Wenn wir einen Knoten an die Liste anhängen, dann hat der neue Knoten den alten als Vorgänger und der alte den neuen als Nachfolger.

LinkedList zwei Knoten

Also wie sieht der Konstruktur für den neuen Knoten aus?

Knoten zweiterKnoten = new Knoten(null,ersterKnoten,"Nudeln");

Auf die Nudeln bist du nicht gekommen. Oder?

Macht nix! Die anderen Parameter sind eh viel wichtiger.

Der neue Knoten steht am Ende der Liste und hat deshalb keinen Nachfolger. Der Vorgänger des zweiten Knoten, ist der bereits vorhandene Knoten, weshalb wir die Instanzvariable ersterKnoten als zweites Argument übergeben.

Aber haben wir nicht was vergessen? Yes, gut aufgepasst! Der erste Knoten hat jetzt einen Nachfolger. Nämlich den gerade hinzugefügten Knoten.

Puh, zum Glück haben wir an eine setter Methode gedacht!

ersterKnoten.setSuccessor(zweiterKnoten);

Fügen wir einen dritten Knoten hinzu!

Und jetzt wird es richtig interessant! Wir müssen uns nämlich entscheiden, ob wir den Knoten einfach hinten anhängen oder zwischen die beiden bereits erzeugten Knoten einfügen.

Wenn wir den dritten Knoten hinten an die Liste hängen, dann können wir unser Prozedre von gerade wiederholen. Wir müssen nur überall da wo das Wörtchen erster steht, zweiter und da wo zweiter steht dritter hinschreiben.

Aber hey! Wir sind Abennteurer! Da ist es Ehrensache, dass wir uns für den schwierigen Fall entscheiden und den Knoten in die Mitte einfügen.

LinkedList drei Knoten

Welchen Vorgänger hat der neue Knoten?

Ganz genau! Den Knoten, den wir als erstes erstellt hatten.

Welchen Nachfolger hat der neue Knoten?

Richtig! Den Knoten, welchen wir als zweites erstellt haben.

Welche Daten wollen wir speichern?

Hmm? Ich schlage Tomatensuppe vor!

Nach diesen Vorüberlegungen ist klar, wie der Konstruktur der Klasse Knoten aufzurufen ist.

Knoten dritterKnoten = new Knoten(zweiterKnoten,ersterKnoten,"Tomatensuppe");

Jetzt müssen wir uns nur noch darum kümmern, die beiden bereits existierenden Knoten anzupassen.

Der erste Knoten hat den neuen Knoten als Nachfolger.

ersterKnoten.setSuccessor(dritterKnoten);

Der als zweites erzeugte Knoten hat den neuen Knoten als Vorgänger.

zweiterKnoten.setPredessor(dritterKnoten);

Sehr gut! Wir haben eine Liste mit drei Knoten, das ist auf jeden Fall ein Anfang.

Wie sieht die Sache bei einer Liste mit beliebig vielen Knoten aus?

Merkst du es? Wir haben die notwendige Denkarbeit bereits getan, denn auch bei einer Liste mit beliebig vielen Elementen haben wir nur diese drei Fälle zu unterscheiden.

  1. Die Liste ist noch leer.
  2. Wir hängen einen Knoten hinten an die Liste an.
  3. Wir fügen einen Knoten zwischen zwei bereits existierenden Knoten ein.

Wir müssen unsere Überlegungen für die dreier Liste also nur in allgemeingültigen Quellcode packen. Hierfür schreiben wir eine Methode insert.

Die Methoden unserer Liste packen wir alle in eine eigene Klasse, die wir LinkedList nennen. Außerdem benötigen wir drei Attribute um den ersten, den letzten und den Knoten auf den wir aktuell in der Liste stehen zu speichern.

1: class LinkedList {
	
2:      private Knoten aktuellerKnoten = null;
3:	private Knoten letzterKnoten = null;
4:	private Knoten ersterKnoten = null;
	
5:	public void insert(Object data){
6:	  //1.Fall: Die Liste ist leer
7:	  if (aktuellerKnoten == null){
8:		aktuellerKnoten = new Knoten(null,null,data);
10:		ersterKnoten = aktuellerKnoten;
11:	  }else{
12:		//2.Fall Wir hängen einen Knoten hinten an
13:		if (aktuellerKnoten.getSuccessor() == null){
14:		   aktuellerKnoten.setSuccessor(new Knoten(null,aktuellerKnoten,data));
15:		   letzterKnoten = aktuellerKnoten.getSuccessor();
16:		   aktuellerKnoten = letzterKnoten;
17:		}else{
18:		//3.Fall Wir fügen eine Knoten zwischen zwei existierenden Knoten ein.
19:		   Knoten tempSuccessor = aktuellerKnoten.getSuccessor();
20:		   aktuellerKnoten.setSuccessor(new Knoten(tempSuccessor,aktuellerKnoten,data));
21:		   tempSuccessor.setPredessor(aktuellerKnoten.getSuccessor());
22:		   aktuellerKnoten = aktuellerKnoten.getSuccessor();
23:		}				
24:	   }
25:	}
26: }

Neue Knoten fügen wir hinter dem Knoten, auf dem wir aktuell stehen, d.h. direkt hinter aktuellerKnoten ein.

verkettete Liste Knoten einfügen

Hat die Variable aktuellerKnoten den Wert null, dann haben wir eine leere Liste und in den Zeilen drei bis sechs wird der erste Knoten einer neuen Liste erstellt.

Wenn der aktuelle Knoten keinen Nachfolger hat, also die Variable aktuellerKnoten den Wert null besitzt, dann befinden wir uns am Ende der Liste und in den Zeilen neun bis elf wird ein zusätzlicher Knoten an die Liste angehängt. In diesem Fall wird der neue Knoten als aktueller Knoten verwendet.

Im letzten Fall (Zeile 13-17) ist der aktuelle Knoten ein Knoten irgendwo zwischen Listenanfang und Listenende und wir erzeugen einen Knoten, den wir zwischen zwei bereits existierenden Knoten einfügen müssen.

Hierzu gehen wir genau wie in unserem Beispiel mit den drei Knoten vor. Wir fügen den neuen Knoten hinter den Knoten ein, auf dem wir aktuell stehen indem wir in Zeile 14 den Nachfolger des aktuellen Knoten auf den neuen Knoten setzen. Der bisherige Nachfolger des aktuellen Knoten hat jetzt den neuen Knoten als Vorgänger (Zeile 16). Wieder ändern wir (Zeile 15) den aktuellen Knoten auf den neu erzeugten Knoten (Zeile 17).

Um später einfacher prüfen zukönnen, ob wir am Anfang oder am Ende der Liste stehen, sichern wir den ersten Knoten in der Variablen ersterKnoten und den letzten Knoten der Liste in der Variablen letzterKnoten.

Die Liste mit einem Iterator durchlaufen

Natürlich macht unsere Liste nur dann Spaß, wenn wir eine Möglichkeit haben diese zu durchlaufen und die einzelnen Werte ausgeben können.

Und da wir Profis werden wollen. Handeln wir auch wie Profis. Und wie handelt ein Profi in diesem Fall?

Er baut sich einen eigenen Iterator und durchläuft damit die Liste innerhalb einer Schleife.

Um einer Klasse einen Iterator hinzuzufügen müsssen wir die java interfaces Iterable und Iterator mittels des Schlüsselworts implements einbinden.

class LinkedList implements Iterable<Object>, Iterator<Object>

Da wir Daten des allgemeinsten Typ Object in unserer Liste speichern, setzen wir über die Generics den Datentyp des Iterators ebenfalls auf Object.

Die Iterable Schnittstelle besitzt die Methode iterator und die Schnittstelle Iterator die Methoden hasNext(), next() und remove.

Diese Methoden müssen wir „nur“ in unserer Listen-Klasse implementieren und schon haben wir eine Liste mit Iterator-Funktionalität.

Am leichtesten ist iterator() aus Iterable zu implementieren, die einfach eine Instanz auf das Objekt zurückliefert, über das wir iterieren wollen. Da das unsere Liste selbst ist, müssen wir lediglich eine Instanz der Liste selbst zurückgeben.

Klingt wieder schrecklich kompliziert, ist aber mit Hilfe des Schlüsselworts this ratzi fatzi implementiert.

1: public Iterator<Object> iterator(){
2:   return this;
3: }

Auch hier dürfen wir nicht vergessen, dass wir über ein Generic den Rückgabetyp auf Object setzen.

Damit wäre bereits die Methode des java interfaces Iterable implementiert.

Kümmern wir uns also um die java Schnittstelle Iterator. Beginnen wir mit der Methode next, die wir dazu verwenden wollen innerhalb unserer Liste um ein Element nach vorne zu springen.

Hier der Programmcode. Eine Erklärung folgt im Anschluss!

1: public Knoten next(){
2:   if(aktuellerKnoten.getSuccessor() != null){
3:	aktuellerKnoten = aktuellerKnoten.getSuccessor();
4:   }else{
5:	System.out.println("letzter Knoten erreicht!");
6:   }
7:   return aktuellerKnoten;
8:}

Mit der if Bedingung in Zeile zwei überprüfen wir, ob wir bereits am Ende der Liste stehen. In diesem Fall können wir nicht weiter vorrücken und geben die Meldung „letzter Knoten erreicht“ auf dem Bildschirm aus!

Andernfalls setzen wir in Zeile drei den neuen aktuellen Knoten auf den Nachfolger des Knotens, auf dem wir aktuell stehen und geben diesen als Rückgabewert zurück.

Wahrscheinlich kannst du dir bereits denken wie wir die hasNext() Methode implementieren.

Mit dieser Methode möchten wir überprüfen, ob es ein weiteres Listenelement gibt.

Wir müssen also nur prüfen, ob der Knoten, auf dem wir aktuell stehen einen Nachfolger hat.

1: public boolean hasNext(){
2:   if (aktuellerKnoten.getSuccessor() == null){
3:    	return false;
4:    }else{
5:    	return true;
6:    }
7:}

Existiert kein Nachfolger, dann gibt es kein weiteres Element in der Liste und die if Bedingung in Zeile zwei ist erfüllt, weshalb die Methode den Wahrheitswert false zurückliefert.

Jetzt kommt der Klopper. Die remove() Methode, mit der wir einen Knoten aus unserer Liste löschen wollen.

1: public void remove(){    
    //Erstes Element löschen
2:  if (aktuellerKnoten == ersterKnoten){
3:	ersterKnoten = aktuellerKnoten.getSuccessor();
4:	ersterKnoten.setPredessor(null);
5:	aktuellerKnoten = ersterKnoten;
6:  }else{
	//letztes Element löschen
7:	if (aktuellerKnoten.getSuccessor() == null){
8:	  aktuellerKnoten = aktuellerKnoten.getPredessor();
9:	  aktuellerKnoten.setSuccessor(null);
10:       letzterKnoten = aktuellerKnoten;
11:	}else{
12:	  //Element in der Mite der Liste löschen
13:       Knoten tempSuccessor = aktuellerKnoten.getSuccessor();
14:	  Knoten tempPredessor = aktuellerKnoten.getPredessor();
15:	  aktuellerKnoten = tempPredessor;
16:	  aktuellerKnoten.setSuccessor(tempSuccessor);
17:	  tempSuccessor.setPredessor(aktuellerKnoten);
18:	}
19:  }
20:}

Ähnlich wie beim Einfügen eines Knotens, haben wir es auch hier wieder einfach, wenn wir uns am Anfang oder am Ende der Liste befinden.

Wollen wird den ersten Knoten löschen, so müssen wir nur dafür sorgen, dass der bisher zweite Knoten in der Liste zum Listenanfang wird.

Und genau das machen wir in den Zeilen drei bis fünf. Hier setzen wir die Variable ersterKnoten auf den bisher zweiten Knoten in der Liste und entfernen dessen Vorgänger (der bisherige Listenanfang). Außerdem setzen wir den aktuellen Knoten auf den neuen Listenanfang.

Ganz ähnlich gehen wir vor um einen Knoten am Listenende zu entfernen (Zeile 8 bis 10). Wir setzen zunächst den aktuellen Knoten auf den vorletzten Knoten in der Liste (d.h. den Vorgänger des bisher letzten Knoten) und sorgen dafür, dass der vorletzte Knoten zum letzten wird indem wir dessen Nachfolger entfernen.

Richtige Arbeit haben wir eigentlich erst, wenn wir einen Knoten zwischen Anfang und Ende der Liste entfernen wollen. Der Programmcode hierfür steht in den Zeilen 13 bis 17. Da wir den aktuellen Knoten löschen wollen, sichern wir als erstes dessen Vorgänger und Nachfolger in den Variablen tempSuccessor und tempPredessor.

Anschließend setzen wir den aktuellen Knoten auf den Vorgänger des zu löschenden Knotens (Zeile 15). Der Nachfolger dieses Knotens ist der Nachfolger des Knotens, den wir löschen wollen (Zeile 16).

Und Last but not least dürfen wir nicht vergessen, dass der Nachfolger des zu entfernenden Knotens den aktuellen Knoten (Vorgänger des Knotens, den wir löschen möchten) jetzt als Vorgänger hat.

Java LinkedList remove

So langsam reißt der Geduldsfaden! Machen wir einen Testlauf!

Fügen wir die Werte Harry, Lisa, Peter, Fiona und Laura in eine neue Liste ein.

1: LinkedList neueListe = new LinkedList();
2: neueListe.insert("Harry");
3: neueListe.insert("Lisa");
4: neueListe.insert("Peter");
5: neueListe.insert("Fiona");
6: neueListe.insert("Laura");

Nach dem ganzem Zeug von oben ist das doch sehr entspannt. Wir erzeugen eine Instanz neueListe und fügen mit der insert Methode nacheinander die Daten ein.

Nach den Einfüge-Operationen befinden wir uns am Ende der Liste, deshalb spendieren wir unserer Klasse noch eine kleine Methode, mit der wir auf den ersten Datensatz springen können.

public void ersterKnoten(){
  aktuellerKnoten = ersterKnoten;
}

Alles was die Methode macht, ist den aktuellen Knoten auf den ersten Knoten in der Listen zu setzen. Wie gesagt alles vollkommen entspannt.

Außerdem wäre eine Methode, mit der wir die Daten des aktuellen Knotens ausgeben können sehr nice.

Eine einfache getter Methode wie du sie kennst.

public Object getAktuelleDaten(){
	return aktuellerKnoten.getData();
}

Puh, aber jetzt bin ich aufgeregt. Jetzt wollen wir unseren selbstgebauten Iterator mal testen.

Der folgende Programmschnipsel durchläuft unsere Liste und gibt die Daten jedes Knoten auf dem Bildschirm aus.

1: neueListe.ersterKnoten();
2: for (Iterator<Object> it = neueListe.iterator();it.hasNext();it.next()){
3:	System.out.println(neueListe.getAktuelleDaten());
4:   }
5:   System.out.println(neueListe.getAktuelleDaten());

In der ersten Zeile positionieren wir uns zunächst an den Anfang der Liste.

Über den in der for Schleife erzeugten Iterator it durchlaufen wir die gesamte Liste und geben jeden in der Liste gespeicherten Wert auf dem Bildschirm aus.

Die Schleife läuft solange bis der Iterator beim letzten Element der Liste angekommen ist, d.h. die Methode hasNext() den Wert false zurückliefert.

Im Operationsteil der Schleife verwenden wir die next Methode um zum jeweils nächsten Knoten zu gelangen.

Da die Schleife in dem Moment abbricht, in dem wir den letzten Knoten erreicht haben, müssen wir den letzten Datensatz der Liste in Zeile fünf noch gesondert ausgeben.

Hier die entsprechende Programmausgabe:

Harry
Lisa
Peter
Fiona
Laura

So unsere Java LinkedList ist fertig. Ich hoffe ich konnte dir helfen ein tiefes Verständnis für diese Datenstruktur zu erhalten.

Im folgenden der Übersichtlichkeit wegen die vollständige LinkedList Klasse. Die Testläufe der Klassen können vollständig in der main Methode implementiert werden.

class LinkedList implements Iterable<Object>, Iterator<Object> {
	
  private Knoten aktuellerKnoten = null;
  private Knoten letzterKnoten = null;
  private Knoten ersterKnoten = null;
	
  public void insert(Object data){
	//1.Fall: Die Liste ist leer
	if (aktuellerKnoten == null){
	  aktuellerKnoten = new Knoten(null,null,data);
	  ersterKnoten = aktuellerKnoten;
	}else{
	  //2.Fall Wir hängen einen Knoten hinten an
	  if (aktuellerKnoten.getSuccessor() == null){
	    aktuellerKnoten.setSuccessor(new Knoten(null,aktuellerKnoten,data));
	    letzterKnoten = aktuellerKnoten.getSuccessor();
	    aktuellerKnoten = letzterKnoten;
	  }else{
	     //3.Fall Wir fügen eine Knoten zwischen zwei existierenden Knoten ein.
	     Knoten tempSuccessor = aktuellerKnoten.getSuccessor();
	     aktuellerKnoten.setSuccessor(new Knoten(tempSuccessor,aktuellerKnoten,data));
	     tempSuccessor.setPredessor(aktuellerKnoten.getSuccessor());
	     aktuellerKnoten = aktuellerKnoten.getSuccessor();
	   }				
	}
  }
	
  public Knoten next(){
    if(aktuellerKnoten.getSuccessor() != null){
	aktuellerKnoten = aktuellerKnoten.getSuccessor();
    }else{
	System.out.println("letzter Knoten erreicht!");
    }
	return aktuellerKnoten;
  }
	
  public Iterator<Object> iterator(){
    return this;
  }
	
  public boolean hasNext(){
     if (aktuellerKnoten.getSuccessor() == null){
	return false;
     }else{
        return true;
     }
  }
	
  public void remove(){    
     //Erstes Element löschen
     if (aktuellerKnoten == ersterKnoten){
	ersterKnoten = aktuellerKnoten.getSuccessor();
	ersterKnoten.setPredessor(null);
	aktuellerKnoten = ersterKnoten;
     }else{
        //letztes Element löschen
	if (aktuellerKnoten.getSuccessor() == null){
	  aktuellerKnoten = aktuellerKnoten.getPredessor();
	  aktuellerKnoten.setSuccessor(null);
	  letzterKnoten = aktuellerKnoten;
	}else{
	   //Element in der Mite der Liste löschen
	   Knoten tempSuccessor = aktuellerKnoten.getSuccessor();
	   Knoten tempPredessor = aktuellerKnoten.getPredessor();
	   aktuellerKnoten = tempPredessor;
	   aktuellerKnoten.setSuccessor(tempSuccessor);
	   tempSuccessor.setPredessor(aktuellerKnoten);
	}
      }
    }
	
    public void ersterKnoten(){
	aktuellerKnoten = ersterKnoten;
    }
	
    public Object getAktuelleDaten(){
	return aktuellerKnoten.getData();
    }

}

Aber eines darf ich dir natürlich nicht verschweigen! Das war eine Übung! Die in der java LinkedList Klasse implementierte Liste ist natürlich weitaus optimierter als unser Eigenbau, deshalb solltest du im richtigen Leben natürlich auf die Klasse java LinkedList zurückgreifen.

Und wie das geht, erfährst du im folgenden Video:

Wie immer freue ich mich über deine Fragen im Kommentarbereich! Hat dir der Artikel gefallen? Dann folge uns doch am besten gleich auf Facebook!

Hallo ich bin Kim und ich möchte ein großer Programmierer werden. Machst du mit?

Kommentare (14)

  • Antworte

    Das ist ja alle gut und schön erklärt. Wäre aber noch schöner wenn man am Ende mal noch eine Zusammenfassung hätte mit dme kompletten Code. Weil ich weis nie wo ich jetzt was reinschreiben muss, da es immer nur Bruchstücke von Code sind. Z.B. gleich mit ganz oben, wo gesagt wird das man dann die Vorgänger und Nachfolger wieder überschreiben muss. Da steht dann nur eine Zeile da „ersterKnoten.setSuccessor(zweiterKnoten);“….. Wo muss ich das eintragen? Direkt in die Klasse „Knoten“ oder in eine main Methode??? Keine Ahnung.

    Oder auch z.B wo dann erklärt wird wie man etwas schreibt damit man belibig viele Knoten einfügen kann. Da steht etwas von „aktueller Knoten“, aber der wurde noch nie deklariert. Wo muss ich das machen? Nur in der Methode oder brauche ich den aktuellen Knoten später nochmal das er nicht in der Methode geschrieben seien darf. ….. Fazit: Viele offene Fragen.

    • Hallo Phillip, danke für deinen Kommentar. Ich werde den kompletten Programmcode in Kürze nachliefern. Bei einer doppelt verketteten Liste haben wir immer nur einen einzelnen Knoten im Blickfeld und das ist der aktuelleKnoten von dem wir lediglich den Vorgängerknoten und den Nachfolgeknoten kennen. Auf die wir mit Hilfe der getter und setter Methoden zugreifen können. Ich denke am besten ist es mit zwei Klassen zu arbeiten. Eine für den einzelnen Knoten in der man die Daten, den Vorgängerknoten und den Nachfolgeknoten speichert. Und eine weitere um die Listen-Methoden Einfügen, löschen etc. zu implementieren. Viele Grüße Kim

  • Antworte

    Hallo Kim, deine Information finde ich Toll. Ich habe deine Web Page gefunden weil ich dabei bin eine Aufgabe von DVL (Doppel Verkette List) zu erledigen.
    Leider habe ich mehrere Fragen, vielleicht hast Du ein Tipp für mich. Ich bin keine Super Programmierer auf diesen Grund Kontakt ich dich.

    ich habe folgendes DVL , Java zu implementieren mit schnittestellen. Ich denke es funktioniert einigermaßen OK. Leider dann sollte ich ein Stack machen und hier liegt meine ganze „doubt“.

    Hier die DVL definintion. (Das habe ich schön implementiert)

    IValueElement.java and ValueElement.java files,

    package s c h n i t t s t e l l e n ;
    public interface IValueElement
    {
    public St r ing getName ( ) ;
    public void setName ( St r ing paramName ) ;
    public int getValue ( ) ;
    public void s e tValue ( int paramValue ) ;
    }

    IListElement.java und ListElement.java file
    package s c h n i t t s t e l l e n ;
    public interface ILi s tEl ement
    {
    public IValueElement getValueElement ( ) ;
    public void setValueElement ( IValueElement value ) ;
    public ILi s tEl ement g e tPr ede c e s s o r ( ) ;
    public void s e tPr e d e c e s s o r ( ILi s tEl ement pr ede c e s s o r ) ;
    public ILi s tEl ement g e tSuc c e s s o r ( ) ;
    public void s e t S u c c e s s o r ( ILi s tEl ement s u c c e s s o r ) ;
    }

    IList.java und List.java file
    package s c h n i t t s t e l l e n ;
    public interface I L i s t
    {
    public ILi s tEl ement getHead ( ) ;
    public void insertAtTheEnd ( IValueElement value ) ;
    public void ins e r tAtPos ( int pos , IValueElement value ) ;
    public IValueElement getElementAt ( int p o s i t i o n ) ;
    public int ge tFi r s tPosOf ( IValueElement value ) ;
    public void d e l e t eFi r s tOf ( IValueElement value ) ;
    public void de l e t eAl lOf ( IValueElement value ) ;
    public boolean member ( IValueElement value ) ;
    public void r e v e r s e ( ) ;
    public St r ing t oSt r ing ( ) ;
    }

    example:
    I L i s t l i s t = new Li s t ( ) ;
    IValueElement data00 = new ValueElement ( „K0“ , 0 ) ;
    IValueElement data01 = new ValueElement ( „K1“ , 1 0 ) ;
    IValueElement data02 = new ValueElement ( „K2“ , 2 0 ) ;
    l i s t . insertAtTheEnd ( data00 ) ;
    l i s t . insertAtTheEnd ( data01 ) ;
    l i s t . insertAtTheEnd ( data02 ) ;

    Hier meine Frage:
    =============
    Ich sollte die DVL implementation benutzen für mein Stack, aber IValueElement hat 2 Value (String und integer).
    Aber in Stack sollte ich nur ein integer benutzen .
    example: stack.pop(4);
    ich verstehe nicht wie kann die DVL Java.code benutzen für mein Stack.java

    IStack.java
    package s c h n i t t s t e l l e n ;
    public interface IStack
    {
    public I L i s t getDVL ( ) ;
    public int g e t S i z e ( ) ;
    public boolean isEmpty ( ) ;
    public boolean i s F u l l ( ) ;
    public int pop ( ) ;
    public void push ( int value ) ;
    public int top ( ) ;
    }

    Vielen Dank für deine Feedback.
    Maverick

    • Hallo Maverick,

      vielen Dank für deinen Kommentar!

      Eine doppelt verkettete List ist sehr gut geeignet um einen Stack zu implementieren, da du sehr einfach Elemente hinten an die Liste anhängen kannst. Bei deiner Stack Implementierung musst du immer nur mit dem letzten Element in der Liste arbeiten und du musst deine Klassen und Schnittstellen so gestalten, dass du auch nur auf dieses Zugriff hast.

      Bei der Stack push Operation hängst du einfach ein Element an die Liste hinten dran und bei der pop Operation entfernst du das letzte Element in der Liste. Das Listenende verwendest du also als dein Stack-Kopf, auf den du Datensätze legen (push) oder entnehmen (pop) kannst.

      Ich vermute bei deinem IValueElement handelt es sich um das was ich in meinem Artikel Knoten nenne. Um herauszufinden für was die Parameter stehen, müsste man sich den Konstruktor der Klasse IValueElement ansehen. Ich könnte mir vorstellen (nur Mutmaßung) dass ein Parameter dafür gedacht ist den Verweis auf den Knotenn-Nachfolger in der Liste zu speichern.

      Normalerweise gibt es einen „Spezialwert“ (in der Regel der Nullwert null), welches das Listenende markiert. Da du bei deiner Stack implementierung nur Elemente hinten an die Liste dranhängst sollte dieser „Spezialwert“ bei der push Operation als Parameter übergeben werden.

      Aber wie gesagt da müsste man sich die Klasse IValueElement genauer ansehen.

      Ich werde die Tage ein kleines Video machen oder einen Artikel schreiben, in dem ich erkläre wie man eine doppelt verkettete Liste verwendet um einen Stack zu implementieren. Bitte gib mir etwas Zeit.

      Viele Grüße
      Kim

      P.S Natürlich wäre auch eine Implementierung möglich, bei der du nur mit dem ersten Element der Liste arbeitest.

  • Antworte

    Ich heisse Marvin

  • Antworte

    Was bedeutet denn die Punktnotation bei der DVL ?

    z.b aktuellerKnoten.getSuccessor()

    • Hallo Mario, aktuellerKnoten ist ein Objekt und dieses Objekt besitzt die Methode getSuccessor(). Mit Hilfe der Punktnotation gibst du an von welchem Objekt du die Methode getSuccessor aufrufst. Viele Grüße Kim

  • Antworte

    Hey,
    super Tutorial. Eine Frage: bei deiner ersten implementierung von „LinkedList“ müsste man doch im dritten Fall den letzten Knoten noch einmal neu setzen, da der letzte Knoten immer noch auf dem aktuellen Knoten liegt?

    Schöne Grüße

    • Hallo Georg, vielen Dank für deinen Kommentar. Aktuell sehe ich keinen Fehler. Möglicherweise übersehe ich aber was, welche Code meinst du genau? Viele Grüße Kim

    • Hey Kim,

      Ich bin das Snipped noch einmal durch gegangen. Meine Frage war, warum du beim setzen eines neuen Knotens zwischen 2 bestehende Knoten keinen neuen letzten Knoten setzt.
      Ich habe aber im nachgang gemerkt, dass man das nicht muss, da man ja die struktur der äußeren Knoten nicht ändert.
      Trozdem danke.

      Grüße

  • Antworte

    Die next-Methode ist für Knoten geschrieben, wird dann aber auf dem Object-Iterator aufgerufen. Wie kann das funktionieren?
    Bei mir mit leicht abgewandeltem Code (String-Datentypen als content in den Knoten, statt Objekt-Daten) funktioniert es nicht.

    • Hallo Melanie, die Klasse Object ist der kleinste Nenner aller Klassen. Jede Klasse erbt automatisch von Object. Daher kannst du Object als Behälter für alles auffassen. Was funktioniert bei dir denn nicht? Erhälst du eine Fehlermeldung? Viele Grüße Kim

  • Antworte

    Hallo Kim,
    knallt deine Implementierung der Methode hasNext(), wenn der aktuelleKnoten NULL ist? Hier müsste doch eine NullPointerException fliegen oder?
    Und noch eine weitere Fragen: Wieso ist deine LinkedList vom Typ Object und nicht generisch und dadurch typsicher mithilfe von T implementiert?
    LG,
    Niklas

    • Hallo Niklas, ja, wenn aktuellerKnoten NULL ist, und man dann eine Methode aufruft fliegt eine NullpointerException. Allerdings sollte die Situation, dass aktuellerKnoten den Wert Null hat nicht eintreten. Anstatt mit Object kann man auch mit Generics arbeiten. Das setzt allerdings voraus, dass sich der Leser mit Generics auskennt und das will ich für diesen Artikel nicht voraussetzten. Viele Grüße Kim

Hinterlasse ein Kommentar