Felder und Listen SS12

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2012-03-26T01:58:14+00:00. Aktuelle Version

Inhaltsverzeichnis

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.

Einkaufszettel-->Liste "Einkaufszettel"
Gurke-->Listenelement "Gurke"
Tomate-->Listenelement "Tomate"
Brot-->Listenelement "Brot"
Käse-->Listenelement "Käse"

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.

Definition des Listenelements

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.

Definition der einfach-verketteten-Liste


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
Definition der Kontrollfunktion ob einfach-verkettete-Liste leer ist




Zugriff auf das den Listenkopf für einfach-verkettete-Listen
Der Zugriff auf en Listenkopf erfolgt durch das zugreiffen auf die Klassenvariabel "kopf".
Zugriff auf das den Listenkopf für einfach-verkettete-Listen
 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.
Definition der Funktion die das erste Element einer einfach-verkettete-Listen zurückgibt
public Object holeErstesElement() {
 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.
Definition der Funktion zum holen des letzten Elements für einfach-verkettete-Listen
 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 3 Schritten.
Als ersten muss das neue Element angelegt werden.
Danach muss der Zeiger vom bis dahin letzten Element von "null" auf das neue Element geändert werden.
Zuletzt muss noch der Zeiger vom Kopfelement geändert werden so das dieser auf das neue letzte Element verweist.
Definition der Funktion zum Einfügen eines Elements am Ende der einfach-verketteten-Liste






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.
Als erste wird wieder ein neues Listenelement mit dem übergebenen Inhalt erzeugt.
Danach wird der Zeiger vom Kopfelement auf das bis dahin erste Element zwischengespeichert.
Anschließend wird der Zeiger vom Kopfelement so geändert das er auf das neue Listenelement zeigt.
Zuletzt wird der Zeiger des neuen Elements auf den zwischengespeicherten Wert angepasst.
Definition der Funktion zum Einfügen am Anfang der Liste






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. 
Definition der Funktion zum Einfügen nach einer beliebigen Position der Liste






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.
Definition der vereinheitlichten Funktion zum Einfügen






Das Löschen eines Elements für einfach-verkettete-Listen
Das Löschen eines Elements erfolgt in 3 Schritten.
Zu erste wird die Liste durchlaufen bis ein Elementgefunden wird dessen Nachfolger dem angegebenen Element entspricht.
Dann wird der Zeiger des Elements geändert.
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.
Definition der Funktion zum Entfernen eines Elements aus der Liste






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.
Es wird zunächst das Element gespeichert, dessen Nachfolger dem Startwert entspricht.
Als nächstes wird der Zeiger auf das Element gespeichert, dass auf den Endwert folgt.
Abschließend muss nur noch der Zeiger vom Vorgänger des Startwertes angepasst werden so das dieser auf den Nachfolger des Endwertes zeigt.
Definition der Funktion zum Entfernen mehrerer zusammenhängender Elemente






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.
Definition der vereinheitlichten Löschfunktionen






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.
Definition der Funktion zum Leeren einer Liste






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.
Definition der Funktion zum Verschieben eines Elemente






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.

Definition der Funktion zum Entfernen mehrerer zusammenhängender Elemente






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.
Definition der Verschiebefunktionen auf Basis von verschiebeBlockNach






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.
Definition des Listenelements




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.
Definition der Liste
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;
}





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 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 Zeigerauf den Nachfolger des Kopfelements auf "null" Zeigt ist die Liste leer
Definition der Funktion zum holen des ersten Elements
 public boolean istLeer() {
   if (kopf.holeNachfolger() == null) {
     return true;
   } else {
     return false;
   }
 } 


Zugriff auf das den Listenkopf
Der Zugriff auf en Listenkopf erfolgt durch das zugreiffen auf die Klassenvariabel "kopf".
Definition der Funktion zum holen des Listenkopfes
 public Object holeListenkopf() {
   return kopf;
 } 


Zugriff auf das erste Element
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.
Definition der Funktion zum holen des ersten Elements
 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.
