Liste

Eine Liste ist eine einfache rekursive Datenstruktur. In der Objektorientierung wird eine Liste dabei meist aus zwei verschiedenen Klassen zusammengesetzt: Eine Art Verwaltungsklasse, die repräsentant der Liste selbst ist, und einer Klasse für die Elemente, welche 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. 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 dem Nullpointer zeigen. Diese Verwaltungsklasse ist die Klasse, die ein Anwendungsprogrammierer verwenden möchte, um mit einer Liste zu arbeiten.

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 ist, je nach Implementierung, relativ einfach:

• Wenn das letzte Element der Liste bekannt ist, so wird die Referenz des nächsten Elementes dieses letzten Elementes auf das neue Element gesetzt und die Referenz auf das letzte Element 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.

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.