Aktuelle Version vom 1. Februar 2017, 19:05 Uhr

Eine Liste ist eine einfache rekursive Datenstruktur. Sie gehört zu den dynamischen Datenstrukturen. Eine Liste ist nützlich, um mit einer dynamisch großen Menge an Daten zu arbeiten. Mit einem Array ist das nicht unbedingt möglich, da dieses eine konstante Größe besitzt.

In der Objektorientierung wird eine Liste 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 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.

Begriffe

Um spezielle Bestandteile einer Liste einfacher benennen zu können, werden folgende Begriffe verwendet:

• Die first-Referenz der Liste zeigt auf das erste Element der Liste, auch Kopfelement genannt.
• Die last-Referenz der Liste zeigt auf das letzte Element der Liste, auch Fußelement genannt. Sie 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.

Elementklasse

Ein Objekt der Elementklasse besitzt ein Attribut um einen Wert zu speichern und eine Referenz auf das nächste Element in der Liste (next-Referenz).

Die Operationen der Listenklasse nehmen ausschließlich Werte vom Datentyp der in der Elementklasse gespeicherten Daten entgegen und geben auch nur diese zurück.

Elementobjekte sind meistens nicht nach Außen sichtbar und für den Verwender der Liste uninteressant.

Verwaltungsklasse

Erklärung

Die Listenklasse dient der Verwaltung.

Die eigentlichen Listenobjekte besitzen eine Referenz auf das erste (first-Referenz) und optional das letzte Element (last-Referenz) der Liste. Eine Liste ist leer, wenn die Referenzen des ersten und letzten Elementes auf den Nullpointer zeigen.

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

Beim Anfügen wird ein neues Element am Ende der Liste hinzugefügt.

Zuerst muss ein neues Elementobjekt erstellt werden.

Falls das letzte Element der Liste durch die last-Referenz bekannt ist, so wird die next-Referenz dieses bisher letzten Elementes auf das neue Element gesetzt. Außerdem wird die last-Referenz der Liste auf das neu angefügte Element gesetzt.

Falls das letzte Element der Liste nicht vermerkt ist, so muss zuerst nach dem ersten Element in der Liste, dessen next-Referenz auf den Nullpointer zeigt, gefunden werden. Dieses Element hat kein nächstes Element und muss daher das letzte sein. Wie im anderen Fall auch wird jetzt die next-Referenz dieses Elementes auf das neu eingefügte Element gesetzt.

Einfügen

Beim Einfügen muss die Liste vom ersten Element bis zur gewünschten Position durchlaufen werden. Ist diese gefunden, müssen zwei next-Referenzen geändert werden:

Zuerst wird die next-Referenz des neuen Elementes auf den ehemaligen Nachfolger seines Vorgängers gesetzt.

Dann wird die next-Referenz des Vorgängers auf das neue Element gesetzt.

Diese Reihenfolge ist wichtig, damit die Verkettung der Liste zu keinem Zeitpunkt unterbrochen wird. Ansonsten würde die Liste ihre Daten verlieren.

Auslesen

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

Entfernen

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

Beim Entfernen wird die Liste bis zum gewünschten Element durchlaufen.

Dann wird die next-Referenz vom vorigen Element (Vorgänger) auf das übernächste (Nachfolger) gesetzt. Das Element dazwischen ist damit nicht mehr Teil der Verkettung. Für gewöhnlich wird der Wert des entfernten Elementes im Anschluss zurückgegeben, um diesen weiter verwenden zu können. Das Element selbst ist jedoch nicht mehr erreichbar und wird vom Garbage Collector aufgesammelt.

Beim Durchlaufen der Liste sollte immer der Vorgänger des zu löschenden Elementes zwischengemerkt werden, da dieser ansonsten nicht wiedergefunden und damit auch seine Referenz nicht umgeändert werden kann.

Um das erste Element der Liste zu löschen, wird die first-Referenz auf das zweite Element gesetzt.

Leeren

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

Verwendungsbeispiel

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);
    }
}