Definition der Funktion zum holen des letzten Elements
 public Object holeLetztesElement() {
   Object le = kopf;
   while(le.holeNachfolger() != null){
     le = le.holeNachfolger();
   }
   return le;
 } 


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.
Als ersten muss das neue Element angelegt werden.
Danach muss der Zeiger vom Kopfelement auf das letzte Element so geändert werden das er auf das neue Element verweist.
Zuletzt muss der Zeiger vom bis dahin letzten Element so angepasst werden das er ebenfalls auf das neue Element verweist.
Definition der Funktion zum Einfügen eines Elements am Ende der Liste
 public void einfgEnde(Object inhalt) {
   Object neues = DListenElement(inhalt);
   Object letztes = holeLetztesElement();
   letztes.defiNachfolger(neues);
   neues.defiNachfolger(kopf);
   kopf.defiVorganger(neues);
   neues.defiVorganger(altes);
 }




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.
Als erste wird wieder ein neues Listenelement mit dem übergebenen Inhalt erzeugt.
Danach wird der Zeiger vom Kopfelement auf das bis dahin erste Element zwischengespeichert.
Anschließend wird der Zeiger vom Kopfelement so geändert das er auf das neue Listenelement zeigt.
Zuletzt wird der Zeiger des neuen Elements auf den zwischengespeicherten Wert angepasst.
Definition der Funktion zum Einfügen am Anfang der doppelt-verketteten-Liste
 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);
 }




Das Einfügen nach einer beliebigen Position in der doppelt-verketteten-Liste
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. 
Definition der Funktion zum Einfügen nach einer beliebigen Position der Liste
 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);
 }




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.
Definition der vereinheitlichten Funktion zum Einfügen
 public void einfgAmAnfang(Object inhalt) {
   einfgNach("h", inhalt);
 }
 public void einfgAmEnde(Object inhalt) {
   Object zeiger = holeLetztesElement().holeElementdaten();
   einfgNach(zeiger, inhalt);
 }




Das Löschen eines Elements aus einer doppelt-verketteten-Liste
Das Löschen eines Elements erfolgt in 3 Schritten.
Zu erste wird die Liste durchlaufen bis ein Elementgefunden wird dessen Nachfolger dem angegebenen Element entspricht.
Dann wird der Zeiger des Elements geändert.
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.
Definition der Funktion zum Entfernen eines Elements aus der Liste
 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.defiNachfolger(zeigere);
   zeigere.defiVorganger(zeigers);
 }




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.
Es wird zunächst das Element gespeichert, dessen Nachfolger dem Startwert entspricht.
Als nächstes wird der Zeiger auf das Element gespeichert, dass auf den Endwert folgt.
Abschließend muss nur noch der Zeiger vom Vorgänger des Startwertes angepasst werden so das dieser auf den Nachfolger des Endwertes zeigt.
Definition der Funktion zum Entfernen mehrerer zusammenhängender Elemente
 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);
 }




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.
Definition der vereinheitlichten Löschfunktionen für eine doppelt-verkettete-Liste
 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);
 }




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 den Zeiger vom Kopfelement auf "null" zusetzten. Damit werden alle Verweise auf Listenelemente gelöscht.
Definition der Funktion zum Leeren einer doppelt-verketteten-Liste
 public void listeLeeren() {
   kopf.defiNachfolger(kopf);
   kopf.defiVorganger(kopf);
 }




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 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.
Definition der Funktion zum Verschieben eines Elemente in einer doppelt-verketteten-Liste 
 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 && 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);
 }




Das Verschieben mehrere zusammenhängender Elemente
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.

Definition der Funktion zum Entfernen mehrerer zusammenhängender Elemente
 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);
   }
 }




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.
Definition der Verschiebefunktionen auf Basis von verschiebeBlockNach für doppelt-verkettete-Listen
 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);
 }





Vor und Nachteile
Felder
Vergleich von Listen und Feldern