Felder und Listen SS12

Aus ProgrammingWiki

Listen

Eine Liste ist eine Datenstruktur. Beim deren Initialisierung die Anzahl der Listenelemente nicht bekannt ist. Listenelemente sind durch Zeiger auf ein oder mehrere benachbarte Elemente mit einander verkettet. Die Struktur einer Liste ist linear.

Beispiel

Einkaufsliste

Ein einfaches Beispiel ist die Einkaufsliste. Auf Ihr sind die alle Lebensmittel untereinander aufgeschrieben. Dabei stellen die Lebensmittel die Listenelemente dar.

Funktionen für die Einkaufsliste

Hat man beim Schreiben des Einkaufszettels etwas vergessen so kann man dies an jeder beliebigen Stelle des Zettel dazu schreiben. Auch wenn ein Lebensmittel zu viel auf der Liste steht, kann dies an jeder beliebigen Position entfernt werden. Auch kann die Reihenfolge der Lebensmittel auf der Liste beliebig verändert werden.

Einfach verkettete Listen

Wenn man eine solchen Einkaufszettel von oben nach unten Abarbeiten möchte, dabei nicht zurück springen muss, dann biete sich dafür eine einfach-verkettete-Liste an.

theoretischer Ansatz für einfach-verkettete-Listen

Die einfach-verkettete-Liste besteht aus einzelnen Listenelementen. Diese wiederum bestehen aus dem Inhalt des Elements und einem Verweis auf das nachfolgende Element. Damit man beim Zugreifen auf die Liste weis wo das erste Element liegt, wird ein leeres "Kopfelement" eingefügt welches nur den Zeiger auf das erste Element speichert. Wenn die Liste leer ist, dann verweist das Kopfelement auf "null".

Ein Listenelement kann wie folgt repräsentiert werden.

Die einfach-verkettete-Liste kann wie folgt umgesetzt werden. Diese Klasse stellt die Basis für alle anderen Funktionen für einfach-verkettete-Listen dar. Zusätzlich ist in der Basisklasse noch eine Funktion zum Ausgeben aller Listenelement enthalten.

public Object EinfachVerketteteListe() { Object kopf = ListenElement("h"); public void ausgabe() { Object le = kopf.holeNachfolger(); while(le != null){ System.out.println(le.holeElementdaten()); le = le.holeNachfolger(); } } public boolean istLeer() { if (kopf.holeNachfolger() == null) { return true; } else { return false; } } public Object holeListenkopf() { return kopf; } public Object holeErstesElement() { if (istLeer() == true) { return kopf; } else { return kopf.nachfolger; } } public Object holeLetztesElement() { Object le = kopf; while(le.holeNachfolger() != null){ le = le.holeNachfolger(); } return le; } public void einfgEnde(Object inhalt) { Object neues = ListenElement(inhalt); Object letztes = holeLetztesElement(); letztes.nachfolger = neues; } public void einfgStart(Object inhalt) { Object neues = ListenElement(inhalt); Object zeiger = kopf.nachfolger; kopf.nachfolger = neues; neues.nachfolger = zeiger; } public void einfgNach(Object vorfahre, Object inhalt) { Object neues, altes, zeiger; zeiger = kopf; while(zeiger != null && !zeiger.holeElementdaten().equals(vorfahre)) { zeiger = zeiger.holeNachfolger(); } neues = ListenElement(inhalt); altes = zeiger.holeNachfolger(); zeiger.nachfolger = neues; neues.nachfolger = altes; } public void einfgAmAnfang(Object inhalt) { einfgNach("h", inhalt); } public void einfgAmEnde(Object inhalt) { Object zeiger = holeLetztesElement().holeElementdaten(); einfgNach(zeiger, inhalt); } public void entf(Object inhalt) { Object le = kopf; while (le.holeNachfolger() != null && !le.holeElementdaten().equals(inhalt)){ if(le.holeNachfolger().holeElementdaten().equals(inhalt)){ if(le.holeNachfolger().holeNachfolger() != null){ le.nachfolger = le.holeNachfolger().holeNachfolger(); } else { le.nachfolger = null; break; } } le = le.holeNachfolger(); } } public void entferneBlock(Object start, Object ende) { Object le = kopf; Object zeigere = kopf; Object zeigers = null; while (le.holeNachfolger() != null && ( zeigers == null || zeigere == kopf)) { if(le.holeNachfolger().holeElementdaten().equals(start)){ zeigers = le; } if(le.holeElementdaten().equals(ende)){ zeigere = le.holeNachfolger(); } le = le.holeNachfolger(); } if (zeigere == kopf) { zeigere = null;} zeigers.nachfolger = zeigere; } public void entferneErstes() { Object zeiger = holeErstesElement().holeElementdaten(); entferneBlock(zeiger, zeiger); } public void entferneLetztes() { Object zeiger = holeLetztesElement().holeElementdaten(); entferneBlock(zeiger, zeiger); } public void entferneElement(Object zeiger) { entferneBlock(zeiger, zeiger); } public void listeLeeren() { kopf.nachfolger = null; } public void verschiebe(Object inhalt, Object position) { Object le = kopf; Object zeigerp = kopf; Object zeigerpn = kopf; Object zeigersn = kopf; Object zeigers = kopf; Object zeigersv = null; while (le != null && ( zeigersv == null || zeigerp == kopf || zeigersn == kopf || zeigerpn == kopf || zeigers == kopf)) { if (le.holeNachfolger() != null) { if(le.holeNachfolger().holeElementdaten().equals(inhalt)){ zeigersv = le; zeigers = le.holeNachfolger(); if (zeigers == null) { zeigersn = null; } else { zeigersn = zeigers.holeNachfolger(); } } } if(le.holeElementdaten().equals(position)){ zeigerp = le; zeigerpn = le.holeNachfolger(); } le = le.holeNachfolger(); } if (zeigerpn == kopf) { zeigerpn = null;} zeigersv.nachfolger = zeigersn; zeigerp.nachfolger = zeigers; zeigers.nachfolger = zeigerpn; } public void verschiebeBlockNach(Object start, Object ende, Object position) { Object le = kopf; Object zeigersv = null; Object zeigers = kopf; Object zeigere = kopf; Object zeigeren = kopf; Object zeigerp = kopf; Object zeigerpn = kopf; while (le != null && ( zeigersv == null || zeigers == kopf || zeigere == kopf || zeigeren == kopf || zeigerp == kopf || zeigerpn == kopf)) { if (le.holeNachfolger() != null) { if(le.holeNachfolger().holeElementdaten().equals(start)){ zeigersv = le; zeigers = le.holeNachfolger(); } } if(le.holeElementdaten().equals(ende)){ zeigere = le; zeigeren = le.holeNachfolger(); } if(le.holeElementdaten().equals(position)){ zeigerp = le; zeigerpn = le.holeNachfolger(); } le = le.holeNachfolger(); } if (zeigerpn == kopf) { zeigerpn = null;} zeigersv.nachfolger = zeigeren; zeigerp.nachfolger = zeigers; zeigere.nachfolger = zeigerpn; } public void verschiebeNach(Object inhalt, Object position) { verschiebeBlockNach(inhalt,inhalt,position); } public void verschiebeAnAnfang(Object inhalt) { verschiebeBlockNach(inhalt,inhalt,"h"); } public void verschiebeAnEnde(Object inhalt) { Object zeiger = holeLetztesElement().holeElementdaten(); verschiebeBlockNach(inhalt,inhalt,zeiger); } public void verschiebeBlockAnAnfang(Object start, Object ende) { verschiebeBlockNach(start,ende,"h"); } public void verschiebeBlockAnEnde(Object start, Object ende) { Object zeiger = holeLetztesElement().holeElementdaten(); verschiebeBlockNach(start,ende,zeiger); } return this; }

