AuK/Felder und Listen SS12
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
== 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.<br />
{| border="0"
| 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.
<popup name="Definition des Listenelements">
<code id="4f6f8846bd001">
public Object ListenElement (Object obj){
Object elementdaten = obj;
Object nachfolger = null;
public void defiNachfolger(Object nachfolger2) {
this.nachfolger = nachfolger2;
}
public Object holeNachfolger() {
return nachfolger;
}
public Object holeElementdaten() {
return elementdaten;
}
return this;
}
</code>
</popup>
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.
<popup name="Definition der einfach-verketteten-Liste">
<code id="4f6f8846bd3ea">
Object kopf = ListenElement("h");
public void ausgabe() {
Object le = kopf.holeNachfolger();
while(le != null){
System.out.println(le.holeElementdaten());
le = le.holeNachfolger();
}
}
</code>
</popup>
<code id="4f702f7c275ce" hidden>
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;
}
</code>
<run id="4f6f8846c2335">
list = EinfachVerketteteListe();
list.ausgabe();
</run>
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
<popup name="Definition der Kontrollfunktion ob einfach-verkettete-Liste leer ist">
public boolean istLeer() {
if (kopf.holeNachfolger() == null) {
return true;
} else {
return false;
}
}
</popup>
===== Zugriff auf das den Listenkopf für einfach-verkettete-Listen =====
Der Zugriff auf en Listenkopf erfolgt durch das zugreiffen auf die Klassenvariabel "kopf".
<popup name="Zugriff auf das den Listenkopf für einfach-verkettete-Listen">
public Object holeListenkopf() {
return kopf;
}
</popup>
===== 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.
<popup name="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;
}
}
</popup>
===== 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.
<popup name="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;
}
</popup>
===== Das Einfügen am Ende der Liste für einfach-verkettete-Listen =====
Das Hinzufügen am Ende der Liste erfolgt in 2 Schritten.
# Neues Element anlegen
# Der Zeiger vom bis dahin letzten Element von "null" auf das neue Element ändern
<popup name="Definition der Funktion zum Einfügen eines Elements am Ende der einfach-verketteten-Liste">
public void einfgEnde(Object inhalt) {
Object neues = ListenElement(inhalt);
Object letztes = holeLetztesElement();
letztes.defiNachfolger(neues);
}
</popup>
<run id="4f6f8846c25d7">
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());
</run>
===== 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.
# Neues Listenelement mit dem übergebenen Inhalt erzeugt
# Zeiger vom Kopfelement auf das bis dahin erste Element zwischenspeichern
# Der Zeiger vom Kopfelement so ändern das er auf das neue Listenelement zeigt
# Der Zeiger des neuen Elements auf den zwischengespeicherten Wert anpassen.
<popup name="Definition der Funktion zum Einfügen am Anfang der Liste">
public void einfgStart(Object inhalt) {
Object neues = ListenElement(inhalt);
Object zeiger = kopf.nachfolger;
kopf.nachfolger = neues;
neues.defiNachfolger(zeiger);
}
</popup>
<run id="4f6cd5ac0eead">
liste = EinfachVerketteteListe();
liste.einfgEnde("Apfel");
liste.einfgEnde("Birne");
liste.einfgEnde("Kiwi");
liste.einfgStart("Käse");
liste.ausgabe();
</run>
===== 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.
<popup name="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 != null && !zeiger.holeElementdaten().equals(vorfahre)) {
zeiger = zeiger.holeNachfolger();
}
neues = ListenElement(inhalt);
altes = zeiger.holeNachfolger();
zeiger.nachfolger = neues;
neues.nachfolger = altes;
}
</popup>
<run id="4f6df29cf0faa">
Object liste = EinfachVerketteteListe();
liste.einfgEnde("Apfel");
liste.einfgEnde("Birne");
liste.einfgEnde("Brot");
liste.einfgNach("Apfel","Käse");
liste.ausgabe();
</run>
===== 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.
<popup name="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);
}
</popup>
<run id="4f6ed093d6c06">
Object liste = EinfachVerketteteListe();
liste.einfgAmEnde("Apfel");
liste.einfgAmEnde("Birne");
liste.einfgAmEnde("Brot");
liste.einfgAmAnfang("Käse");
liste.ausgabe();
</run>
===== Das Löschen eines Elements für einfach-verkettete-Listen =====
Das Löschen eines Elements erfolgt in 2 Schritten.
# Durchlaufen der Liste bis ein Elementgefunden wird dessen Nachfolger dem angegebenen Element entspricht.
# Ä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.
<popup name="Definition der Funktion zum Entfernen eines Elements aus der einfach-verketteten-Liste">
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();
}
}
</popup>
<run id="4f6cf7c79b376">
Object liste = EinfachVerketteteListe();
liste.einfgEnde("Apfel");
liste.einfgEnde("Birne");
liste.einfgEnde("Brot");
liste.entf("Birne");
liste.ausgabe();
</run>
===== 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.
# Speichern des Elements, dessen Nachfolger dem Startwert entspricht
# Speichern des Zeigers auf das Element, dass auf den Endwert folgt
# Anpassen des Zeigers vom Vorgänger des Startwertes so das dieser auf den Nachfolger des Endwertes zeigt
<popup name="Definition der Funktion zum Entfernen mehrerer zusammenhängender Elemente">
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);
}
</popup>
<run id="4f6df29cf106f">
Object liste = EinfachVerketteteListe();
liste.einfgEnde("Apfel");
liste.einfgEnde("Birne");
liste.einfgEnde("Wasser");
liste.einfgEnde("Saft");
liste.einfgEnde("Brot");
liste.entferneBlock("Birne","Saft");
liste.ausgabe();
</run>
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.
<popup name="Definition der vereinheitlichten Löschfunktionen">
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);
}
</popup>
<run id="4f702f7c27c7b">
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();
</run>
===== 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.
<popup name="Definition der Funktion zum Leeren einer Liste">
public void listeLeeren() {
kopf.defiNachfolger(null);
}
</popup>
<run id="4f702f7c27e10">
Object liste = EinfachVerketteteListe();
liste.einfgEnde("Apfel");
liste.einfgEnde("Birne");
liste.einfgEnde("Wasser");
liste.einfgEnde("Saft");
liste.einfgEnde("Brot");
liste.listeLeeren();
liste.ausgabe();
</run>
===== 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.
# Ermitteln des Elements dessen Nachfolger das zu verschiebende Element ist und Speichern in zB.: elementInhaltVorganger.
# Ermitteln des Elements das auf das zu verschiebende Element folgt und Speichern in zB.: elementInhaltNachfolger.
# Ermitteln des Elements nach dem eingefügt werden soll und Speichern in zB.: elementPosition.
# Ermitteln des Elements das auf das Element folgt nach dem der Wert eingefügt werden soll und Speichern in zB.: elementPositionNachfolger.
# Den Zeiger von elementInhaltVorganger so setzten das er auf elementInhaltNachfolger zeigt.
# Den Zeiger von elementPosition so ändern das er auf das zu verschiebende Element zeigt.
# Den Zeiger vom verschobenen Elment so anpassen das er auf elementPositionNachfolger verweist.
<popup name="Definition der Funktion zum Verschieben eines Elemente in einer einfach-verketteten-Liste">
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);
}
</popup>
<run id="4f702f7c27fa4">
Object liste = EinfachVerketteteListe();
liste.einfgEnde("Apfel");
liste.einfgEnde("Birne");
liste.einfgEnde("Wasser");
liste.einfgEnde("Saft");
liste.einfgEnde("Brot");
liste.verschiebe("Apfel","Birne");
liste.ausgabe();
</run>
===== 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.
# Ermitteln des Elements dessen Nachfolger das zuverschiebende Startelement ist und Speichern in zB.: elementStartVorganger.
# Ermitteln des Elements das auf das zu verschiebende Endelement folgt und Speichern in zB.: elementEndeNachfolger.
# Ermitteln des Elements nach dem eingefügt werden soll und Speichern in zB.: elementPosition.
# Ermitteln des Elements das auf das Element folgt nach dem der Wert eingefügt werden soll und Speichern in zB.: elementPositionNachfolger.
# Den Zeiger von elementStartVorganger so setzten das er auf elementEndeNachfolger zeigt.
# Den Zeiger von elementPosition so ändern das er auf das zu verschiebende Startelement zeigt.
# Den Zeiger vom verschobenen Endelment so anpassen das er auf elementPositionNachfolger verweist.
<popup name="Definition der Funktion zum Entfernen mehrerer zusammenhängender Elemente">
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);
}
</popup>
<run id="4f702f7c2813a">
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();
</run>
===== 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.
<popup name="Definition der Verschiebefunktionen auf Basis von verschiebeBlockNach">
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);
}
</popup>
<run id="4f702f7c28276">
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();
</run>
=== 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.
<popup name="Definition des Listenelements">
<code id="4f702f7c276d0">
public Object DListenElement(Object obj){
Object elementdaten = obj;
Object nachfolger = null;
Object vorganger = null;
public void defiNachfolger(Object element) {
this.nachfolger = element;
}
public void defiVorganger(Object element) {
this.vorganger = element;
}
public Object holeNachfolger() {
return nachfolger;
}
public Object holeVorganger() {
return vorganger;
}
public Object holeElementdaten() {
return elementdaten;
}
return this;
}
</code>
</popup>
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.
<popup name="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;
}
</popup>
<code id="4f702f7c27812" hidden>
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;
}
</code>
<run id="4f702f7c283af">
Object list = DoppeltVerketteteListe();
list.ausgabe();
</run>
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
<popup name="Definition der Kontrollefunktion on doppelt-verkettete-Liste leer ist">
public boolean istLeer() {
if (kopf.holeNachfolger() == kopf) {
return true;
} else {
return false;
}
}
</popup>
===== Zugriff auf das den Listenkopf der doppelt-verkettete-Liste =====
Der Zugriff auf en Listenkopf erfolgt durch das zugreiffen auf die Klassenvariabel "kopf".
<popup name="Definition der Funktion für den Zugriff auf den Listenkopf der doppelt-verkettete-Liste">
public Object holeListenkopf() {
return kopf;
}
</popup>
===== 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.
<popup name="Definition der Funktion zum holen des ersten Elements aus einer doppelt-verkettetet-Liste ">
public Object holeErstesElement() {
if (istLeer() == false) {
return kopf.nachfolger;
} else {
return kopf;
}
}
</popup>
===== 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.
<popup name="Definition der Funktion zum holen des letzten Elements einer doppelt-verkettetet-Liste">
public Object holeLetztesElement() {
if (istLeer() == false) {
return kopf.vorganger;
} else {
return kopf;
}
}
</popup>
===== 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.
# Neues Element anlegen
# 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
# Der Zeiger vom bis dahin letzten Element so anpassen das er ebenfalls auf das neue Element verweist und dieses dann auf das Kopfelement
<popup name="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);
}
</popup>
<run id="4f702f7c284df">
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());
</run>
===== 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.
# Neues Listenelement mit dem übergebenen Inhalt erzeugen
# Zeiger vom Kopfelement auf das bis dahin erste Element zwischenspeichern
# Der Zeiger vom Kopfelement so ändern das er auf das neue Listenelement zeigt und dieses dann auf das alte erste Element
# Der Zeiger vom alten ersten Element so ändern das dieser auf das neuen Elements verweist und diese Element dann auf das Kopfelement
<popup name="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);
}
</popup>
<run id="4f702f7c28620">
Object liste = DoppeltVerketteteListe();
liste.einfgEnde("Apfel");
liste.einfgEnde("Birne");
liste.einfgEnde("Kiwi");
liste.einfgStart("Käse");
liste.ausgabe();
</run>
===== Das Einfügen nach einer beliebigen Position in der doppelt-verketteten-Liste =====
# Liste bis zur angegebenen Position durchlaufen
# Position und Zeiger auf den Nachfolger speichern
# Neues Element mit dem übergebenen Daten generieren
# Den Zeiger vom angegebenen Element so ändern das er auf das neue Element verweist und dieses dann auf den alten Nachfolger der angegebenen Position
# Den Zeiger vom ehemaligen Nachfolger der angegebene Psoition so ändern das dieser auf das neuen Element und dieses auf die angegebene Position verweist
<popup name="Definition der Funktion zum Einfügen nach einer beliebigen Position der doppelt-verkettete-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);
}
</popup>
<run id="4f702f7c2878f">
Object liste = DoppeltVerketteteListe();
liste.einfgEnde("Apfel");
liste.einfgEnde("Birne");
liste.einfgEnde("Brot");
liste.einfgNach("Apfel","Käse");
liste.ausgabe();
</run>
===== 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.
<popup name="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);
}
</popup>
<run id="4f702f7c288c6">
Object liste = DoppeltVerketteteListe();
liste.einfgAmEnde("Apfel");
liste.einfgAmEnde("Birne");
liste.einfgAmEnde("Brot");
liste.einfgAmAnfang("Käse");
liste.ausgabe();
</run>
===== Das Löschen eines Elements aus einer doppelt-verketteten-Liste =====
Das Löschen eines Elements erfolgt in 3 Schritten.
# Liste durchlaufen bis das angegebene Element gefunden wird
# Den Vorgänger und den Nachfolger zwischenspeichern
# Zeiger des Vorgängers auf den Nachfolger ändern
# Zeiger des Nachfolgers auf den Vorgänger ändern
<popup name="Definition der Funktion zum Entfernen eines Elements aus der Liste">
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);
}
</popup>
<run id="4f702f7c289fb">
Object liste = DoppeltVerketteteListe();
liste.einfgEnde("Apfel");
liste.einfgEnde("Birne");
liste.einfgEnde("Brot");
liste.entf("Birne");
liste.ausgabe();
</run>
===== 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.
# Speichern des Vorgängers des Startwertes und des Nachfolger des Endwertes
# Zeiger des Vorgängers zeigt auf Nachfolger
# Zeiger des Nachfolgers zeigt auf Vorgänger
<popup name="Definition der Funktion zum Entfernen mehrerer zusammenhängender Elemente aus einer doppelt-verketteten-Liste">
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);
}
</popup>
<run id="4f702f7c28b39">
Object liste = DoppeltVerketteteListe();
liste.einfgEnde("Apfel");
liste.einfgEnde("Birne");
liste.einfgEnde("Wasser");
liste.einfgEnde("Saft");
liste.einfgEnde("Brot");
liste.entferneBlock("Birne","Saft");
liste.ausgabe();
</run>
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.
<popup name="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);
}
</popup>
<run id="4f702f7c28c70">
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();
</run>
===== 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.
<popup name="Definition der Funktion zum Leeren einer doppelt-verketteten-Liste">
public void listeLeeren() {
kopf.defiNachfolger(kopf);
kopf.defiVorganger(kopf);
}
</popup>
<run id="4f702f7c28da6">
Object liste = DoppeltVerketteteListe();
liste.einfgEnde("Apfel");
liste.einfgEnde("Birne");
liste.einfgEnde("Wasser");
liste.einfgEnde("Saft");
liste.einfgEnde("Brot");
liste.listeLeeren();
liste.ausgabe();
</run>
===== 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.
# Speichern des Vorgängers des zu verschiebenden Elements in zB.: elementInhaltVorganger.
# Speichern des Nachfolgers des zu verschiebenden Elements in zB.: elementInhaltNachfolger.
# Speichern des Elements nach dem Eingefügt werden soll in zB.: elementPosition.
# Speichern des Elements des Nachfolgers von elementPosition in zB.: elementPositionNachfolger.
# Den Nachfolgerzeiger von elementInhaltVorganger so setzten das er auf elementInhaltNachfolger zeigt.
# Den Vorgängerzeiger von elementInhaltNachfolger so setzten das er auf elementInhaltVorganger zeigt.
# Den Nachfolgerzeiger von elementPosition so ändern das er auf das zu verschiebende Element zeigt.
# Den Vorgängerzeiger von dem zu verschiebenden Element s o ändern das er auf elementPosition zeigt.
# Den Nachfolgerzeiger vom verschobenen Elment so anpassen das er auf elementPositionNachfolger verweist.
# Den Vorgängererzeiger von elementPositionNachfolger anpassen so das er auf das zu verschiebende Elment verweist.
<popup name="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 && ( 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);
}
</popup>
<run id="4f702f7c28f02">
Object liste = DoppeltVerketteteListe();
liste.einfgEnde("Apfel");
liste.einfgEnde("Birne");
liste.einfgEnde("Wasser");
liste.einfgEnde("Saft");
liste.einfgEnde("Brot");
liste.verschiebe("Apfel","Birne");
liste.ausgabe();
</run>
===== 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.
# Speichern des Vorgängers des zu verschiebenden Startelements in zB.: elementStartVorganger.
# Speichern des Nachfolgers des zu verschiebenden Endelements in zB.: elementEndeNachfolger.
# Speichern des Elements nach dem Eingefügt werden soll in zB.: elementPosition.
# Speichern des Elements des Nachfolgers von elementPosition in zB.: elementPositionNachfolger.
# Den Nachfolgerzeiger von elementStartVorganger so setzten das er auf elementEndeNachfolger zeigt.
# Den Vorgängerzeiger von elementEndeNachfolger so setzten das er auf elementStartVorganger zeigt.
# Den Nachfolgerzeiger von elementPosition so ändern das er auf das zu verschiebende Startelement zeigt.
# Den Vorgängerzeiger von dem zu verschiebenden Startelement so ändern das er auf elementPosition zeigt.
# Den Nachfolgerzeiger vom verschobenen EndElment so anpassen das er auf elementPositionNachfolger verweist.
# Den Vorgängererzeiger von elementPositionNachfolger anpassen so das er auf das zu verschiebende Endelement verweist.
<popup name="Definition der Funktion zum Entfernen mehrerer zusammenhängender Elemente in doppelt-verkettete-Liste ">
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);
}
}
</popup>
<run id="4f702f7c291e9">
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();
</run>
===== 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.
<popup name="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);
}
</popup>
<run id="4f702f7c295db">
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();
</run>
=== 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.
{| border="1"
|-
| || '''einfach-verkettete-Liste''' || '''doppelt-verkettete-Liste'''
|-
| istLeer || konstante Zeit || konstante Zeit
|-
| kopf() || konstante Zeit || konstante Zeit
|-
| holeErstesElement() || konstante Zeit || konstante Zeit
|-
| holeLetztesElement() || Laufzeit abhängig von der Anzahl der Listenelemente || konstante Zeit
|-
| einfgStart() || konstante Zeit || konstante Zeit
|-
| einfgEnde() || Laufzeit abhängig von der Anzahl der Listenelemente || konstante Zeit
|-
| einfgNach() || Laufzeit abhängig von der Anzahl der Listenelemente || Laufzeit abhängig von der Anzahl der Listenelemente
|-
| entf(), entferneBlock() || Laufzeit abhängig von der Anzahl der Listenelemente || Laufzeit abhängig von der Anzahl der Listenelemente
|-
| entfAmAnfang() || konstante Zeit || konstante Zeit
|-
| entfAmEnde() || Laufzeit abhängig von der Anzahl der Listenelemente || konstante Zeit
|-
| verschiebe(), verschiebeBlockNach() || Laufzeit abhängig von der Anzahl der Listenelemente || Laufzeit abhängig von der Anzahl der Listenelemente
|-
| verschiebeAnAnfang() || Laufzeit abhängig von der Anzahl der Listenelemente || Laufzeit abhängig von der Anzahl der Listenelemente
|-
| verschiebeAnEnde() || Laufzeit abhängig von der Anzahl der Listenelemente || Laufzeit abhängig von der Anzahl der Listenelemente
|-
| listeLeeren() || konstante Zeit || konstante Zeit
|}
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.
{| border="1"
|-
| '''1. Dimension''' || '''2. Dimension''' || '''Wert'''
|-
| 0 || 0 || Apfel
|-
| 0 || 1 || 1,50€
|-
| 1 || 0 || Birne
|-
| 1 || 1 || 2,50€
|-
| 2 || 0 || Kiwi
|-
| 2 || 1 || 0,80€
|}
=== theoretischer Ansatz für Felder ===
Die Standard implementierung von Feldern reserviert beim erzeugen des Array eine festen Bereich im Speicher.
<code id="4f702f7c27936" >
int[] bfeld = new int[10];
for(int i=0; i < 10; i++) bfeld[i] = i;
</code>
<run id="4f702f7c2979c">
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;
</run>
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.
<code id="4f702f7c27a5b">
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;
}
</code>
<run id="4f702f7c2996a">
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]);
}
</run>
=== 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 ====
# Anlegen eines neuen Feldes
# Einfügen des neue Elements in das neue Feld
# Alle Elemente des alten Feldes an das neue Feld am Einfügen mit einem versatz von 1
# Neues Feld auf altes Feld speichern
==== Das Einfügen nach einer beliebigen Position im Feld ====
# Alle Elemente nach der Position in einem 2. Feld zwischenspeichern
# Neues Element nach der Position einfügen
# 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 ====
# Das zu verschiebende Element wird zwischen gespeichert
# Element löschen
# Wenn das Element hinter seiner alte Position eingefügt werden soll, dann muss der Indexwert um 1 reduziert werden, sonst bleibt er gleich.
# 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.