Version vom 9. Juni 2016, 22:42 Uhr

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.

Begriffe

Um spezielle Elemente einer Liste einfacher bennennen zu können, verwendet man folgende Begriffe:

• Die first-Referenz der Liste zeigt auf das erste Element der Liste.
• Die last-Referenz der Liste zeigt auf das letzte Element der Liste. Dies ist optional.
• Die next-Referenz eines Elementes zeigt auf das nächste Element.
• Ein Objekt der Listenklasse verwaltet eine Liste.
• Ein Objekt der Elementklasse speichert ein einzelnes Element der Liste ab.

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:

• Zuerst muss das neue Datum in ein Elementobjekt eingebettet werden, damit es in die Datenstruktur aufgenommen werden kann.
• Wenn das letzte Element (last-Referenz) 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 sucht man nach dem ersten Element in der Liste, dessen next-Referenz auf den Nullpointer zeigt. Dieses Element hat kein nächstes Element und muss daher das letzte sein. Die entsprechende next-Referenz des letzten Elementes wird dann wie oben 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. Das zu entfernende Element ist dadurch nicht mehr in der Verkettung der Liste und damit entfernt. Für gewöhnlich wird der Wert des entfernten Elementes im Anschluss zurückgegeben um mit ihm bei Bedarf noch weiter zu arbeiten. Das Elementobjekt selbst ist jedoch 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 Attribut, 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 .

Verwendungsbeispiele

Implementierungsbeispiele werden hier nicht angegeben, da dies Teil der Praktikumsaufgaben ist.

public class Bank {
    private Personlist customers;

    public Bank(){
        this.customers = new Personlist();
    }

    public void addCustomer(Person customer){
        this.customers.add(customer);
    }
}