list = EinfachVerketteteListe(); list.ausgabe();

ausführen

Damit wäre der grundlegende Aufbau einer einfach-verketteten-Liste umgesetzt.

Funktionen für einfach-verkettete-Listen

Die grundlegende Funktionen einer solchen Liste sind das hinzufügen und löschen von Elementen. Dafür muss oft auf der erste beziehungsweise auf das letzte Element zugegriffen werden.

Kontrolle ob einfach-verkettete-Liste leer ist

Bevor eine Veränderung an der Liste vorgenommen wird, muss oft überprüft werden ob diese überhaupt einen Inhalt hat. Wenn der Zeiger des Kopfelements auf "null" zeigt ist die Liste leer

 public boolean istLeer() {
   if (kopf.holeNachfolger() == null) {
     return true;
   } else {
     return false;
   }
 } 

Zugriff auf das den Listenkopf für einfach-verkettete-Listen

Der Zugriff auf en Listenkopf erfolgt durch das zugreiffen auf die Klassenvariabel "kopf".

 public Object holeListenkopf() {
   return kopf;
 } 

Zugriff auf das erste Element für einfach-verkettete-Listen

Der Zugriff auf das erste Element ist relativ einfach, denn der Zeiger des Kopfes verweist stets auf das erste Element. Zu vor muss nur geprüft werden ob die Liste überhaupt eine Element enthält.

 if (istLeer() == false) {
   return kopf.nachfolger;
 } else {
   return kopf;
 }

Zugriff auf das letzte Element für einfach-verkettete-Listen

Der Zugriff auf das letzte Element ist Wesentlich aufwendiger, denn dafür muss die ganze Liste durchlaufen werden bis der Nachfolger des aktuellen Elements null ist.

 public Object holeLetztesElement() {
   Object le = kopf;
   while(le.holeNachfolger() != null){
     le = le.holeNachfolger();
   }
   return le;
 }

Das Einfügen am Ende der Liste für einfach-verkettete-Listen

Das Hinzufügen am Ende der Liste erfolgt in 2 Schritten.

1. Neues Element anlegen
2. Der Zeiger vom bis dahin letzten Element von "null" auf das neue Element ändern

 public void einfgEnde(Object inhalt) {
   Object neues = ListenElement(inhalt);
   Object letztes = holeLetztesElement();
   letztes.defiNachfolger(neues);
 }

list = EinfachVerketteteListe(); System.out.println("Ist die Liste leer: " + list.istLeer()); list.einfgEnde("Apfel"); list.einfgEnde("Birne"); list.einfgEnde("Kiwi"); list.ausgabe(); System.out.println("Listenkopf: " + list.holeListenkopf().holeElementdaten()); System.out.println("Erster Listenpunkt: " + list.holeErstesElement().holeElementdaten()); System.out.println("Letzter Listenpunkt: " + list.holeLetztesElement().holeElementdaten()); System.out.println("Ist die Liste leer: " + list.istLeer());

ausführen

Das Einfügen am Anfang der Liste für einfach-verkettete-Listen

Das Hinzufügen am Anfang der Liste gestaltet sich etwas schwieriger, denn hierfür sind 4 Schritte nötig.

1. Neues Listenelement mit dem übergebenen Inhalt erzeugt
2. Zeiger vom Kopfelement auf das bis dahin erste Element zwischenspeichern
3. Der Zeiger vom Kopfelement so ändern das er auf das neue Listenelement zeigt
4. Der Zeiger des neuen Elements auf den zwischengespeicherten Wert anpassen.

 public void einfgStart(Object inhalt) {
   Object neues = ListenElement(inhalt);
   Object zeiger = kopf.nachfolger;
   kopf.nachfolger = neues;
   neues.defiNachfolger(zeiger);
 }

liste = EinfachVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Kiwi"); liste.einfgStart("Käse"); liste.ausgabe();

ausführen

Das Einfügen nach einer beliebigen Position für einfach-verkettete-Listen

Das einfügen nach einer beliebigen Stelle ähnelt stark dem Einfügen am Ende der Liste. Im Unterschied dazu wird statt die Liste bis zum letzten Element zu durchlaufen, die Liste nur bis zur angegebenen Position durchlaufen. Diese Position wird dann gespeichert außer dem wird seperat der Zeiger auf das nachfolgende Element gespeichert. Im Anschluss wird wieder ein neues Element mit dem übergebenen Daten generiert. Danach wird der Zeiger vom angegebenen Element so geändert das er auf das neue Element verweist. Abschließend wird der Zeiger vom neuen Element so motiviziert das er das selbe Ziel hat der zu vor zwischengespeicherte Zeiger.

 public void einfgNach(Object vorfahre, Object inhalt) {
   Object neues, altes, zeiger;
   zeiger = kopf;
   while(zeiger != null && !zeiger.holeElementdaten().equals(vorfahre)) {
     zeiger = zeiger.holeNachfolger();
   }
   neues = ListenElement(inhalt);
   altes = zeiger.holeNachfolger();
   zeiger.nachfolger = neues;
   neues.nachfolger = altes;
 }

Object liste = EinfachVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Brot"); liste.einfgNach("Apfel","Käse"); liste.ausgabe();

ausführen

Vereinheitlichung der Funktionen zum Einfügen für einfach-verkettete-Listen

Die Funktionen zum Einfügen am Anfang und am Ende der Liste sind bei genauerem betrachten nur Sonderfälle der Funktion "einfgNach". Daher kann man die Funktionen vereinheitlichen.

Die Funktion zum Einfügen am Anfang der Liste stellt das Einfügen nach dem Kopfelement der Liste dar.

Die Funktion zum Einfügen am Ende der Liste ist das Einfügen nach dem letzten Element der Liste.

 public void einfgAmAnfang(Object inhalt) {
   einfgNach("h", inhalt);
 }

 public void einfgAmEnde(Object inhalt) {
   Object zeiger = holeLetztesElement().holeElementdaten();
   einfgNach(zeiger, inhalt);
 }

Object liste = EinfachVerketteteListe(); liste.einfgAmEnde("Apfel"); liste.einfgAmEnde("Birne"); liste.einfgAmEnde("Brot"); liste.einfgAmAnfang("Käse"); liste.ausgabe();

ausführen

Das Löschen eines Elements für einfach-verkettete-Listen

Das Löschen eines Elements erfolgt in 2 Schritten.

1. Durchlaufen der Liste bis ein Elementgefunden wird dessen Nachfolger dem angegebenen Element entspricht.
2. Ändern des Zeigers des Elements

Wenn das letzte Element der Liste gelöscht werden soll, dann muss der Zeiger auf "null" gesetzt werden. Sollte das zu entfernender Element einen Nachfolger haben, dann wird der Zeiger auf diesen geändert.

 public void entf(Object inhalt) {
   Object le = kopf;
   while (le.holeNachfolger() != null && !le.holeElementdaten().equals(inhalt)){
     if(le.holeNachfolger().holeElementdaten().equals(inhalt)){
       if(le.holeNachfolger().holeNachfolger() != null){
         le.defiNachfolger(le.holeNachfolger().holeNachfolger());
       } else {
         le.nachfolger = null;
         break;
       }
     }
     le = le.holeNachfolger();
   }
 }

