Liste

Eine Liste ist eine einfache rekursive Datenstruktur. Sie gehört zu den dynamischen Datenstrukturen. In der Objektorientierung wird eine Liste dabei meist aus zwei verschiedenen Klassen zusammengesetzt: Einer Art Verwaltungsklasse, die Repräsentant der Liste selbst ist, und einer Klasse für die Elemente, die von der Liste verwaltet werden sollen.

Eine Liste besteht dabei aus einem ersten Element und, falls gewünscht, einem letzten Element. Ein Element speichert dabei immer genau einen Eintrag in der Liste und eine Referenz auf das nächste Element der Liste (next-Referenz). Durch diese Verkettung der Referenzen entsteht die Reihenfolge der Elemente in der Liste.

Verwaltungsklasse

Die eigentlichen Listenobjekte besitzen je eine Referenz auf das erste und das letzte Element der Liste. Eine Liste ist leer, wenn die Referenzen des ersten und letzten Elementes auf den Nullpointer zeigen. Diese Verwaltungsklasse ist die Klasse, die ein Anwendungsprogrammierer verwenden möchte, um mit einer dynamisch großen Menge an Daten zu arbeiten. Mit einem Array ist dies nicht unbedingt möglich, da es eine konstante Größe besitzt.

Operationen

Auf Listen können folgende Operationen ausgeführt werden:

• Anfügen eines neuen Elementes
• Einfügen eines neuen Elementes an einer bestimmten Position in der Liste
• Auslesen eines beliebigen Elementes der Liste
• Entfernen eines beliebigen Elementes der Liste
• Abfrage, ob die Liste leer ist
• Leeren der Liste

Anfügen

Anfügen bedeutet immer, ein Element am Ende der Liste hinzuzufügen.

Es ist, je nach Implementierung, relativ einfach:

• Wenn das letzte Element der Liste bekannt ist, so wird die next-Referenz dieses Elementes auf das neue Element gesetzt und die last-Referenz der Liste wird auf das neue Element gesetzt.
• Wenn das letzte Element der Liste nicht vermerkt wird, so wird die gesamte Liste bis zum ersten Vorkommen einer null-Referenz durchlaufen und die entsprechende Referenz wird auf das neue Element gesetzt.

Einfügen

Beim Einfügen muss die Liste vom ersten Element bis zur gewünschten Position durchlaufen werden. Ist die gewünschte Position gefunden, wird die next-Referenz des vorherigen Elementes auf das neue Element gesetzt und die next-Referenz des neuen Elementes auf die ehemalige next-Referenz des vorherigen Elementes. Die Referenzen dürfen bei der Implementierung dabei natürlich auf keinen Fall verloren gehen, sonst bricht die Kette und die Liste verliert ihre Daten.

Auslesen

Beim Auslesen wird die Liste bis zum gewünschten Element durchlaufen und der Wert des gewünschten Elementes zurückgegeben.

Entfernen

Entfernen geschieht entweder per Angabe des zu entfernenden Elementes oder durch Angabe des Indizes.

Beim Entfernen wird die Liste bis zum gewünschten Element durchlaufen und sich das direkt vorherige Element zwischengemerkt. Ist das Element gefunden, wird die next Referenz des vorherigen Elementes auf das übernächste gesetzt. Dadurch ist das zu entfernende Element nicht mehr erreichbar und wird freigegeben.

Leeren

Die Referenz auf das erste (und letzte) Element der Liste wird einfach auf null gesetzt. Dadurch sind alle zuvor in der Liste vorhandenen Elemente nicht mehr erreichbar und werden freigegeben.

Elementklasse

Ein Objekt der Elementklasse ist meistens nicht nach Außen sichtbar und für den Anwendungsentwickler, der die Liste verwendet, nicht von Interesse. Es besitzt ein Feld, um den Wert des gespeicherten Datums zu speichern und eine Referenz auf das nächste Element in der Liste.

Die Operationen der Liste nehmen ausschließlich Werte vom Typ der in der Elementklasse gespeicherten Daten, nicht jedoch vom Typ der Elementklasse selbst entgegen und geben auch nur diese zurück .