Version vom 26. Januar 2016, 21:13 Uhr

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 Verwaltungsklasse der Liste heißt meistens List und ihre Objekte 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.

Operationen

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

• Anfügen^[1] 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^[2]
• 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

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.

Fußnoten

1. ↑ Anfügen bedeutet immer: Ans Ende der Liste hinzufügen
2. ↑ Entweder per Angabe des zu entfernenden Elementes oder durch Angabe des Indizes