Object liste = EinfachVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Brot"); liste.entf("Birne"); liste.ausgabe();

ausführen

Das Löschen mehrere zusammenhängender Elemente für einfach-verkettete-Listen

Für das Löschen mehrerer zusammenhängender Element wird die Funktion zum löschen eines Elements erweitert. Als Übergabewerte wird als erste der Startwert, dann der Endwert angegeben.

1. Speichern des Elements, dessen Nachfolger dem Startwert entspricht
2. Speichern des Zeigers auf das Element, dass auf den Endwert folgt
3. Anpassen des Zeigers vom Vorgänger des Startwertes so das dieser auf den Nachfolger des Endwertes zeigt

 public void entferneBlock(Object start, Object ende) {
   Object le = kopf;
   Object zeigere = kopf;
   Object zeigers = null;
   while (le.holeNachfolger() != null && ( zeigers == null || zeigere == kopf)) {
     if(le.holeNachfolger().holeElementdaten().equals(start)){
       zeigers = le;
     }
     if(le.holeElementdaten().equals(ende)){
       zeigere = le.holeNachfolger();
     }
     le = le.holeNachfolger();
   }
   if (zeigere == kopf) { zeigere = null;}
   zeigers.defiNachfolger(zeigere);
 }

Object liste = EinfachVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Wasser"); liste.einfgEnde("Saft"); liste.einfgEnde("Brot"); liste.entferneBlock("Birne","Saft"); liste.ausgabe();

ausführen

Hinweis: Die Listenelement werde nicht wirdklich gelöscht, es werden nur die Zeiger auf diese Element gelöscht.

Vereinheitlichung der Löschenfunktionen für einfach-verkettete-Listen

Auch hier stellt das einfache Löschen wieder einen Sonderfall der Funktion zum Löschen einem Abschnitt aus der Liste dar. Wenn man als Startwert und als Endwert den Wert, der beim einfachen Löschen übergeben wird verwendet, dann wird genau das eine Element gelöscht.

Außerdem lassen sich auf diese Weise 2 Sonderfälle abwickeln.

Zum einen das Löschen des ersten Elements. Dabei wird über die Funktion zum Holen des ersten Elements das erste Element ermittelt und als Start- und Endwert übergeben an die Funktion zum Löschen eines Abschnittes aus der Liste.

Ganz ähnlich geht man beim Löschen des letzten Elements der Liste vor. Dabei ruft man über die Funktion holeletzteElement das Letzte Element ab und übergibt diese wieder an die Funktion.

 public void entferneErstes() {
   Object zeiger = holeErstesElement().holeElementdaten();
   entferneBlock(zeiger, zeiger);
 }

 public void entferneLetztes() {
   Object zeiger = holeLetztesElement().holeElementdaten();
   entferneBlock(zeiger, zeiger);
 }

 public void entferneElement(Object zeiger) {
   entferneBlock(zeiger, zeiger);
 }

Object liste = EinfachVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Wasser"); liste.einfgEnde("Saft"); liste.einfgEnde("Brot"); liste.entferneErstes(); liste.entferneLetztes(); liste.entferneElement("Wasser"); liste.ausgabe();

ausführen

Leeren einer Liste für einfach-verkettete-Listen

Auch das leeren der Liste könnte man über die Löschfunktion erledigen durch die Übergabe des ersten und letzten Wertes. Einfach ist es aber einfach den Zeiger vom Kopfelement auf "null" zusetzten. Damit werden alle Verweise auf Listenelemente gelöscht.

 public void listeLeeren() {
   kopf.defiNachfolger(null);
 }

Object liste = EinfachVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Wasser"); liste.einfgEnde("Saft"); liste.einfgEnde("Brot"); liste.listeLeeren(); liste.ausgabe();

ausführen

Das Verschieben eines Elements für einfach-verkettete-Listen

Die Funktion zum Verschieben von einem Element hinter ein anderes Element lässt sich wie folgt realisieren und hat 7 Schritte. Dabei müssen folgende Wert übergeben werden: das Element was verschoben werden soll und das Element nach dem es eingefügt werden soll.

1. Ermitteln des Elements dessen Nachfolger das zu verschiebende Element ist und Speichern in zB.: elementInhaltVorganger.
2. Ermitteln des Elements das auf das zu verschiebende Element folgt und Speichern in zB.: elementInhaltNachfolger.
3. Ermitteln des Elements nach dem eingefügt werden soll und Speichern in zB.: elementPosition.
4. Ermitteln des Elements das auf das Element folgt nach dem der Wert eingefügt werden soll und Speichern in zB.: elementPositionNachfolger.
5. Den Zeiger von elementInhaltVorganger so setzten das er auf elementInhaltNachfolger zeigt.
6. Den Zeiger von elementPosition so ändern das er auf das zu verschiebende Element zeigt.
7. Den Zeiger vom verschobenen Elment so anpassen das er auf elementPositionNachfolger verweist.

 public void verschiebe(Object inhalt, Object position) {
   Object le = kopf;
   Object zeigerp = kopf;
   Object zeigerpn = kopf;
   Object zeigersn = kopf;
   Object zeigers = kopf;
   Object zeigersv = null;
   while (le != null && ( zeigersv == null || zeigerp == kopf || zeigersn == kopf || zeigerpn == kopf || zeigers == kopf)) {
     if (le.holeNachfolger() != null) {
       if(le.holeNachfolger().holeElementdaten().equals(inhalt)){
         zeigersv = le;
         zeigers = le.holeNachfolger();
         if (zeigers == null) { zeigersn = null; } else  { zeigersn = zeigers.holeNachfolger(); }
       }
     }
     if(le.holeElementdaten().equals(position)){
       zeigerp = le;
       zeigerpn = le.holeNachfolger();
     }
     le = le.holeNachfolger();
   }
   if (zeigerpn == kopf) { zeigerpn = null;}
   zeigersv.defiNachfolger(zeigersn);
   zeigerp.defiNachfolger(zeigers);
   zeigers.defiNachfolger(zeigerpn);
 }

Object liste = EinfachVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Wasser"); liste.einfgEnde("Saft"); liste.einfgEnde("Brot"); liste.verschiebe("Apfel","Birne"); liste.ausgabe();

ausführen

Das Verschieben mehrere zusammenhängender Elemente für einfach-verkettete-Listen

Die Funktion zum Verschieben von mehreren zusammenhängenden Elementen hinter ein anderes Element lässt sich wie folgt realisieren und hat 7 Schritte. Dabei müssen folgende Wert übergeben werden: das Startelement und das Endelement welche verschoben werden sollen und das Element nach dem sie eingefügt werden sollen.

1. Ermitteln des Elements dessen Nachfolger das zuverschiebende Startelement ist und Speichern in zB.: elementStartVorganger.
2. Ermitteln des Elements das auf das zu verschiebende Endelement folgt und Speichern in zB.: elementEndeNachfolger.
3. Ermitteln des Elements nach dem eingefügt werden soll und Speichern in zB.: elementPosition.
4. Ermitteln des Elements das auf das Element folgt nach dem der Wert eingefügt werden soll und Speichern in zB.: elementPositionNachfolger.
5. Den Zeiger von elementStartVorganger so setzten das er auf elementEndeNachfolger zeigt.
6. Den Zeiger von elementPosition so ändern das er auf das zu verschiebende Startelement zeigt.
7. Den Zeiger vom verschobenen Endelment so anpassen das er auf elementPositionNachfolger verweist.

 public void verschiebeBlockNach(Object start, Object ende, Object position) {
   Object le = kopf;
   Object zeigersv = null;
   Object zeigers = kopf;
   Object zeigere = kopf;
   Object zeigeren = kopf;
   Object zeigerp = kopf;
   Object zeigerpn = kopf;
   while (le != null && ( zeigersv == null || zeigers == kopf || zeigere == kopf || zeigeren == kopf || zeigerp == kopf || zeigerpn == kopf)) {
     if (le.holeNachfolger() != null) {
       if(le.holeNachfolger().holeElementdaten().equals(start)){
         zeigersv = le;
         zeigers = le.holeNachfolger();
       }
     }
     if(le.holeElementdaten().equals(ende)){
       zeigere = le;
       zeigeren = le.holeNachfolger();
     }      if(le.holeElementdaten().equals(position)){
       zeigerp = le;
       zeigerpn = le.holeNachfolger();
     }      le = le.holeNachfolger();
   }
   if (zeigerpn == kopf) { zeigerpn = null;}
   zeigersv.defiNachfolger(zeigeren);
   zeigerp.defiNachfolger(zeigers);
   zeigere.defiNachfolger(zeigerpn);
 }

Object liste = EinfachVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Wasser"); liste.einfgEnde("Saft"); liste.einfgEnde("Brot"); liste.verschiebeBlockNach("Birne","Wasser","Saft"); liste.ausgabe();

ausführen

Vereinheitlichung der Verschiebefunktionen für einfach-verkettete-Listen

Auch hier lassen sich die Funktionen zum Verschieben wieder alle durch die Funktion verschiebeBlockNach realisieren.

Beim Verschieben von nur einem Element, wird einfach der Startwert und Endwert gleichgesetzt.

Beim Verschieben an den Anfang wird als Position der Listenkopf übergeben, der Rest wird je nach Bedarf genutzt.

Beim Verschieben an das Ende wird als Position das letzte Element übergeben, der Rest wird je nach Bedarf genutzt.

 public void verschiebeNach(Object inhalt, Object position) {
   verschiebeBlockNach(inhalt,inhalt,position);
 }

 public void verschiebeAnAnfang(Object inhalt) {
   verschiebeBlockNach(inhalt,inhalt,"h");
 }

 public void verschiebeAnEnde(Object inhalt) {
   Object zeiger = holeLetztesElement().holeElementdaten();
   verschiebeBlockNach(inhalt,inhalt,zeiger);
 }

 public void verschiebeBlockAnAnfang(Object start, Object ende) {
   verschiebeBlockNach(start,ende,"h");
 }

 public void verschiebeBlockAnEnde(Object start, Object ende) {
   Object zeiger = holeLetztesElement().holeElementdaten();
   verschiebeBlockNach(start,ende,zeiger);
 }

Object liste = EinfachVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Wasser"); liste.einfgEnde("Saft"); liste.einfgEnde("Brot"); liste.verschiebeNach("Wasser","Saft"); liste.verschiebeAnAnfang("Brot"); liste.verschiebeAnEnde("Saft"); liste.verschiebeBlockAnAnfang("Birne","Saft"); liste.verschiebeBlockAnEnde("Wasser","Brot"); liste.ausgabe();

ausführen

Doppelt verkettete Listen

Wenn beim Abarbeiten eines Einkaufszettel nicht nur von oben nach unten sondern auch anders herum, dann empfiehlt es eine doppelt-verkettete-Liste zu verwenden.

theoretischer Ansatz

Die doppelt-verkettete-Liste besteht aus einzelnen Listenelementen. Diese wiederum bestehen aus dem Inhalt des Elements und einem Verweis auf das nachfolgende Element und das vorausgegangene Element. Damit man beim Zugreifen auf die Liste weis wo das erste und das letzte Element liegt, wird ein leeres "Kopfelement" eingefügt welches nur den Zeiger auf das erste und das letzte Element speichert. Wenn die Liste leer ist, dann verweist das Kopfelement auf "null".

Ein Listenelement kann wie folgt repräsentiert werden.

Die doppelt-verkettete-Liste kann wie folgt umgesetzt werden. Diese Klasse stellt die Basis für alle anderen Funktionen für doppelt-verkettete-Listen dar. Zusätzlich ist in der Basisklasse noch eine Funktion zum Ausgeben aller Listenelement enthalten.

 public Object DoppeltVerketteteListe() {

   Object kopf = DListenElement("h");

   kopf.nachfolger = kopf;
   kopf.vorganger = kopf;

   public void ausgabe() {
     Object le = kopf.holeNachfolger();
     while(le != kopf){
       System.out.println(le.holeElementdaten());
       le = le.holeNachfolger();
     }
   }
 
   return this;
 }

public Object DoppeltVerketteteListe() { Object kopf = DListenElement("h"); kopf.nachfolger = kopf; kopf.vorganger = kopf; public void ausgabe() { Object le = kopf.holeNachfolger(); while(le != kopf){ System.out.println(le.holeElementdaten()); le = le.holeNachfolger(); } } public boolean istLeer() { if (kopf.holeNachfolger() == kopf) { return true; } else { return false; } } public Object holeListenkopf() { return kopf; } public Object holeErstesElement() { if (istLeer() == false) { return kopf.nachfolger; } else { return kopf; } } public Object holeLetztesElement() { if (istLeer() == false) { return kopf.vorganger; } else { return kopf; } } public void einfgEnde(Object inhalt) { Object neues = DListenElement(inhalt); Object letztes = holeLetztesElement(); letztes.nachfolger = neues; neues.nachfolger = kopf; kopf.vorganger = neues; neues.vorganger = letztes; } public void einfgStart(Object inhalt) { Object neues = DListenElement(inhalt); Object zeiger = kopf.nachfolger; kopf.nachfolger = neues; neues.nachfolger = zeiger; zeiger.vorganger = neues; neues.vorganger = kopf; } public void einfgNach(Object vorfahre, Object inhalt) { Object neues, altes, zeiger; zeiger = kopf; while(zeiger.holeNachfolger != null && !zeiger.holeElementdaten().equals(vorfahre)) { zeiger = zeiger.holeNachfolger(); } neues = DListenElement(inhalt); altes = zeiger.holeNachfolger(); zeiger.nachfolger = neues; neues.nachfolger = altes; altes.vorganger = neues; neues.vorganger = zeiger; } public void einfgAmAnfang(Object inhalt) { einfgNach("h", inhalt); } public void einfgAmEnde(Object inhalt) { Object zeiger = holeLetztesElement().holeElementdaten(); einfgNach(zeiger, inhalt); } public void entf(Object inhalt) { Object le = kopf; Object zeigere = null; Object zeigers = null; while (le.holeNachfolger() != kopf && ( zeigers == null || zeigere == null)) { if(le.holeElementdaten().equals(inhalt)){ zeigers = le.holeVorganger(); zeigere = le.holeNachfolger(); } le = le.holeNachfolger(); } if (zeigere == null) { zeigere = kopf;} zeigers.nachfolger = zeigere; zeigere.vorganger = zeigers; } public void entferneBlock(Object start, Object ende) { Object le = kopf.holeNachfolger(); Object zeigere = null; Object zeigers = null; while (le != kopf && ( zeigers == null || zeigere == null)) { if(le.holeElementdaten().equals(start)){ zeigers = le.holeVorganger(); } if(le.holeElementdaten().equals(ende)){ zeigere = le.holeNachfolger(); } le = le.holeNachfolger(); } zeigers.nachfolger = zeigere; zeigere.vorganger = zeigers; } public void entferneErstes() { Object zeiger = holeErstesElement().holeElementdaten(); entferneBlock(zeiger, zeiger); } public void entferneLetztes() { Object zeiger = holeLetztesElement().holeElementdaten(); entferneBlock(zeiger, zeiger); } public void entferneElement(Object zeiger) { entferneBlock(zeiger, zeiger); } public void listeLeeren() { kopf.nachfolger = kopf; kopf.vorganger = kopf; } public void verschiebe(Object inhalt, Object position) { Object le = kopf.holeNachfolger(); Object zeigerp = null; Object zeigerpn = null; Object zeigersn = null; Object zeigers = null; Object zeigersv = null; while (le != kopf && ( zeigersv == null || zeigers == null || zeigersn == null || zeigerp == null || zeigerpn == null)) { if(le.holeElementdaten().equals(inhalt)){ zeigersv = le.holeVorganger(); zeigers = le; zeigersn = le.holeNachfolger(); } if(le.holeElementdaten().equals(position)){ zeigerp = le; zeigerpn = le.holeNachfolger(); } le = le.holeNachfolger(); } if ( zeigersv != null && zeigers != null && zeigersn != null && zeigerp != null && zeigerpn != null) { zeigersv.nachfolger = zeigersn; zeigersn.vorganger = zeigersv; zeigerp.nachfolger = zeigers; zeigers.vorganger = zeigerp; zeigers.nachfolger = zeigerpn; zeigerpn.vorganger = zeigers; } } public void verschiebeBlockNach(Object start, Object ende, Object position) { Object le = kopf.holeNachfolger(); Object zeigersv = null; Object zeigers = null; Object zeigere = null; Object zeigeren = null; Object zeigerp = null; Object zeigerpn = null; while (le != kopf && ( zeigersv == null || zeigers == null || zeigere == null || zeigeren == null || zeigerp == null || zeigerpn == null)) { if(le.holeElementdaten().equals(start)){ zeigersv = le.holeVorganger(); zeigers = le; } if(le.holeElementdaten().equals(ende)){ zeigere = le; zeigeren = le.holeNachfolger(); } if(le.holeElementdaten().equals(position)){ zeigerp = le; zeigerpn = le.holeNachfolger(); } le = le.holeNachfolger(); } if (zeigersv != null && zeigers != null && zeigere != null && zeigeren != null && zeigerp != null && zeigerpn != null) { zeigersv.nachfolger = zeigeren; zeigeren.vorganger = zeigersv; zeigerp.nachfolger = zeigers; zeigers.vorganger = zeigerp; zeigere.nachfolger = zeigerpn; zeigerpn.vorganger = zeigere; } } public void verschiebeNach(Object inhalt, Object position) { verschiebeBlockNach(inhalt,inhalt,position); } public void verschiebeAnAnfang(Object inhalt) { verschiebeBlockNach(inhalt,inhalt,"h"); } public void verschiebeAnEnde(Object inhalt) { Object zeiger = holeLetztesElement().holeElementdaten(); verschiebeBlockNach(inhalt,inhalt,zeiger); } public void verschiebeBlockAnAnfang(Object start, Object ende) { verschiebeBlockNach(start,ende,"h"); } public void verschiebeBlockAnEnde(Object start, Object ende) { Object zeiger = holeLetztesElement().holeElementdaten(); verschiebeBlockNach(start,ende,zeiger); } return this; }

Object list = DoppeltVerketteteListe(); list.ausgabe();

ausführen

Damit wäre der grundlegende Aufbau einer doppelt-verketteten-Liste umgesetzt.

Funktionen

Die grundlegende Funktionen einer solchen Liste sind das hinzufügen und löschen von Elementen. Dafür muss oft auf der erste beziehungsweise auf das letzte Element zugegriffen werden.

Kontrolle ob doppelt-verkettete-Liste leer ist

Bevor eine Veränderung an der Liste vorgenommen wird, muss oft überprüft werden ob diese überhaupt einen Inhalt hat. Wenn der Zeiger vom Nachfolger des Kopfelements auf das Kopfelement zeigt ist die Liste leer

 public boolean istLeer() {
   if (kopf.holeNachfolger() == kopf) {
     return true;
   } else {
     return false;
   }
 } 

Zugriff auf das den Listenkopf der doppelt-verkettete-Liste

Der Zugriff auf en Listenkopf erfolgt durch das zugreiffen auf die Klassenvariabel "kopf".

 public Object holeListenkopf() {
   return kopf;
 } 

Zugriff auf das erste Element der doppelt-verkettetet-Liste

Der Zugriff auf das erste Element ist relativ einfach, denn der Zeiger des Kopfes verweist stets auf das erste Element. Zu vor muss nur geprüft werden ob die Liste überhaupt eine Element enthält.

 public Object holeErstesElement() {
   if (istLeer() == false) {
     return kopf.nachfolger;
   } else {
     return kopf;
   }
 }

Zugriff auf das letzte Element von doppelt-verketteten-Listen

Der Zugriff auf das letzte Element ist genauso einfach. Der Zeiger vom Kopf auf den Vorgänger des Kopfes zeigt direkt auf das letzte Element.

 public Object holeLetztesElement() {
   if (istLeer() == false) {
     return kopf.vorganger;
   } else {
     return kopf;
   }
 } 

Das Einfügen am Ende der doppelt-verketteten-Liste

Das Hinzufügen am Ende der Liste ist nun relativ einfach und kann in konstanter Zeit durchgeführt werden.

1. Neues Element anlegen
2. Der Zeiger vom Kopfelement auf das letzte Element so ändern das er auf das neue Element verweist und diesen dann erst auf das alte letzte Element verweist
3. Der Zeiger vom bis dahin letzten Element so anpassen das er ebenfalls auf das neue Element verweist und dieses dann auf das Kopfelement

 public void einfgEnde(Object inhalt) {
   Object neues = DListenElement(inhalt);
   Object letztes = holeLetztesElement();
   letztes.defiNachfolger(neues);
   neues.defiNachfolger(kopf);
   kopf.defiVorganger(neues);
   neues.defiVorganger(altes);
 }

Object list = DoppeltVerketteteListe(); System.out.println("Ist die Liste leer: " + list.istLeer()); list.einfgEnde("Apfel"); list.einfgEnde("Birne"); list.einfgEnde("Kiwi"); list.ausgabe(); System.out.println("Listenkopf: " + list.holeListenkopf().holeElementdaten()); System.out.println("Erster Listenpunkt: " + list.holeErstesElement().holeElementdaten()); System.out.println("Letzter Listenpunkt: " + list.holeLetztesElement().holeElementdaten()); System.out.println("Ist die Liste leer: " + list.istLeer());

ausführen

Das Einfügen am Anfang der doppelt-verketteten-Liste

Das Hinzufügen am Anfang der Liste gestaltet sich etwas schwieriger, denn hierfür sind 4 Schritte nötig.

1. Neues Listenelement mit dem übergebenen Inhalt erzeugen
2. Zeiger vom Kopfelement auf das bis dahin erste Element zwischenspeichern
3. Der Zeiger vom Kopfelement so ändern das er auf das neue Listenelement zeigt und dieses dann auf das alte erste Element
4. Der Zeiger vom alten ersten Element so ändern das dieser auf das neuen Elements verweist und diese Element dann auf das Kopfelement

 public void einfgStart(Object inhalt) {
   Object neues = DListenElement(inhalt);
   Object zeiger = kopf.nachfolger;
   kopf.defiNachfolger(neues);
   neues.defiNachfolger(zeiger);
   zeiger.defiVorganger(neues);
   neues.defiVorganger(kopf);
 }

Object liste = DoppeltVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Kiwi"); liste.einfgStart("Käse"); liste.ausgabe();

ausführen

Das Einfügen nach einer beliebigen Position in der doppelt-verketteten-Liste

1. Liste bis zur angegebenen Position durchlaufen
2. Position und Zeiger auf den Nachfolger speichern
3. Neues Element mit dem übergebenen Daten generieren
4. Den Zeiger vom angegebenen Element so ändern das er auf das neue Element verweist und dieses dann auf den alten Nachfolger der angegebenen Position
5. Den Zeiger vom ehemaligen Nachfolger der angegebene Psoition so ändern das dieser auf das neuen Element und dieses auf die angegebene Position verweist

 public void einfgNach(Object vorfahre, Object inhalt) {
   Object neues, altes, zeiger;
   zeiger = kopf;
   while(zeiger.holeNachfolger != null && !zeiger.holeElementdaten().equals(vorfahre)) {
     zeiger = zeiger.holeNachfolger();
   }
   neues = DListenElement(inhalt);
   altes = zeiger.holeNachfolger();
   zeiger.defiNachfolger(neues);
   neues.defiNachfolger(altes);
   altes.defiVorganger(neues);
   neues.defiVorganger(zeiger);
 }

Object liste = DoppeltVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Brot"); liste.einfgNach("Apfel","Käse"); liste.ausgabe();

ausführen

Vereinheitlichung der Funktionen zum Einfügen in eine doppelt-verkettete-Liste

Die Funktionen zum Einfügen am Anfang und am Ende der Liste sind bei genauerem betrachten nur Sonderfälle der Funktion "einfgNach". Daher kann man die Funktionen vereinheitlichen.

Die Funktion zum Einfügen am Anfang der Liste stellt das Einfügen nach dem Kopfelement der Liste dar.

Die Funktion zum Einfügen am Ende der Liste ist das Einfügen nach dem letzten Element der Liste.

 public void einfgAmAnfang(Object inhalt) {
   einfgNach("h", inhalt);
 }

 public void einfgAmEnde(Object inhalt) {
   Object zeiger = holeLetztesElement().holeElementdaten();
   einfgNach(zeiger, inhalt);
 }

Object liste = DoppeltVerketteteListe(); liste.einfgAmEnde("Apfel"); liste.einfgAmEnde("Birne"); liste.einfgAmEnde("Brot"); liste.einfgAmAnfang("Käse"); liste.ausgabe();

ausführen

Das Löschen eines Elements aus einer doppelt-verketteten-Liste

Das Löschen eines Elements erfolgt in 3 Schritten.

1. Liste durchlaufen bis das angegebene Element gefunden wird
2. Den Vorgänger und den Nachfolger zwischenspeichern
3. Zeiger des Vorgängers auf den Nachfolger ändern
4. Zeiger des Nachfolgers auf den Vorgänger ändern

 public void entf(Object inhalt) {
   Object le = kopf.holeNachfolger;
   Object zeigere = null;
   Object zeigers = null;
   while (le != kopf && ( zeigers == null || zeigere == null)) {
     if(le.holeElementdaten().equals(inhalt)){
       zeigers = le.holeVorganger();
       zeigere = le.holeNachfolger();
     }
     le = le.holeNachfolger();
   }
   if (zeigere == null) { zeigere = kopf;}
   zeigers.defiNachfolger(zeigere);
   zeigere.defiVorganger(zeigers);
 }

Object liste = DoppeltVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Brot"); liste.entf("Birne"); liste.ausgabe();

ausführen

Das Löschen mehrere zusammenhängender Elemente aus einer doppelt-verketteten-Liste

Für das Löschen mehrerer zusammenhängender Element wird die Funktion zum löschen eines Elements erweitert. Als Übergabewerte wird als erste der Startwert, dann der Endwert angegeben.

1. Speichern des Vorgängers des Startwertes und des Nachfolger des Endwertes
2. Zeiger des Vorgängers zeigt auf Nachfolger
3. Zeiger des Nachfolgers zeigt auf Vorgänger

 public void entferneBlock(Object start, Object ende) {
   Object le = kopf.holeNachfolger();
   Object zeigere = null;
   Object zeigers = null;
   while (le != kopf && ( zeigers == null || zeigere == null)) {
     if(le.holeElementdaten().equals(start)){
       zeigers = le.holeVorganger();
     }
     if(le.holeElementdaten().equals(ende)){
       zeigere = le.holeNachfolger();
     }
     le = le.holeNachfolger();
   }
   zeigers.defiNachfolger(zeigere);
   zeigere.defiVorganger(zeigers);
 }

Object liste = DoppeltVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Wasser"); liste.einfgEnde("Saft"); liste.einfgEnde("Brot"); liste.entferneBlock("Birne","Saft"); liste.ausgabe();

ausführen

Hinweis: Die Listenelement werde nicht wirdklich gelöscht, es werden nur die Zeiger auf diese Element gelöscht.

Vereinheitlichung der Löschenfunktionen für eine doppelt-verkettete-Liste

Auch hier stellt das einfache Löschen wieder einen Sonderfall der Funktion zum Löschen einem Abschnitt aus der Liste dar. Wenn man als Startwert und als Endwert den Wert, der beim einfachen Löschen übergeben wird verwendet, dann wird genau das eine Element gelöscht.

Außerdem lassen sich auf diese Weise 2 Sonderfälle abwickeln.

Zum einen das Löschen des ersten Elements. Dabei wird über die Funktion zum Holen des ersten Elements das erste Element ermittelt und als Start- und Endwert übergeben an die Funktion zum Löschen eines Abschnittes aus der Liste.

Ganz ähnlich geht man beim Löschen des letzten Elements der Liste vor. Dabei ruft man über die Funktion holeletzteElement das Letzte Element ab und übergibt diese wieder an die Funktion.

 public void entferneErstes() {
   Object zeiger = holeErstesElement().holeElementdaten();
   entferneBlock(zeiger, zeiger);
 }

 public void entferneLetztes() {
   Object zeiger = holeLetztesElement().holeElementdaten();
   entferneBlock(zeiger, zeiger);
 }

 public void entferneElement(Object zeiger) {
   entferneBlock(zeiger, zeiger);
 }

Object liste = DoppeltVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Wasser"); liste.einfgEnde("Saft"); liste.einfgEnde("Brot"); liste.entferneErstes(); liste.entferneLetztes(); liste.entferneElement("Wasser"); liste.ausgabe();

ausführen

Leeren einer doppelt-verketteten-Liste

Auch das leeren der Liste könnte man über die Löschfunktion erledigen durch die Übergabe des ersten und letzten Wertes. Einfach ist es aber einfach die Zeiger vom Kopfelement auf "kopf" zusetzten. Damit werden alle Verweise auf Listenelemente gelöscht.

 public void listeLeeren() {
   kopf.defiNachfolger(kopf);
   kopf.defiVorganger(kopf);
 }

Object liste = DoppeltVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Wasser"); liste.einfgEnde("Saft"); liste.einfgEnde("Brot"); liste.listeLeeren(); liste.ausgabe();

ausführen

Das Verschieben eines Elements in einer doppelt-verketteten-Liste

Die Funktion zum Verschieben von einem Element hinter ein anderes Element lässt sich wie folgt realisieren und hat 10 Schritte. Dabei müssen folgende Wert übergeben werden: das Element was verschoben werden soll und das Element nach dem es eingefügt werden soll.

1. Speichern des Vorgängers des zu verschiebenden Elements in zB.: elementInhaltVorganger.
2. Speichern des Nachfolgers des zu verschiebenden Elements in zB.: elementInhaltNachfolger.
3. Speichern des Elements nach dem Eingefügt werden soll in zB.: elementPosition.
4. Speichern des Elements des Nachfolgers von elementPosition in zB.: elementPositionNachfolger.
5. Den Nachfolgerzeiger von elementInhaltVorganger so setzten das er auf elementInhaltNachfolger zeigt.
6. Den Vorgängerzeiger von elementInhaltNachfolger so setzten das er auf elementInhaltVorganger zeigt.
7. Den Nachfolgerzeiger von elementPosition so ändern das er auf das zu verschiebende Element zeigt.
8. Den Vorgängerzeiger von dem zu verschiebenden Element s o ändern das er auf elementPosition zeigt.
9. Den Nachfolgerzeiger vom verschobenen Elment so anpassen das er auf elementPositionNachfolger verweist.
10. Den Vorgängererzeiger von elementPositionNachfolger anpassen so das er auf das zu verschiebende Elment verweist.

 public void verschiebe(Object inhalt, Object position) {
   Object le = kopf.holeNachfolger();
   Object zeigerp = null;
   Object zeigerpn = null;
   Object zeigersn = null;
   Object zeigers = null;
   Object zeigersv = null;
   while (le != kopf && ( zeigersv == null || zeigers == null || zeigersn == null || zeigerp == null || zeigerpn == null)) {
     if(le.holeElementdaten().equals(inhalt)){
       zeigersv = le.holeVorganger();
       zeigers = le;
       zeigersn = le.holeNachfolger();
     }
     if(le.holeElementdaten().equals(position)){
       zeigerp = le;
       zeigerpn = le.holeNachfolger();
     }
     le = le.holeNachfolger();
   }
   if ( zeigersv != null && zeigers != null && zeigersn != null && zeigerp != null && zeigerpn != null) {
     zeigersv.defiNachfolger(zeigersn);
     zeigersn.defiVorganger(zeigersv);
     zeigerp.defiNachfolger(zeigers);
     zeigers.defiVorganger(zeigerp);
     zeigers.defiNachfolger(zeigerpn);
     zeigerpn.defiVorganger(zeigers);
 }

Object liste = DoppeltVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Wasser"); liste.einfgEnde("Saft"); liste.einfgEnde("Brot"); liste.verschiebe("Apfel","Birne"); liste.ausgabe();

ausführen

Das Verschieben mehrere zusammenhängender Elemente in doppelt-verkettete-Liste

Die Funktion zum Verschieben von mehreren zusammenhängenden Elementen hinter ein anderes Element lässt sich wie folgt realisieren und hat 10 Schritte. Dabei müssen folgende Wert übergeben werden: das Startelement und das Endelement welche verschoben werden sollen und das Element nach dem sie eingefügt werden sollen.

1. Speichern des Vorgängers des zu verschiebenden Startelements in zB.: elementStartVorganger.
2. Speichern des Nachfolgers des zu verschiebenden Endelements in zB.: elementEndeNachfolger.
3. Speichern des Elements nach dem Eingefügt werden soll in zB.: elementPosition.
4. Speichern des Elements des Nachfolgers von elementPosition in zB.: elementPositionNachfolger.
5. Den Nachfolgerzeiger von elementStartVorganger so setzten das er auf elementEndeNachfolger zeigt.
6. Den Vorgängerzeiger von elementEndeNachfolger so setzten das er auf elementStartVorganger zeigt.
7. Den Nachfolgerzeiger von elementPosition so ändern das er auf das zu verschiebende Startelement zeigt.
8. Den Vorgängerzeiger von dem zu verschiebenden Startelement so ändern das er auf elementPosition zeigt.
9. Den Nachfolgerzeiger vom verschobenen EndElment so anpassen das er auf elementPositionNachfolger verweist.
10. Den Vorgängererzeiger von elementPositionNachfolger anpassen so das er auf das zu verschiebende Endelement verweist.

 public void verschiebeBlockNach(Object start, Object ende, Object position) {
   Object le = kopf.holeNachfolger();
   Object zeigersv = null;
   Object zeigers = null;
   Object zeigere = null;
   Object zeigeren = null;
   Object zeigerp = null;
   Object zeigerpn = null;
   while (le != kopf && ( zeigersv == null || zeigers == null || zeigere == null || zeigeren == null || zeigerp == null || zeigerpn == null)) {
     if(le.holeElementdaten().equals(start)){
       zeigersv = le.holeVorganger();
       zeigers = le;
     }
     if(le.holeElementdaten().equals(ende)){
       zeigere = le;
       zeigeren = le.holeNachfolger();
     }
     if(le.holeElementdaten().equals(position)){
       zeigerp = le;
       zeigerpn = le.holeNachfolger();
     }
     le = le.holeNachfolger();
   }
   if (zeigersv != null && zeigers != null && zeigere != null && zeigeren != null && zeigerp != null && zeigerpn != null) {
     zeigersv.defiNachfolger(zeigeren);
     zeigeren.defiVorganger(zeigersv);
     zeigerp.defiNachfolger(zeigers);
     zeigers.defiVorganger(zeigerp);
     zeigere.defiNachfolger(zeigerpn);
     zeigerpn.defiVorganger(zeigere);
   }
 }

Object liste = DoppeltVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Wasser"); liste.einfgEnde("Saft"); liste.einfgEnde("Brot"); liste.verschiebeBlockNach("Birne","Wasser","Saft"); liste.ausgabe();

ausführen

Vereinheitlichung der Verschiebefunktionen für doppelt-verkettete-Listen

Auch hier lassen sich die Funktionen zum Verschieben wieder alle durch die Funktion verschiebeBlockNach realisieren.

Beim Verschieben von nur einem Element, wird einfach der Startwert und Endwert gleichgesetzt.

Beim Verschieben an den Anfang wird als Position der Listenkopf übergeben, der Rest wird je nach Bedarf genutzt.

Beim Verschieben an das Ende wird als Position das letzte Element übergeben, der Rest wird je nach Bedarf genutzt.

 public void verschiebeNach(Object inhalt, Object position) {
   verschiebeBlockNach(inhalt,inhalt,position);
 }

 public void verschiebeAnAnfang(Object inhalt) {
   verschiebeBlockNach(inhalt,inhalt,"h");
 }

 public void verschiebeAnEnde(Object inhalt) {
   Object zeiger = holeLetztesElement().holeElementdaten();
   verschiebeBlockNach(inhalt,inhalt,zeiger);
 }

 public void verschiebeBlockAnAnfang(Object start, Object ende) {
   verschiebeBlockNach(start,ende,"h");
 }

 public void verschiebeBlockAnEnde(Object start, Object ende) {
   Object zeiger = holeLetztesElement().holeElementdaten();
   verschiebeBlockNach(start,ende,zeiger);
 }

Object liste = DoppeltVerketteteListe(); liste.einfgEnde("Apfel"); liste.einfgEnde("Birne"); liste.einfgEnde("Wasser"); liste.einfgEnde("Saft"); liste.einfgEnde("Brot"); liste.verschiebeNach("Wasser","Saft"); liste.verschiebeAnAnfang("Brot"); liste.verschiebeAnEnde("Saft"); liste.verschiebeBlockAnAnfang("Birne","Saft"); liste.verschiebeBlockAnEnde("Wasser","Brot"); liste.ausgabe();

ausführen

Vergleich der beiden Listentypen

Einfach- verkettete-Listen benötigen weniger Speicher als doppelt-verkettete-Listen, denn es muss pro Listenelement ein Zeiger weniger gespeichert werden.

Es zeigt sich das einfach-verkettete-Listen nur bei Funktionen am Anfang der Liste in konstanter Zeit arbeiten, alle anderen Funktionen sind von der Anzahl der Listenelement abhängig. Doppelt.verkettete-Listen arbeiten zusätzlich noch am Ende der Liste in konstanter Zeit.

Felder

Als Feld bezeichnet man eine Datenstruktur in der mehrere Variabeln vom gleichen Datentyp gespeichert sind. Der Zugriff erfolgt über Indices. Array liegen in einem bei ihrer Erzeugung festgelegten Speicherbereich. Die Indices verweisen daher von der Startadresse ausgehend auf den Speicherplatz des Elemets. Eindiemnsionale Array beteichnet man auch als Vektor. Zweidimensionale als Tabelle oder Matrix. Dabei gibt es keine Beschränkung wie viele Dimensionen ein Array maximal haben kann. Da Arrays eine der grundlegensten Datenstrukturen sind, sind sie in fast allen Programmiersprachen von Haus aus implementiert.

Beispiel für Felder

Wenn wir nun mit unserem Einkauf an die Kasse kommen wird dort vom Barcodescanner der Strickcode erfasst und in einen Wert umgewandelt. Dieser Wert sagt dem Kassensystem dann umwelches Element es sich handelt in der Warentabelle.

theoretischer Ansatz für Felder

Die Standard implementierung von Feldern reserviert beim erzeugen des Array eine festen Bereich im Speicher.

int[] bfeld = new int[10]; for(int i=0; i < 10; i++) bfeld[i] = i;

for(int i=0; i < 10; i++) bfeld[i] = i; for (int i = 0; i < bfeld.length; i++) { System.out.println("Element "+i+" = "+bfeld[i]); } //bfeld[10] = 10;

ausführen

Wenn durch hinzufügen die Speicherobergrenze erreicht wird, dann kann kein weiteres Element hinzugefügt werden. Um trotzdem weitere Elemente speichern zu können muss dafür ein kleiner Trick begangen werden. Wenn die Obergrenze erreicht ist wird ein neues Feld erzeugt das 2 mal so viele Elemente speichern kann wie das alte Feld. Dann werden alle Elemente des alten Feldes in dem neue gespeichert und zwar an der selben Position. Danach wird dem alten Feld das neue Feld zugewiesen und der Speicher für das Erzeugen des erweiterten Array wieder freigegeben.

public int[] BFeld(int anzahl){ return new int[anzahl]; } public int[] einfgEnde(int[] feld, int wert){ int i = 1; int j = feld.length - 1; if (feld[j]!= 0){ feld = aufstocken(feld); j = feld.length - 1;} while(i < j && feld[i]!= 0){ i++; } if (feld[i] == 0){ feld[i] = wert; } return feld; } public int[] aufstocken(int[] feld1) { int anz = 2 * feld1.length; int[] feld2 = BFeld(anz); for (int i=0; i < feld1.length; i++){ feld2[i] = feld1[i]; } return feld2; } public int[] entfEnde(int[] feld){ int i = 1; while(i < feld.length-1 && feld[i]!= 0){ i++; } i--; feld[i] = 0; if ( (i-1)*4 < feld.length) { feld = kleinerMachen(feld); } return feld; } public int[] kleinerMachen(int[] feld1){ int anz = feld1.length / 2; int[] feld2 = BFeld(anz); for (int i=0; i < feld2.length; i++){ feld2[i] = feld1[i]; } return feld2; }

int[] bfeld = BFeld(10); for(int i=0; i < 5; i++) bfeld[i] = i; bfeld = einfgEnde(bfeld, 8); bfeld = einfgEnde(bfeld, 9); bfeld = einfgEnde(bfeld, 10); bfeld = einfgEnde(bfeld, 11); bfeld = einfgEnde(bfeld, 12); bfeld = einfgEnde(bfeld, 13); bfeld = einfgEnde(bfeld, 14); /*bfeld = entfEnde(bfeld); bfeld = entfEnde(bfeld); bfeld = entfEnde(bfeld); bfeld = entfEnde(bfeld); bfeld = entfEnde(bfeld); bfeld = entfEnde(bfeld); bfeld = entfEnde(bfeld);*/ for (int i = 0; i < bfeld.length; i++) { System.out.println("Element "+i+" = "+bfeld[i]); }

ausführen

Funktionen für Felder

Kontrolle ob Feld leer ist

Wenn das Element mit dem Index "0" den Wert "0" hat, dann ist das Feld leer.

Zugriff auf das erste Element im Feld

Zugriff auf das Element mit dem Index "0".

Zugriff auf das letzte Element im Feld

Der Index des letzten Elementes ist entspricht der Anzahl der Element weniger 1.

Das Einfügen am Anfang des Feldes

1. Anlegen eines neuen Feldes
2. Einfügen des neue Elements in das neue Feld
3. Alle Elemente des alten Feldes an das neue Feld am Einfügen mit einem versatz von 1
4. Neues Feld auf altes Feld speichern

Das Einfügen nach einer beliebigen Position im Feld

1. Alle Elemente nach der Position in einem 2. Feld zwischenspeichern
2. Neues Element nach der Position einfügen
3. Ausgelagerte Elemente mit einem Versatz von 1 wieder einfügen

Das Löschen eines Elements eines Feldes

Dafür müssen die alle Einträge nach dem zu löschenden Element um eine Indexposition nach vorne eingefügt werden. Das bis dahin letzte Element wird mit der Wertezuweisung "0" gelöscht

Leeren eines Feldes

Das Element mit dem Indxex "0" wird auf "0" gesetzt.

Das Verschieben eines Elements im Feld

1. Das zu verschiebende Element wird zwischen gespeichert
2. Element löschen
3. Wenn das Element hinter seiner alte Position eingefügt werden soll, dann muss der Indexwert um 1 reduziert werden, sonst bleibt er gleich.
4. Einfügen des zwischengespeicherten Elements nach dem angebenen und eventuell modifizeriten Indice

Vergleich von Listen und Feldern

Felder sind beim Zugriff über ein Indice wesentlich schnell als Listen. Der große Vorteil von Listen ist das effiziente Verändern der Reihenfolge in einer Liste ob durch Verschieben oder durch Einfügen.